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
24 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 23, userów: 1, ukrytych: 0
I am vader
Użytkownicy na czacie discord
I am vader (12:50, 18.08.18):
gratki
Penguin (11:29, 18.08.18):
Gratulacje
exp (22:07, 17.08.18):
gratuluję również, kariera z przyszłością
Chell (15:00, 17.08.18):
dzieki
Wojo (11:37, 17.08.18):
Gratulacje
Chell (7:00, 17.08.18):
jaką stawkę myślicie że mogę wołać ako junior php po miesiącu praktyk i 2 stażu?
Chell (6:59, 17.08.18):
gmclany, zaraz będę kończył staż i zaczynał pracę na pół etatu
gnysek (9:54, 16.08.18):
niewiele, ale jest szybsze.
MaxGaming (3:25, 16.08.18):
Skoro pliki o rozszerzeniu html(przy standardowej konfiguracji serwera) są po prostu wyświetlane, a te z rozszerzeniem php wykonywane to czy użycie pliku html o tym samym kodzie jest szybsze niż pliku php(jeśli w źródle pliku znajduje się oczywiście sam kod hrml)?
Wojo (17:12, 15.08.18):
Exp podglądaj sobie reportaże o chwilowkach i o tym jak ludzie mają problemy z wyjaśnieniem że nie brali żadnego kredytu
exp (15:16, 15.08.18):
max czemu nie mógł udowodnić, nie chcieli sprawdzić jego podpisu? numer dowodu się zgadzał?
exp (15:15, 15.08.18):
no to też może się przydać, bo typ na koncie google miał podane imię i nazwisko i w adresie prawdopodobnie miał datę urodzenia, więc jak ktoś mnie okradnie, to mam podejrzanego. ale wątpię, że prokuratura będzie zainteresowana tym
I am vader (12:27, 15.08.18):
Nie powinno też się mordować ale to nie powstrzymuje ludzi
Wojo (22:26, 14.08.18):
Ale z drugiej strony nie powinno się kogoś okradać mimo wszystko
Sutikku (21:57, 14.08.18):
exp w formie dowodu mógłby pokazać, że nieumyślnie wysłał komuś swoje dane?
MaxGaming (17:37, 14.08.18):
Mój znajomy własnie wpadł w taką chwilówkę i jako że nie potrafił udowdnić że to nie on wziął to musi to spłacać
exp (17:36, 14.08.18):
no jak czytałem o tym, to w takiej sytuacji musisz de facto udowodnić niewinność
Wojo (19:56, 13.08.18):
z tym są różne scenariusze ale i tak powinien ktoś to uregulować bo to jest nienormalne jak mozna czlowiekowi zniszczyc zycie przez bledy mlodosci
exp (19:46, 13.08.18):
zna mój adres zameldowania, a nie zamieszkania, więc wyjebongo. boję się tylko o chwilówki itd. podobno w razie przyjścia komornika łatwo zamknąć sprawę, ale i tak nie chciałbym takich nieprzyjemności
Sutikku (19:29, 13.08.18):
osobiście myślę, że nic Ci nie grozi, ewentualnie pizza co wieczór będzie przyjeżdżać
exp (15:33, 13.08.18):
przez głupią literówkę wysłałem skan pewnego papieru niewłaściwej osobie. robię to regularnie i zrobiłem się trochę nieostrożny
exp (15:31, 13.08.18):
myślicie, że grozi mi coś, jeśli obcy człowiek posiadł prawie wszystkie moje dane osobowe? (ale nie zna mojego numeru dowodu)
gnysek (10:20, 11.08.18):
Dobra zrestartowałem serwer.
gnysek (10:36, 10.08.18):
wynajem!
MaxGaming (0:23, 10.08.18):
chodiz mi bardziej o doświadczenie niż hajs bo pracować wolę na swoim za mniej niż na etacie za więcej ale jednak pierwsza praca po technikum informatycznym od razu w marketingu to fajna sprawa. Tylko jeździć ponad 100km w jedną stronę codziennie pociągiem?
MaxGaming (0:22, 10.08.18):
więc nie mam pojęcia co robić
MaxGaming (0:22, 10.08.18):
wgl to zaproponowano mi prace w dziale marketingu jednej z polskich firm dzięki temu co uczę się na własną rekę, sam dyrektor działu marketingu stwierdził że woli takie osoby niż te świeżo po studiach które na studiach nie nauczą się praktycznie nic co jest na prawdę potrzebne w tej pracy ale... w WWA a ja mam jednak daleko żeby codziennie tam dojedżać
MaxGaming (23:56, 9.08.18):
nie wytłumaczysz że na prawdę rząd nie może stworzyć tych pieniędzy na 500 plus
MaxGaming (23:55, 9.08.18):
Obsługi telefonu dziecko się samo potrafi nauczyć. Teraz spróbuj nauczyć tego moją babcię. Zrozumcie że ludzie są różni. Znam 20 latków których
I am Lord (23:13, 9.08.18):
I nie chodził na żadne dokształcające najęcia
I am Lord (23:13, 9.08.18):
Mój tata pojechał do Norwegii bez języka i się nauczył go w rok już tak że coś tam rozumiał w pracy a przez 3 latach już w miarę płynnie gada
I am Lord (23:11, 9.08.18):
Przebywanie w obcym środowisku dłuższy czas sam w sobie uczy człowieka jezyka
Sutikku (22:46, 9.08.18):
zgadzam się
MaxGaming (22:40, 9.08.18):
Ale język nie jest potrzebny żeby przetrwać widocznie. Odpuścice trochę. Każda rozsądna osoba by się uczyła języka ale nie jest to jakiś przymus. Myślę że to właśnie dzięki temu że takie osoby nie myślą "nie znasz języka, nie próbuj" to przynajmniej nie siedzą na zasiłkach w Polsce tylko na zmywaku w Anglii
Sutikku (22:36, 9.08.18):
o przepraszam za przekleństwa, wydawały się tak adekwatne do treści, ze nie zauważyłem.
Sutikku (22:34, 9.08.18):
a co to za robienie gierek jak wychodzą Ci chujowe i są rakiem gamingu, i co z Ciebie za żołnierz jak chujowo strzelasz? Grunt, że próbują, efekty słabe fakt. Nie uważam, że to dobre i mądre wyjście, nie miałbym strefy komfortu gdybym nie mógł komunikować się w czyimś kraju, ale potrafię takich ludzi zrozumieć. Dziwniejsze jest dla mnie, że będąc tak długo w danym kraju język sam się nie podłapie.
Wojo (21:20, 9.08.18):
najwyraźniej nie jesteś patustem skoro nie potrafisz pojąć tego jak można żyć na krawędzi i bez żadnych zmartwień
I am vader (20:11, 9.08.18):
Ale co to za życie jak się izolujesz i stajesz się rakiem narodu?
Sutikku (17:40, 9.08.18):
potrafią i próbują ;p
Sutikku (17:40, 9.08.18):
słabe porównania, bo za granicę przeważnie jedzie się zarobić i żyć, a skoro oni zarabiają i żyją, to więcej im do szczęścia nie trzeba
I am vader (17:20, 9.08.18):
Jak idziesz na wojnę uczysz się strzelać, bo inaczej zginiesz. Jak chcesz zrobić grę to uczysz się programowania, bo inaczej nie dasz rady. Jak idziesz do szkoły uczysz się tego co Ci każą, bo inaczej jesteś idiotą. Jak wyjeżdżasz za granicę, uczysz się jezyka i kultury, bo inaczej jesteś pasożytem. Proste. Nie potrafisz, nie próbuj.
Wojo (14:32, 9.08.18):
Zazwyczaj są to ludzie, którzy nie lubią gdy narzuca im się jakiekolwiek zasady
exp (13:44, 9.08.18):
max, jeżeli nauczenie się języka kraju, w którym mieszka się na stałe jest dla niektórych niemożliwe ze względu na "strefę komfortu" to już nie wiem, co mam powiedzieć xd
exp (13:43, 9.08.18):
też znam ukraińców, którzy mówią po polsku, niektórzy bardzo dobrze. tak samo, jak wielu polaków w anglii czy niemczech też dobrze zna język miejscowy. nigdzie nie mówiłem, że wszyscy są źli, ale wielu
Wojo (13:15, 9.08.18):
propaganda cały czas istnieje tylko jest bardziej lub mniej intensywna. Aktualnie nie ma żadnej szansy aby dziecko nie było skażone propagandą (no chyba, że mieszka w jaskini)
MaxGaming (12:14, 9.08.18):
nie słuchałem jak ktoś kiedyś na tym forum polecał w każdym nowym telefonie taśmą zaklejać ten czujnik zalania i teraz mam problem XD
MaxGaming (12:09, 9.08.18):
za dużo propagandy już poszło. Trzeba by czekać a nowe pokolenie które nie jest skażone propagandą A o zgrozo propaganda nie ustaje
MaxGaming (12:08, 9.08.18):
W sumie demokracja to jedna wielka pułapka. Co możemy niby zrobić? Chodzić po domach i tłumaczyć ludziom żeby głosować na inne partie? Nie da rady przekonać większości
MaxGaming (12:07, 9.08.18):
sądzą że są sprytni bo wolą PO albo PiS, a to jest jeden ciort
MaxGaming (12:07, 9.08.18):
Ale tak jest w obie strpny. "Wpjna" PO/PiS to pułapka w którą większośc ludzi się łapie
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.02324 sekund ] [ Liczba zapytań MySQL: 13 ]