Fastbar
Powrót do strony głównej
Trzymaj pliki na gmclan.org!
Game Maker w pytaniach i odpowiedziach!
Polska dokumentacja
Tabela wyników ligi 24
Pobierz GM
Akademia GMCLANu
Kategorie bazy artykułów
Artykuły -> Kąciki programowania -> Algorytmy i struktury danych
Treść artykułu
Wyszukiwanie binarne
autor: Platyna (20.01.11)
     Wyobraźmy sobie, że chcemy znaleźć najmniejszą (lub największą) wartość spełniającą pewien warunek. Załóżmy, że nie istnieje szybki sposób na wyliczenie tej wartości, jednak dla zadanej wartości x potrafimy w prosty sposób odpowiedzieć czy wartość ta spełnia nasze wymagania czy nie. Wiemy również, że dla dowolnej liczby x jeśli spełnia ona nasz warunek to również wszystkie liczby większe (lub mniejsze) go spełniają, a jeśli nasz x nie spełnia wymagań to wszystkie liczby mniejsze (lub większe) też ich nie spełniają. Brzmi to jak jakiś teoretyczny bełkot matematyka więc by sytuacja stała się jaśniejsza posłużę się prostym przykładem:

     Nasz kolega wymyśla sobie pewną liczbę a do 1000 i nie mówi nam jaka to liczba. My możemy strzelić w dowolną liczbę i uzyskamy odpowiedź czy nasza liczba jest większa od a czy nie. I to zgadza się z wypowiedzianym wcześniej bełkotem. Bo jeśli liczba w którą strzeliliśmy spełnia warunek (jest większa) to również wszystkie liczby większe też go spełniają. Działa to również w drugą stronę. Jeśli nasz liczba nie spełnia warunku (kolega powiedział, że jest mniejsza) to również wszystkie liczby mniejsze też warunku nie spełniają.

     Teraz wyobraźmy sobie, że chcemy jak najszybciej odgadnąć o jakiej liczbie pomyślał nasz kolega. I tu w grę wchodzi właśnie wyszukiwanie binarne. Naszym warunkiem by liczba była "fajna" jest to, że ma być większa lub równa a. I tak jak mówiłem na samym początku, szukamy najmniejszej liczby spełniającej warunek, czyli właśnie liczby a. Bo a jest najmniejszą liczbą większą lub równą a. Gdybyśmy rzeczywiście próbowali odgadnąć liczbę kolegi nieświadomie zastosowalibyśmy właśnie algorytm wyszukiwania binarnego. Moglibyśmy strzelać po kolei wszystkie liczby od 1 do a, aż w końcu byśmy trafili. Pesymistycznie wykonalibyśmy n strzałów jeśli liczba pochodzi z przedziału od 1 do n. Stosując wyszukiwanie binarne zwykle liczbę odgadniemy znacznie szybciej. Wystarczy nam jedynie logarytm o podstawie 2 z a strzałów. Czyli dla przedziału od 1 do 1000000 pesymistycznie będzie to zaledwie 20 strzałów! Jak to działa?

     Załóżmy, że liczba jest z przedziału od 1 do 100. Strzelamy w połowę (czyli w 50) i już wiem czy jest ona z przedziału od 1 do 50 czy od 51 do 100. Zmniejszyliśmy przeszukiwany przedział o połowę. Załóżmy, że kolega powiedział, że 50 nie spełnia warunku (nie jest większe lub równe). Znów strzelamy w połowę (czyli w 75) i zostaje nam już tylko 25 możliwości. Po zaledwie 7 takich strzałach odgadniemy liczbę.

     Za pewne powiecie, że to nic nadzwyczajnego. Że taka strategia jest oczywista. To prawda. W tym konkretnym przykładzie. Jednak istnieją problemy w których nie widać na pierwszy rzut oka, że dobrym pomysłem będzie zastosowanie wyszukiwania binarnego. Posłużę się tutaj przykładem bardziej praktycznym i bardziej związanym z tym o czym jest ta strona czyli z grami.

     Wyobraźmy sobie, że mamy jakieś działko laserowe. Chcemy narysować od niego promień lasera o pewnej długości. Mianowicie promień ma się urwać gdy natrafi na jakąś przeszkodę. Nie potrafimy w żaden łatwy i szybki sposób obliczyć jaką długość powinien mieć promień i gdzie się kończyć. Ale powiedzmy, że mamy pewną funkcję, która otrzymuje odcinek i mówi nam czy na długości tego odcinka jest jakaś jakaś przeszkoda. W Game Makerze taką funkcją jest collision_line(). Możemy więc sprawdzać coraz dłuższe odcinki za każdym razem zwiększając je o 1 piksel, aż w końcu odcinek pewnej długości natrafi na przeszkodę. Rozwiązanie jest może i poprawne, ale bardzo wolne. Ale zauważmy, że jeśli odcinek długości x nie natrafi na przeszkodę to żaden, krótszy odcinek również nie. I to samo w drugą stronę. Jeśli odcinek długości x przetnie jakąś przeszkodę to każdy dłuższy też ją przetnie! Co nam to przypomina? Wyszukiwanie binarne! Świetny przykład, ale już nie taki oczywisty. Nie możemy łatwo obliczyć długości promienia, ale możemy łatwo sprawdzić czy promień o danej długości jest za krótki czy za długi. Gdybyśmy mięli mapę o długości 10000 to czasochłonne byłoby sprawdzanie kolizji z 10000 coraz dłuższych odcinków. A tak sprawdzimy ich zaledwie 14 (bo tyle wynosi logarytm dwójkowy z 10000).

