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
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: 9 | ocena: 9.00 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
31 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 29, userów: 2, ukrytych: 0
nowy_user, PatrykPlayingPOLSKA

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
nowy_user (10:36, 26.06.17):
Hej, czy był ktoś z was na kursie programowania CodersLab(Ci od baneru)? Zastanawiam się nad tym, ale jestem ciekaw czy warto.
Chell (1:16, 26.06.17):
conieco
ANtY (1:03, 26.06.17):
elo co tam
I am Lord (19:53, 25.06.17):
Za dużo tam różnych optymalizacyjnych działań na bitach i flagach bitowych
I am Lord (19:50, 25.06.17):
Ogółem prawie nic nie rozumiem z tego kodu źródłowego, analiza gry AAA to nie mój poziom :p
I am Lord (19:49, 25.06.17):
Udało mi się skompilować i odpalić kod źródłowy ArxLibertatis (portu gry ArxFatalis) ile z tym roboty było ja pierdziele, nigdy więcej
I am vader (4:04, 25.06.17):
Nie ma to jak usuwanie botów o 4'tej
I am vader (20:22, 24.06.17):
Threef za biały jest na allahuackbar
Ignatus (19:59, 24.06.17):
Threef zapuść wąsa do tej brody bo jest teraz za bardzo allahuakbar
I am Lord (18:01, 24.06.17):
ok mam chwilkę> to wbiję
Threef (17:26, 24.06.17):
Właśnie zaczynam streamować. www.twitch.tv/threef_games
I am Lord (17:02, 24.06.17):
Zbanowałem bota zanim zrobił temat to jest skill a nie jakieś programowanie
I am Lord (15:07, 24.06.17):
Chyba sobie do niego powrócę ale pamiętam że ciężko mi było się w tym połapać wszystkim, niby tego Newton Ponga zrobiłem ale połowę gry odwalił za mnie silnik fizyczny więc za wiele się nie nauczyłem
ANtY (13:21, 24.06.17):
na szczescie, bo to co w unity było to nawet nie był prawdziwy JS
Danieo (11:44, 24.06.17):
C# jest wiodącym językiem w Unity. Tak jak Boo już wymarło to powoli wymiera JS
Adriann (22:49, 23.06.17):
Łoo, pszekonał :3
Nikas (22:03, 23.06.17):
chuj kurwa gem makr zarabiaj dorary
PatrykPlayingPOLSKA (21:33, 23.06.17):
Są wakacje więc postanawiam nie zmarnować tego czasu.
I am vader (20:55, 23.06.17):
C#
I am Lord (19:40, 23.06.17):
C#
PatrykPlayingPOLSKA (19:09, 23.06.17):
Właśnie,może ktoś powiedzieć w czym zacząć pisać w Unity czy w C# czy javascript.W czym lepiej ?
ANtY (17:42, 23.06.17):
w GMie możesz programować bardzo mieszaną składnią, także zależy jak to robisz, w Unity korzystasz z C# (wcześniej dużo ludzi jeszcze z JS korzystało ale unity juz go nie supportuje na rowni z c#)
I am vader (16:54, 23.06.17):
Anty
nowy_user (12:59, 23.06.17):
Rozumiem, a czy jest na forum ktoś kto się "przebranżowił" z GMa na Unity? Sam o tym myślę, ale wiecie, to jest całkiem inny język programowania i domyślam się że wymaga to ogromu pracy...
Wojo (10:35, 23.06.17):
O tym juz pisalem ze możliwości GMa są stanowczo zbyt małe jak na dzisiejsze czasy. GM nie nadazyl za skokiem technologicznyn
nowy_user (8:53, 23.06.17):
Rzeczywiście cena lekko przesadzona. Ja oczywiście rozumiem, że ostatnio powstało sporo komercyjnych gier na GMa i domyślam się też, że włodarze Yoyo aspirują do tego, aby GM był używany przez studia developerskie, i to wszystko fajnie. Ale bądźmy szczerzy, jeśli porównamy możliwości GMa do Unity to jednak nasz kochany program jeszcze musi sporo nadgonić, więc te wysokie ceny - na ten moment- są od czapy.
Danieo (8:17, 23.06.17):
W Unity też. Jedynie musisz być zarejestrowanym developerem Sony (mieć dostęp do Devkita PS4)
Wojo (7:45, 23.06.17):
W Unreal Engine za to nie doplacasz nic. Jedynie jakiś tam procent z zysku ale myślę że to i tak jest uczciwe biorąc pod uwagę możliwości
Ignatus (23:22, 22.06.17):
3000zł z roczną możliwość eksportu na PS4 solidna cena
Uzjel (21:27, 22.06.17):
Master chyba
I am vader (21:03, 22.06.17):
Errr...czym jest Ultimate?
Threef (19:32, 22.06.17):
gnysek na Ultimate, na X1 i PS4. 3 Moduły są teraz na subskrypcję
gnysek (19:16, 22.06.17):
Subskrypcja jest tylko na Ultimate, na resztę nie.
I am Lord (19:01, 22.06.17):
Vader no tutaj na głównej: i.imgur.com/SPrqXPK.png
Threef (17:42, 22.06.17):
Na razie to info że exporty na X1 i PS4 są ważne na 12 miesięcy
I am Lord (17:41, 22.06.17):
Teraz żałuję że kupiłem go :/
I am Lord (17:40, 22.06.17):
Najpierw baitują że nie będzie subskrypcji a teraz ją wprowadzają
Adriann (17:36, 22.06.17):
Cooooooooooooo?!
Threef (17:25, 22.06.17):
Przepraszam co...? GM:S2 ma mieć teraz moduły subskrypcyjnie? Na 12 miesięcy? lol
I am vader (13:39, 22.06.17):
Nie wiem jak dotrzeć do tego działu nawet
I am Lord (11:45, 22.06.17):
im vader moj jest w assorted top down
PatrykPlayingPOLSKA (10:00, 22.06.17):
Mi się wydaje że większość gości to boty ale może być też paru ludzi,trzeba jakoś zachęcić ludzi do zarejestrowania na tym forum,np można jakoś polepszyć tą polską dokumentajcę,coś do niej dodać,na steamworkshop gamemaker można jakoś popisać że jest takie ciekawe coś jak GMC,no sposobów może być wiele.
nowy_user (9:30, 22.06.17):
Chell , aktywnych userów może i dziesięciu, ale np. w tej chwili jest 133 gości! Unbelievable! Swoją drogą , ciekaw jestem dlaczego ludzie się tak ukrywają, zamiast po ludzku się zarejestrować.
Chell (22:56, 21.06.17):
niestety sprzedawanie assetow po zlotowke na ktore zbija sie po 5 osob jest malo oplacalne na forum na ktorym jest 10 aktywnych userow
nowy_user (22:52, 21.06.17):
A może powinniśmy stworzyć własny markietplace tu na gmclanie? Ja widzę same plusy: Po pierwsze - > ceny byłyby w złotówkach, więc więcej ludzi mogłoby sobie na nie pozwolić, Po drugie -> Nie wiem jak wy, ale ja wolałbym wspierać finansowo programistę od nas , ktoś kogo znam z forumowej aktywności zamiast jakiegoś anonimowego geeka z Californi lub Colorado. I po trzecie -> Zmotywowało by to nas wszystkich do twórczości.
I am vader (22:48, 21.06.17):
A który asset jest twój? Przegrzebałem showcase i top rated i nic podpisanego HuderLord nie znalazlem
I am Lord (19:06, 21.06.17):
Aha no super, nic się na głównej nic nie zmieniło pół toku już mój asset tam jest, yoygames zapomniało że ma ten MP że go nie moderują?
I am Lord (19:04, 21.06.17):
Dawno nie zaglądałem tam
nowy_user (12:47, 21.06.17):
Przepraszam , miało być Uzjel.
Ankieta
» Jakiej wersji GameMakera głównie Używasz?
GameMaker: Studio 2
GameMaker: Studio
GameMaker 8.1 i starsze
Żadnej

GMCLAN to serwis o programie Game Maker i nie tylko.
Copyright © 2002-2017. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!

[ Czas generowania strony: 0.01049 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev