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) | czas czytania: 7 minut, 1 sekunda
     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
gnysek (13:58, 18.02.19):
bo tam są głównie XMLe, wiec kazdy edytor do www się nada
gnysek (13:58, 18.02.19):
ja otwierałem w phpstormie i robiłem replace
nowy_user (13:45, 18.02.19):
BTW. Na forum YoYo coraz większe naciski ze strony użytkowników. Podoba mi się to, że użytkownicy wywierają presję na Yoyo, aby produkt i forum dalej się rozwijały. Nie podoba mi się natomiast to, że Yoyo samo nie wychodzi z inicjatywą :/
nowy_user (13:44, 18.02.19):
Dzięki za info, postaram się jeszcze pokombinować z GMEdit , może tam będzie ta opcja.
gnysek (13:28, 18.02.19):
a faktycznie, nie ma globalnego replace, to w GMS2 tylko, trzeba robić globalny find i ręcznie zmieniać
nowy_user (10:30, 18.02.19):
Niestety, w edit jest opcja Find a resource (Ctrl+R) ale to pozwala wyszukiwać np. całe obiekty sprity itd. Nie do końca mi o to chodziło. To, co ja bym chciał zrobić to np. podmienić nazwę jednej zmiennej, która jest dość nieintuicyjna, a pojawia się bardzo często, i jest porozsiewana po różnych obiektach i skryptach. Chciałbym móc podmienić nazwę tej zmiennej we wszystkich miejscach, za jednym zamachem...
gnysek (10:05, 18.02.19):
wejdź do menu "Edit" i tam chyba będzie, wraz ze skrótem.
nowy_user (9:24, 18.02.19):
Panowie, prosta sprawa, nie wiem czy czegoś nie widzę przez jakieś chwilowe zaćmienie umysłu, ale gdzie w GM1.4 jest opcja globalna 'search and replace' ? Lokalnie, dla danego obiektu pojawia sie po wciśnięciu ctrl+F , natomiast globalnie, jak wcisnę ctrl+shit+F to pojawia się sama wyszukiwarka, bez opcji replace... Chciałem zmienić nazwę jednej zmiennej, chyba nie będę musiał tego robić ręcznie?
Konrad-GM (0:12, 18.02.19):
Yup, dokładnie tak powinno chodzić, potem jest trochę więcej różnorodnych pułapek, więc robi się coraz trudniejsze
I am Lord (0:06, 18.02.19):
ale aż tak? www.youtube.com...eature=youtu.be
Konrad-GM (23:58, 17.02.19):
Ten kurczak szybko chodzi, więc to ficzer jest, żeby za łatwo nie dało się przejść gry
I am Lord (23:52, 17.02.19):
ok teraz 8, ale nie wiem czy u mnie czasem nie za szybko chodzi ten kurczak
I am Lord (23:50, 17.02.19):
5 jajaec zdobyłem
I am Lord (23:46, 17.02.19):
12 minut zostało a nie mam game playu jeszcze tylko sama grafika
I am Lord (23:46, 17.02.19):
ja nie zdąrze
Konrad-GM (23:41, 17.02.19):
Dodałem grę na ligę, ale zczaiłem się dopiero teraz, że czarny kolor to przecież też kolor kek, nie bijcie
gnysek (10:35, 15.02.19):
jak jeszcze gdzieś zostały, dawajcie znać
I am Lord (17:40, 14.02.19):
to się nie sprawdzi przy takiej małej ilości osób. Żadne posty się nie gubią tutaj w tłumie żeby je wyróżniać
I am Lord (17:40, 14.02.19):
wyłącz te oceny
gnysek (10:29, 14.02.19):
jeszcze wieczorem zajrzę w kod, jak nie znajdę żadnej opcji to wyłączę ocenianie w tych działach i tyle, i tak mało kto tego potrzebuje, to nie stackoverflow
gnysek (0:46, 14.02.19):
musiałbym chyba wyłączyć oceny
nowy_user (20:43, 13.02.19):
To prawda, jest to irytujące.
I am Lord (20:11, 13.02.19):
da się wymusić żeby to cholerne sortowanie po ocenie postu nie było domyślne? Straszliwie mnie wnerwia
gnysek (11:50, 13.02.19):
tzn. wcześniej też na forach się sporo działo, ale nie miałem internetu to nie widziałem
gnysek (11:49, 13.02.19):
Pamiętam, lata 2003-2008 to chyba takie najbujniejsze. Aż weszły facebooki i smartfony.
Temporal (17:18, 12.02.19):
jestem człowiekiem starej daty i żyje czasami, gdy wszystko działo się na forach internetowych
Temporal (17:17, 12.02.19):
wiem co to Discord, tak tylko głupoty wypisuje
I am Lord (17:12, 12.02.19):
discord to chat a nie portal społecznościowy
I am Lord (17:05, 12.02.19):
bo rozmowy się toczą na discordzie tylko
Temporal (16:51, 12.02.19):
boję się Discordów, Facebooków i Instagramów
SimianVirus7 (22:59, 11.02.19):
tu zwykle jest cicho z tego co wiem na discordzie więcej się dzieje
nowy_user (15:37, 11.02.19):
Wszyscy piszą gry, nik nie ma czasu na pogawędki
Temporal (15:33, 11.02.19):
co tu tak cicho?
nowy_user (17:20, 9.02.19):
Morał z tych historii: Róbcie backupy
Temporal (15:39, 9.02.19):
brzmi jak dobra copypasta
Konrad-GM (14:59, 9.02.19):
Kiedyś robiłem grę w Unity, crash co chwila, a potem ostatni crash usunął mi sporą część assetów w jakiś dziwny sposób, że nie mogłem odzyskać większości kodu czy modeli a kopia mocno była nieaktualna, usunąłem Unity i od tamtej pory nigdy nie wróciłem xD
I am Lord (13:52, 9.02.19):
miałem strzelankę topdown z generowanymi jaskiniami w planach
I am Lord (13:51, 9.02.19):
Ja nie oddałem na ligę bo mi crash GMS2 zepsuł projekt i się wkurzylem. Odinstalowałem go
Temporal (10:13, 9.02.19):
kiedy ten GM mi się znudzi? cały czas jestem pod wrażeniem jak dobry jest ten soft. Oczywiście ma jakieś swoje bolączki i są bardziej zaawansowane silniki, ale to wciąż doskonałe narzędzie zarówno dla początkujących twórców gier jak i zaawansowanych. Tworzenie gier w tym środowisku to sama przyjemność
gnysek (22:03, 8.02.19):
Nie wyjdzie. Jest plan na cały rok rozpisany i nie ma tam gms3. A zniżki były co roku.
nowy_user (18:22, 8.02.19):
Pojawiła się nowa promocja, Lunar Sale, nawet do 50% zniżki na GMS2 Mobile. Chyba niedługo wyjdzie GMS3, skoro co chwila nas zasypują promocjami
nowy_user (22:05, 5.02.19):
Dzięki, wyglada bardzo solidnie, chyba z niego skorzystam
gnysek (17:03, 5.02.19):
mydevil.net po tym jak hekko ceny podniosło
nowy_user (14:40, 5.02.19):
Hej, jaki niedrogi i dobry hosting polecacie do prostego landing Page’a, na którym mógłbym zaprezentować apkę zrobioną w GM? Najlepiej taki, który obsługuje WordPressa, bo bardzo do gustu przypadła mi wtyczka Elementor Page Builder
Sutikku (22:58, 4.02.19):
dziury w głowie
Sutikku (22:58, 4.02.19):
zapomniałem skończyć gierkę na lige .-.
SimianVirus7 (17:35, 4.02.19):
Myślę, że parę dobrych duszyczek by się znalazło i ufundowało nagrody. Jeśli pomysł się spodoba, ja również mogę dorzucić coś od siebie
SimianVirus7 (17:33, 4.02.19):
Można by zrobić jakiś worek gier (ale nie śmieciowych). Human: fall flat, Hollow Knight, Bioshock Inifite, Gothic Universe Edition. To wszystko dobre gry za małą cenę <20zł
Dester (17:13, 4.02.19):
nagrody na Steam na pewno były by bardzo motywujące
Dester (16:53, 4.02.19):
temat był za trudny
Ankieta
» Ile powinny trwać tury Ligi 24?
24h
48h
54h (piątek od 18:00)
7 dni
inna długość (podałem w komentarzu ankiety)

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

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