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
5 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 4, ukrytych: 0
jestemnadal, Uzjel, Gibki Kaktus, I am vader
Użytkownicy na czacie discord
Wojo (11:51, 20.06.18):
jest tak samo koło dupy jak polska koło grecji
gnysek (11:43, 20.06.18):
a udziec to nie jest jakoś koło dupy ?
Penguin (9:00, 20.06.18):
XD
Wojo (22:39, 19.06.18):
jak ból dupy może być pyszny? co najwyżej dupa może być pyszna ale zakładam, że taka nie jest
I am vader (21:55, 19.06.18):
Pysnzy jest bol dupy tych wszystkich cebulaczkow i sebixow ktorych obchodzi pilka nozna.
gnysek (20:23, 19.06.18):
to nie udawaj wielkiego fana, udawaj małego fana
Wojo (19:13, 19.06.18):
Mi to wszystko jedno bo i tak nie lubię piłki nożnej, po co udawać wielkiego fana bo Polska gra w piłke nożną?
MaxGaming (19:11, 19.06.18):
Jak mogliśmy to przegrać
Wojo (14:40, 19.06.18):
na necie można znaleźć ciekawe sekrety o nim ale ja nic nie wiem
Wojo (14:39, 19.06.18):
mnie bardzo ciekawi ten jego coaching. Gdybym miał pieniędzy bez końca to za te pieniądze zapewniłbym sobie niezłą rozrywkę
ANtY (13:36, 19.06.18):
www.pangrodzki....sklep/mars-2488 niech ktoś to kupi i powie mi czy jacek uporał sie z bałaganem
ANtY (13:24, 19.06.18):
www.pangrodzki....-damsko-meskich rozgalezil sie na wszystkie rynku
Chell (12:12, 19.06.18):
75% z teorii e13, już się niczego nie boję
MaxGaming (22:48, 18.06.18):
"to moja ulubiona stronka zaraz po gmclanie"
Wojo (22:48, 18.06.18):
w ogole skoncz typie spam w shoutboxie robic i pisac jakies bzdury zamiast wejsc na gmczat i siedziec w ciszy razem z 16 użytkownikami....
Wojo (22:47, 18.06.18):
nie wole bo tam nie wchodze takie zarty - serio
MaxGaming (22:46, 18.06.18):
Wolisz gmclan? Na prawdę jest on przed tą stronką?
Wojo (22:44, 18.06.18):
a to moja ulubiona stronka zaraz po gmclanie
MaxGaming (22:44, 18.06.18):
position_meeting - co zrobić żeby wykrywał mi maski także tych obiektów które są rysowane w gui? da się to zrobić?
Wojo (22:44, 18.06.18):
15 bez czytania
MaxGaming (22:42, 18.06.18):
nie no mordo żartuje oczywiście żeby nie bylo że jakiś złośliwy jestem
MaxGaming (22:42, 18.06.18):
15 z wliczona przerwą na czytanie komentarzy? xd
Wojo (22:42, 18.06.18):
no i czytam tylko komentarze i nikt sie tam niczym nie przejmuje
Wojo (22:41, 18.06.18):
pudło bo 15
MaxGaming (22:41, 18.06.18):
Wojo nie oszukjmy się, twoja przygoda na phubie pewnie trwa 30 sekund XDD
Wojo (22:40, 18.06.18):
i tak kilka ostatnich kartkowek poprawilem czytajac streszczenia bo bym nie zdał
MaxGaming (22:40, 18.06.18):
To jest raczej propozycja dla tych którzy lubią pracę nad sobą i ogólnie cieżką pracę a nie leniwienie się xd tacy to tylko do szkoły
Wojo (22:40, 18.06.18):
zamiast czytać małego księcia to teraz spędzam czas na robieniu tego co lubię czyli oglądaniu phuba
MaxGaming (22:38, 18.06.18):
Możesz przeczytać je samemu. Ja sam czytam lektury których nie przeczytałem w szkole jak mam wolny czas
Wojo (22:37, 18.06.18):
ale co mi po kasie jakbym nie znał przygód tomka sojera
MaxGaming (22:37, 18.06.18):
Nie rozumiem jak działa to draw_gui. Jak po prostu wstawię w room_editorze jakiś obiekt i dam mu w draw gui draw_self() to rysuje się jako gui, ale nie jest wykrywany w tym miejscu w którym jest ale w tym w którym go postawiłem na start(jakby maska się z nim nie przemieszcza) podczas użycia position_meeting
Wojo (22:37, 18.06.18):
ja gdybym 2 i 3 klasę liceum przesiedział w pracy to mialbym fajny pieniadz na rozruch
MaxGaming (21:55, 18.06.18):
kto po takiej szkole jest gotowy do pracy? Ja osobiście czuję się oszukany i czuję że zmarnowałem te 4 lata. CHociaż moze nie zmarnowałem bo mam już doświadczenie
MaxGaming (21:55, 18.06.18):
nikt nigdy nie wspomniał nawet słowem o jquery a co mówić dalej w szkole
MaxGaming (21:55, 18.06.18):
Uważam że jeśli ktoś nie wie do końca czego chce, albo ma bardzo słabe pojęcie o IT to spoko jest technikum. Jeśli ktoś zna się już na tym czym chce trochę to lepiej usiąść w domu i pouczyć się samemu z książek/kursów/tutoriali
MaxGaming (21:54, 18.06.18):
Robisz technika 4 lata i nikt praktycznie nie bierze go pod uwagę
MaxGaming (21:53, 18.06.18):
jak kończyłem czwartą jeden już jeździł w audi za 150 tyś a drugi w mercedesie za 80tyś nie mówiąc o reszcie hajsu
MaxGaming (21:52, 18.06.18):
Moich dwóch znajomych rzucili technikum na pierwszym roku, posiedzieli 2 lata w domu ucząć się różnych technlogii front-end i back-endowych i założyli firmę kiedy ja byłem w trzeciej klasie
MaxGaming (21:49, 18.06.18):
Ale jak uczyli ich pisać wszystko z pamięci to nie dziwne...
MaxGaming (21:49, 18.06.18):
no kurde kto tak pisze strony internetowe? czego to ma nauczyć? I ciągle uczenei na pamięć. Nikt ode mnie z klasy nie umiał w jakikolwiek sposób debugować kodu. Jak zapomnieli wstawić średnika to wszystko pisali od nowa albo płacz proszę panią nie działa
MaxGaming (21:48, 18.06.18):
Albo na kartce papieru kazali nam pisać stronki całe
MaxGaming (21:46, 18.06.18):
Lub program/stronę dla klienta
MaxGaming (21:45, 18.06.18):
dostawaliśmy pracę na 4h to robiłem ją w godzinę a przez 3h na przykład robiłem kurs C# z jakiś stronek
MaxGaming (21:45, 18.06.18):
A co robiłem na lekcjach? Siedziałem i uczyłem się na własną rekę zupełnie innych rzeczy. Ale przeszkadzało mi to ze muszę tam siedzieć i jeszcze czasami tracić czas na jakieś durne zadania na zaliczenie podczas gdy ja w tym czasie uczyłem się zupełnie czego innego już
MaxGaming (21:44, 18.06.18):
Więc to wcale nie było tak że rozdawali te szóstki
MaxGaming (21:44, 18.06.18):
ostatnio jakąkolwiek szóstkę z zawowdowych w tej szkole miał ktoś 4 lata przede mna
MaxGaming (21:44, 18.06.18):
I były to jedyne 6tki z zawodowych w ciągu ostatnich 4 lat historii tej szkoły
MaxGaming (21:43, 18.06.18):
Ja z zawodowych miałem same 6tki na koniec
MaxGaming (21:43, 18.06.18):
Ale szkoła w Polsce w ogóle nie ma uczyć. Program nauczania E12/E13/E14 sprawia że człowiek wie o każdej z tych dziedziń tylko kompletne podstawy i nie nadaje się nawet zaliczając na 100% wszystkie egzaminy do pracy w jakimkolwiek zawodzie jeśli sam się nie douczy
Wojo (21:42, 18.06.18):
w szkole niskie oceny miałem za zbędną teorię. Sprawdzian z lektury itp. A z wypracowań miałem piąteczki ale co z tego skoro o kant uja mozna to rostrzasc
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.0167 sekund ] [ Liczba zapytań MySQL: 13 ]