Oto przykładowy kod algorytmu wyszukiwania binarnego w GML:

gml:

p=0; //początek przedziału w którym wyszukujemy wyniku
k=10000000; //koniec przedziału

while(p!=k) //w pewnym momencie nasz przedział będzie tak krótki, że będzie zawierał jeden element (p==k). To będzie nasz wynik
{
     q=floor((p+k)/2); //Strzelamy w połowę przedziału i zapisujemy do zmiennej q
     if(WARUNEK(q)) //jeśli q spełnia nasz warunek...
          k=q; //ucinamy przedział o wszystkie liczby większe od q
     else //w przeciwnym wypadku...
          p=q+1; //ucinamy przedział o wszystkie liczby mniejsze i równe q (bo q też jest złe więc je też ucinamy, stąd q+1)
}
return p; //zwracamy wynik


     Zależnie od tego czy zadowalają nas liczby większe czy mniejsze od tej w którą strzelamy nasz kod będzie wyglądał trochę inaczej. Ale wierzę w waszą wrodzoną inteligencję. Jeśli rozumiecie działanie tego kodu to sobie poradzicie.

     Na koniec wypadałoby jeszcze napomknąć, że wyszukiwanie binarne wcale nie musi dotyczyć tylko liczb całkowitych. Mając już przedział o długości 1 wciąż możemy dzielić go na pół. Możemy robić to w nieskończoność aż do osiągnięcia satysfakcjonującej nas dokładności. Świetnym przykładem będzie funkcja obliczająca wartość pierwiastka danej liczby. Następujący kod zwróci nam ją z dokładnością do 3 miejsc po przecinku:
gml:

p=0; //początek przedziału w którym wyszukujemy wyniku
k=argument0; //jako argument otrzymujemy liczbę której pierwiastek chcemy znaleźć

while(k-p>0.001) //W pewnym momencie nasz przedział wyszukiwania będzie bardzo mały. Taka dokładność nas zadowala.
{
     q=((p+k)/2); //Strzelamy w połowę przedziału i zapisujemy do zmiennej q (zauważ, że tu nie zaokrąglamy już q)
     if(q*q>=argument0) //jeśli q jest większe lub równe szukanemu pierwiastkowi
          k=q; //ucinamy przedział o wszystkie liczby większe od q (ustawiamy koniec przedziału wyszukiwania na q)
     else //w przeciwnym wypadku...
          p=q; //ucinamy przedział o wszystkie liczby mniejsze od q (zauważ, że brak tu +1 z poprzedniego kodu)
}
return p; //zwracamy wynik


