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
exp (23:59, 9.12.18):
teraz spoko wygląda
MaxGaming (23:28, 9.12.18):
To już dużo lepsze! Chociaż nadal wygląda trochę jakby to był bug a nie feature
gnysek (22:33, 9.12.18):
ok, to zostawię wersję pierwszą jaką miałem - zmniejszenie przeźroczystości. Będą lekko jaśniejsze ikonki.
MaxGaming (22:24, 9.12.18):
ale nie wszystko na szaro(bo najczęściej większość tematów jest szara przez mały ruch)
MaxGaming (22:24, 9.12.18):
lepiej już oznaczyć wykrzyknikiem małym te nowe, albo coś
MaxGaming (22:23, 9.12.18):
Według mnie to glupio działa. Nagle wszystko jest szare jakby się zepsuło
gnysek (17:26, 9.12.18):
Od teraz posty napisane przed waszą ostatnią wizytą dostaną szarka ikonkę na stronie głównej - łatwiej znaleźć nowy kontent
MaxGaming (17:22, 9.12.18):
po prostu rób coś, zdobywaj doświadczenie i czytaj na jakiś temat żeby się rozwijać
exp (16:43, 9.12.18):
kurczę chciałbym się znać na czymś tak jak ty na gamedevie
exp (16:42, 9.12.18):
aha, więc to o to chodzi
gnysek (13:51, 9.12.18):
prawdopodobnie po to, żeby Steam VAT odprowadzał w stanach, w których trzeba, w Twoim imieniu.
gnysek (13:51, 9.12.18):
bo teraz 100$ wystarczy, tylko z polskiego punktu widzenia musisz zgłosić firmę do podatku (zerowego), w USA (telefonicznie), żeby dostać ichni NIP.
exp (13:40, 9.12.18):
właśnie też wyczytałem to w regulaminie, no ale coś mi tu nie pasuje. ludzie ciągle wrzucają na steama takie gówienka, że nie wierzę, że oni się tak wysilali
gnysek (13:24, 9.12.18):
musiałbyś założyć firmę, zawrzeć umowę ze steam itd.
Temporal (9:52, 8.12.18):
ambicje zawsze nas gubią
exp (22:52, 7.12.18):
w sensie 99 dolarów
exp (22:50, 7.12.18):
tak z ciekawości, jakbym chciał sprzedawać swoją grę, np. na steamie, to po prostu wystarczy zrobić upgrade do wersji "developer" za cztery stówki?
exp (14:37, 7.12.18):
ale mój poprzedni koncept był całkiem fajny i chyba oryginalny. było to tak jakby połączenie spelunky i contry, choć nie do końca
exp (14:36, 7.12.18):
znów naszła mnie ochota na zrobienie gierki i dobrze wiem, że skończy się tak, że mój prosty pomysł się rozrośnie i nigdy jej nie skończę
MaxGaming (23:53, 6.12.18):
co tam u was mordeczki
MaxGaming (3:01, 5.12.18):
też o tym myślałem, lub po prostu ograniczenie np maks 4 strzał i trzeba wytwarzaćnowe
gnysek (23:04, 4.12.18):
Dzida/oszczep. Można rzucać i ma jakaś tam wytrzymałośc, nie trzeba naboi, w razie czego można wytwarzać nową.
exp (19:16, 4.12.18):
może zastawianie pułapek
MaxGaming (17:45, 4.12.18):
U mnie to działa trochę inaczej. Ciężko ranne zwierze przyśpiesza i albo ucieka albo podejmuje walkę i wtedy szarżuje w naszym kierunku
MaxGaming (17:41, 4.12.18):
np łuk, tylko trzeba to tak zrobić aby taki łuk nadawał się jedynie do absolutnie podstawowych celów
MaxGaming (17:41, 4.12.18):
ze trzeba coś zrobić jako taką broń powszednią która akurat będzie miała sporo naboi i łatwo je będzie zdobyć
MaxGaming (17:40, 4.12.18):
hmm, ciekawy system, ale na razie chodzi mi
gnysek (17:37, 4.12.18):
wtedy można mieć mało naboi i ryzykujesz, albo strzelasz 2/3 razy i zgon od razu, albo czekasz aż padnie
gnysek (17:36, 4.12.18):
duże powinny krwawić, jednym strzałem = czekasz 5 minut na śmierć, albo strzelasz dalej
MaxGaming (17:35, 4.12.18):
a chodzi mi o stworzenie bardzo realnego respectu dla dużych zwierząt, chcę żeby polowanie na coś dużego było dla gracza czymś wyjątkowym i odświętnym, kiedy znajdzie jakąś amunicję do fajniejszej broni
MaxGaming (17:34, 4.12.18):
Co nie jest takie proste, bo strzelanie z łuku 3 razy żeby zabić zająca to na przykłąd pomyłka i byłoby bardzo śmiesznie. Zabicie zająca za jendym strzałem = obrażeniom na tyle dużym że na upartego upolowałoby się i dużo większe zwierzęta
MaxGaming (17:34, 4.12.18):
coś takiego żeby nie dało się z tego za wiele zrobić, ale żeby wystarczyło na polowanie na najprostrze zwierzęta pokorju zająca żeby zdobyć pożywienie
MaxGaming (17:33, 4.12.18):
a same pociski będą na wagę złota. Tylko muszę wymyślić jak w to wszystko wpleść uzbrojenie inne niż broń palna
MaxGaming (17:33, 4.12.18):
broń krótka na prawdę nie za bardzo nadaję się do polowania ze względu na swój bardzo mały zasięg i celność, broń pokroju kar98k dla gracza który według fabuły nie za bardzo miał wcześniej kontakt z militariami nie jest szybka do przeładowania i chociaż ma duży zasięg i potrafi powalać z nóg na prawdę szybko to jednak jeden pochopny strzał i zanim przeładujemy to możemy być już martwi
MaxGaming (17:31, 4.12.18):
ale jednoczęśnie funkcjonalna. Unikam realizmu na siłę który by komplikował rozgrywkę i zmieniał ją w niezrozumiałą, a staram się to nadrobić po prostu realizmem w postaci ograniczeń które nałożone są na nas
MaxGaming (17:30, 4.12.18):
jak wspominałem już moja gra ma być jak najprostrza zarówno dla gracza jak i dla mnie w rozwijaniu
MaxGaming (17:30, 4.12.18):
a w grze otwartego świata wcale być nie miało, dopiero w trakcie tworzenia doszedłem do wniosku że można to łatwo i fajnie zrobić i jednoocześnie uniknąc problemów typu "mam misje fabularną 10tyś pikseli ode mnie"
MaxGaming (17:29, 4.12.18):
ale to ma swój haczyk, bo nie dałoby się w tak prosty sposób zrobić otwartego świata, ale wiem jak obejść minusy tego
MaxGaming (17:28, 4.12.18):
Zrobiłem w swojej grze teoretycznie nie limitowany niczym otwarty świat, w praktyce jedynym limitem jest pozycja, czyli zwyczajnie żeby x i y były w stanie się zmieścić w int'cie
MaxGaming (17:09, 4.12.18):
#JANUSZ100%
MaxGaming (17:05, 4.12.18):
To ja daję 20euro jak zorganizujesz to tak że ja ją wygram
gnysek (10:43, 4.12.18):
mam nadzieję w święta w końcu wgrać zmiany które mam gotowe i ruszyć z drugim sezonem ligi 24... jakieś nagrody zorganizujemy, sam osobiście dam kartę na 25eur na Steam
gnysek (10:41, 4.12.18):
że kiedyś był cebulacki ?
Wojo (23:53, 3.12.18):
polemizowałbym
exp (22:56, 3.12.18):
Wojo gmclan raczej nie jest takim cebulackim forum, może kiedyś trochę było, ale i tak wszystko w granicach
MaxGaming (1:05, 3.12.18):
słuszna uwaga w sumie
gnysek (0:42, 3.12.18):
spróbuj z while
MaxGaming (23:34, 2.12.18):
Wybaczcie bo nie jestem w stanie wygooglować. Ma ktoś pojęcie jaka jest maksymalna ilość znaków dla stringa w GMS 1.4?
Wojo (21:55, 2.12.18):
czyli mniej więcej tak jak na gmclanie
exp (19:57, 2.12.18):
potem mogą walić konia do swojej elitarności na swoim forum z 9 użytkownikami
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.01813 sekund ] [ Liczba zapytań MySQL: 13 ]