Inne przykłady zastosowania wyszukiwania binarnego
     1. Mamy posortowaną tablicę liczb i chcemy sprawdzić czy znajduje się w niej jakaś liczba x. Strzelamy w środek tablicy. Jeśli liczba, która się tam znajduje jest za mała to szukamy na prawo od niej, a jeśli za duża to na lewo. Jeśli zostanie nam przedział jednoelementowy to gdy ten element jest równy x to znaleźliśmy szukaną liczbę. Jeśli jest inny to x nie występuje w tej tablicy.
     2. Mamy graf w którym krawędzie mają różne koszty przejścia. Chcemy znaleźć taką ścieżkę między wierzchołkami A i B, w której najdroższa krawędź ma możliwie najmniejszy koszt. Widzimy, że możemy strzelić w dowolny koszt x i sprawdzić czy istnieje ścieżka w której żadna krawędź nie przekracza x.

I to koniec mojego algorytmicznego bełkotu. Może później wymyślę i dodam jeszcze jakieś ciekawsze przykłady. Wyszukiwanie binarne ma ogromne zastosowanie w algorytmice, ale w praktyce raczej rzadko się przydaje. Ale zawsze staniecie się trochę mądrzejsi o te kilka słów. :)
głosów: 10 | ocena: 9.10 oceń zasób | dodał: Platyna
Komentarze
stron: 21

2


av

Platyna (19:18, 4.04.2011)

A co ma nie działać? Jak się rozumie to nie ma co sprawdzać. Można najwyżej przećwiczyć.

av

pablo1517 (23:48, 6.04.2011)

Jasne, jak chemik sobie coś wymyśli i mówi, że rozumie, to też nie przeprowadza doświadczenia, bo po co xD

stron: 21

2



Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
1 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
ANtY (9:07, 22.08.18):
elo co tam
ANtY (9:06, 22.08.18):
jak na swój wiek, doświadczenie w branży zarabiają mniej niż ludzie, którzy sami doszli do tej pozycji, dodatkowo wydają znacznie więcej co sprawia, że akumulują też dużo mniej pieniędzy, po prostu nigdy ich nie szanowali i nie nauczyli się odpowiedniego podejścia przez rozpieszczanie, głównie skupiają się na rozmyślaniu kiedy wjedzie główna część spadku i braniem kredytów akonto niż na inwestowaniu, czy zwiększaniu swoich zarobków
ANtY (9:04, 22.08.18):
ale jesli myslisz ze przepis na sukces w zyciu to miec bogatych rodzicow, ktorzy nie nauczyli cie pokory to polecam przeczytac ksiazke Millionaire Next Door, w skrocie takie osoby pomimo (a raczej przez to, że) otrzymywania dużych ilości pieniędzy na konsumpcję i innych giftów typu dom, czy auto, czy studia
ANtY (9:03, 22.08.18):
po pierwsze są zawody gdzie faktycznie po studiach będzie się trzepać niezłe hajsy (dentyści, specjaliści inni medyczni, dobrzy księgowi, czy prawnicy - szczegolnie jesli celujesz w rynek usług dla "bogatych" ludzi)
Wojo (7:58, 22.08.18):
i wiem, że te moje historyjki nie brzmią wiarygodnie ale taka jest prawda. Jeden z tych kolegów nawet pokazał mi GMCLAN w latach świetności
Wojo (7:44, 22.08.18):
więc nie ma też reguły na to, że bez studiów będzie zarabiać się miliony ale możesz zobaczyć po moim przykładzie na którego z tych kolegów pracodawcy będą patrzeć przychylniejszym okiem
Wojo (7:42, 22.08.18):
I jeśli mówimy teraz o umiejętnościach, mam kolegę, który jest cholernie inteligentnym człowiekiem, całą edukację otrzymywał w szkole same piątki, stypendia itp. i z tego co się dowiedziałem pracował/pracuje jako młodszy programista i zgarnia wydaje mi się gdzieś w granicach 4k mimo, że nie ma matury i technika. Drugi zaś znajomy, który jest niemniej mądry od niego wyjechał do Anglii na studia i wygląda na to, że całkiem dobrze mu tam idzie
Wojo (7:38, 22.08.18):
I Max nie wyjeżdżaj tutaj z Anglią bo ten argument jest trochę bez sensu. Równie dobrze można w Polsce odłożyć kilka pensji i na Ukrainie przez chwilę żyć na dobrym poziomie (jak to robią tamtejsi emigranci)
Wojo (7:36, 22.08.18):
moi rówieśnicy jeżdżą teraz wypasionymi samochodami bo ich starzy wzięli je dla nich w leasingu na firmę, a oni studiują dziennie, wożą się z laskami i całe dnie balują. To jest przepis na sukces - mieć bogatych rodziców, którzy zapomnieli nauczyć dziecko pokory
Wojo (7:33, 22.08.18):
moim wzorcem jest Piotr Kaszubski bo wieku 20 lat został milionerem (w POLSCE) i to bez studiów, nauki itp. !!!
I am Lord (0:41, 22.08.18):
Ten pierwszy z telekomunikacji robi diagnostyke i naprawy swiatlowodow
I am Lord (0:34, 22.08.18):
Jeszcze inny spelnia sie czysto naukowo gdzies tam robiac jakies wyklady i laboratoria ciekawe dla maluchow i młodzieży. Akurat to nie jest typowa praca ale bez studiow by sie nie obylo bo potrzebowal solidnych kontakow w uczelnianych kregach
I am Lord (0:30, 22.08.18):
Studia elektrotechniczne
I am Lord (0:29, 22.08.18):
i zarabiają solidne pieniądze
I am Lord (0:29, 22.08.18):
Mój znajomy po studiach zarabia około 3000 w firmie telekomunikacyjnej lokalnej, a innych też z tych samych studów robi w elektrowni wodnej zaś kolejny robi na wiatrakach
MaxGaming (22:05, 21.08.18):
Moi znajomi rzucający szkołę dawno temu kupują teraz auto po 100-200tyś a znajomi na studiach w tym samym wieku cieszą się z tego że w wolnym czasie podczas studiowania sa w stanie zarobić na kebsa i piwo
MaxGaming (22:03, 21.08.18):
zresztą nawet za 20tyś miesięcznie nie chciałbym do końca życia siedzieć po 8h dziennie programując na przykład
MaxGaming (22:02, 21.08.18):
Tym samym znajomi wobec których zachowywałem się wtedy tak jak większośc osób teraz gdy ja wam to mówię mają już dawno pensje o których chell ty marzysz a jak ty będziesz miał 20tyś wreszcie to oni będą dawno dalej. Ja tym bardziej mogę pomarzyć o ich życiu żeby nie było że kogoś tu obrażam osobiście. Po prostu zrozumiałem dlaczego mają rację i dlaczego zamiast słuchać babcinych rad lepiej odpalić excel i zrobić chłodną kalkulację
MaxGaming (21:59, 21.08.18):
Nie wiem czy to jest moja droga nawet ale wiem że zmarnowałem 4 lata(nic się nie nauczyłem tak na prawdę cennego w szkole, jeśli coś było cennego w szkole to sam się tego uczyłem w domu) a mogę lepszą pracę znaleźć bez technika niż z tym tytułem
MaxGaming (21:58, 21.08.18):
i czemu rozsądne? Bo konserwatywne a Polacy są mistrzami w zacofaniu? Bo mamy tak mówiły że idź na studia? Kiedyś mówiły dzieciom że mechanik to zawód z przyszłością. Wtedy był ale zanim nastał czas tych dzieci już dawno był to przeterminowany pomysł
MaxGaming (21:56, 21.08.18):
Poza tym nie dramatyzuj nikt nikogo nie opluwa. Nie twierdzę też że to droga dl wszystkich, ale mówię tylko że żałuje że mi ktoś tego nie uświadomił wcześniej
MaxGaming (21:56, 21.08.18):
Poza tym może pogadamy o Anglii? Kumam nie każdy chce wyjeżdzać ale czasy są takie że można za pomocą internetu robić interesy na całym świecie. Możesz być polakiem i sprzedawać na terenie Anglii siedząc w Polsce i zarabiać w ten sposób jakbyś tam mieszkał
MaxGaming (21:53, 21.08.18):
Jeśli masz umiejętności warte 20 kafli misięcznie to nikt nie pyta Cię o wykształcenie(w większości branży przynajmniej, oprócz np medycyny/państwówki itp)
Wojo (21:19, 21.08.18):
I dobrze mówisz chell. Wykształcenie to fajny dodatek do pozycji a nie magiczne konto premium
Chell (18:26, 21.08.18):
najbardziej mi się podoba fakt, że w tej swojej wizji świata który będzie ci lizał stopy tak bezczelnie plujesz na wszystko co rozsądne
Chell (18:25, 21.08.18):
tylko mam zdrową świadomość, że gdy zapracuje sobie na przebicie bariery 10 tysi kogoś w końcu zacznie interesować moje wykształcenie, i nie będę miał sufitu w postaci wykształcenia podstawowego
Chell (18:24, 21.08.18):
mój drogi, nie liczę na to, że studia mi podbija wypłatę z 2 do 20k
MaxGaming (14:34, 21.08.18):
w sumie teraz tak myślę że ja też wierzyłem w to bo ktoś tak powiedział a fajnie wierzyć że Twój naród jest lepiej wykształcony, ale gdy poznałem fakty szybko zmieniłem zdanie
MaxGaming (14:33, 21.08.18):
ja też ile nie słyszałem o tej wyższości polskich szkół. Dopóki nie pogadałem z kimś kto faktycznie uczy się np w anaglii
MaxGaming (14:32, 21.08.18):
ja te il
MaxGaming (14:30, 21.08.18):
to jest kompletny absurd. Albo przedmioty na które po prostu trzeba chodzić to chyba tylko polski pomysł. Mam na myśli takie przedmioty na których i tak wiesz że jest taki luz że nie musisz robić nic ale musisz mieć obecności i tracisz swój cenny czas
MaxGaming (14:29, 21.08.18):
więc każdy szedł żeby mieć obecności a albo sam z siebie wydedukował po kilku przykładowych zadaniach jak coś działa albo wracał do domu i uczył się z internetu
MaxGaming (14:28, 21.08.18):
matematyki wyglądała tak że pani profesor nawet nie miała opcji wyjaśnić czegoś tak żeby dotarło do 30 osób bo każdy jest inny
MaxGaming (14:28, 21.08.18):
ale polakom się coś powie i oni bezmyślnie powtarzają dlatego mamy fatalne szkoły i jeszcze fatalniejsze domniemanie że ta szkoła wpłynie poztytywnie na przyszłość. Tak brutalnie mówiąc jeśli musisz iść na studia by np być dobrym programistą to znaczy że jesteś zbyt głupi na bycie dobrym programistą. Wiedza nigdy nie była tak tania i tak powszechna jak dziś. Na prawdę jak wykładowca nie będzie kazał się czegoś nauczyć to nie będziesz umiał sam z siebie się tego
exp (14:25, 21.08.18):
polacy to ogólnie strasznie zakompleksiony naród i sytuację tego kraju powoduje głęboko zakorzeniona polska mentalność. ale to nie zmieni się jeszcze przez długi, długi czas albo i nigdy
exp (14:23, 21.08.18):
a pamiętam, jak za czasów szkolnych wszyscy płonęli dumą, bo podobno polska edukacja jest dużo wyżej i jak polscy uczniowie jadą na wymianę na zachód, to są zawsze kilka szczebli wyżej
MaxGaming (14:15, 21.08.18):
osoby w wieku 16 lat w anglii mają większą wiedzę niż u nas po studiach, ale.. nie mają za to zbędnych ton wiedzy którą w polsce przyjeło się że "wypada mieć"
MaxGaming (14:15, 21.08.18):
Znajomi w anglii którzy się uczą gdy mówią mi jak tam wygląda szkoła to już rozumiem dlaczego polska szkoła zwyczajnie nie może działać
MaxGaming (14:14, 21.08.18):
Nie wiem czemu jako polacy mamy takie kompleksy na punkcie wykształcenia takiego typowo akademickiego. Cieżko do polaków dotrzeć że można się wykształcić poza szkołami, ale to wina PRLu i tego jak później każdy myślał że będzie kimś wielkim bo pójdzie na studia i w nowym systemie będzie bogatym
MaxGaming (14:12, 21.08.18):
miałem też przyjemność rozmawiać z szefem marketingu w polskim startupie mającym 200zł na godzinę i ... wykstzałcenie podstawowe. To jest po prostu śmieszne. Moi znajomi idący na studia liczą że po zrobieniu ich będą zarabiali 3-4tyś a ich rówieśnicy po gimnazjum zarabuają 3-4tyś. I to żadne wyjątki a norma. Wyjątki to są które bez studiów zarabiają czterocyfrowe sumy
MaxGaming (14:10, 21.08.18):
masz studia czy nie
MaxGaming (14:10, 21.08.18):
Chell ile my mamy lat żeby wierzyć że jak zrobisz wyższe to będziesz nagle z 2 tyś zarabiał 20tyś? Nie rozumiem jakie mam mieć arguemnty inne niż znajomi lub inne osoby z którymi się spotykam w swoim życiu. Poza tym przez 4 lata można spokojnie zostać ekspertem w czymś albo skończyć technikum po którym niczego się nie nauczy. Jeśli celujesz powyżej 10 tyś to nawet nie ma mowy o liczeniu na studia. Tutaj już trzeba dać coś z siebie coś więcej ale w takiej sytuacji nic
Wojo (13:47, 21.08.18):
I żeby nie było, nie hejtuję nauki tylko chodzi mi o to, że wykształcenie nie jest wszystkim co człowiek powinien posiadać.
Wojo (12:43, 21.08.18):
A w szkołach wpaja się do głowy bzdurną regułkę "idź na studia bo bez studiów będziesz pracował za minimalną!"
Wojo (12:42, 21.08.18):
I jak dla mnie to wartość człowieka jest istotna bo możemy zobaczyć magistrów, licencjatów robiących na tym samym stanowisku za te same pieniądze co ludzie po zawodówce czy bez szkoły.
Wojo (12:39, 21.08.18):
a jeśli faktycznie ktoś będzie dobry w swoim kierunku i zrobi doktorat to minie wiele lat. Pomijam tutaj kierunki, które faktycznie wymagają nauki i wielu wyrzeczeń (np. lekarskie), ale studia dzienne na badziewnych kierunkach to przedłużenie gimnazjum MOIM ZDANIEM.
Wojo (12:36, 21.08.18):
jak dla mnie całe liceum to była propaganda. wpajanie uczniom do głów tekstów w stylu "idź na studia dzienne na polonistkę to coś z ciebie będzie" i później wielkie zdziwienie, że 23 letni chłopak nigdy nie pracował i nie ma pracy w tym kraju z jego wykształceniem
gnysek (11:49, 21.08.18):
Ja się w szkole nauczyłem assemblera, także cośtam dała.
Chell (10:47, 21.08.18):
no niestety nie zyjemy w czasach, gdy kazdy jest unikalnym platkiem sniegu i byle komu sie cos nalezy na podstawie tego, ze ma fajne pomysly
Chell (10:46, 21.08.18):
koles z niepelnym zawodowym moze sobie zalozyc firme blacharska i dorobic sie 10k miesiecznie, ale to przypadek jeden na milion, i nie brzmi jakos zajebiscie dumnie
Ankieta
» Jakie kursy najchętniej widziałbyś na stronie ?
GM Studio
GM Studio 2
Godot
Construct

GMCLAN to serwis o programie Game Maker i nie tylko.
[ Polityka prywatności ]
Copyright © 2002-2018. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2018 {=|=} fable_inside();

[ Czas generowania strony: 0.02882 sekund ] [ Liczba zapytań MySQL: 13 ]