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: 3, userów: 2, ukrytych: 0
Uzjel, Adriann
Użytkownicy na czacie discord
Wojo (10:48, 16.10.18):
www.youtube.com...h?v=XhmsV_IBles tutaj masz jakieś wyjaśnienia
I am Lord (9:18, 16.10.18):
swędzenie ni występuje po przedwakowaniu kofeiny tylko beta alaniny, na niektórych w tym mnie bardzo negatywnie to wpływa
I am Lord (9:17, 16.10.18):
ale ten filmik jest pocięty i moco zmanipulowany, obejrzyj full 5 minutowy wywiad i tam sprawia wrażenie normalnego tylko lekko nabuzowanego i tyle
MaxGaming (1:49, 16.10.18):
Osoby które nie mają doczynienia z mefedronem itp nie mają pojęcia że tu nie chodzi tylko o te jego drapanie po nosie czy oczy. Chodzi nawet o sposób ekspresji emocji. A raczej nadekspresji w taki bardzo nie typowy sposób. Jak to wyjąsnić? No najlepiej obejrzyjcie ten filmik z adbusterem bo to przykład 1:1
MaxGaming (1:47, 16.10.18):
natomiast na 90% mogę stwierdzić że ćpał
MaxGaming (1:46, 16.10.18):
jedno w tym wszystkim jest pewne - prawdy nie da się udowdnić, ani że był trzeźwy ani że ćpał
MaxGaming (1:46, 16.10.18):
mój kolega który nigdy nie brał amfetaminy a palił codziennie trawę na badaniach na mocz miał amferaminę ktorej nigdy w życiu nie brał i thc nie wykryto
MaxGaming (1:45, 16.10.18):
kolejna sprawa to jakość tych testów... miałem kiedyś robione testy na mocz dzień po paleniu trawy. THC ku mojemu zaskoczeniu nie wyszło wcale
MaxGaming (1:45, 16.10.18):
i czy serio oni robili wgl testy na rcki czy tylko narkotyki tradycyjne?
MaxGaming (1:44, 16.10.18):
co więcej są rcki na które nawet nie ma testów jeszcze
MaxGaming (1:44, 16.10.18):
nie wychodzi za bardzo w moczu. Ludzie donoszą że nawet dzień po nie ma śladu w moczu, po tylu dniach nie ma opcjo na pewno
MaxGaming (1:44, 16.10.18):
z ciekawości sprawdziłem, jesli już weźmiemy testy które obejmują RCki, do tego dodamy że to tylko najpopularniejsze to... najbardziej osławiony 3mmc(aka mefedron) jest do wykrycia w praktyce do 3 dni(testy drugie były robione bodaj po 10 dniach a przed walką to wiadomo...), ale już dzisiaj niemal równie popularny 4cmc(to nie mefedron ale sprzedają go jako mefedron bo działa tak samo a do niedawna był legalny - mefedron od wielu lat nie jest)
MaxGaming (1:24, 16.10.18):
to nie jest do końca takie proste, od zawsze przedtreningówki budzą kontrowersje. Na pewno żadna ilośc kofeiny tak nie robi
MaxGaming (1:23, 16.10.18):
pamiętajmy że kiedyś legalnie w przedtreningówkach stosowano eufedrynę dzisiaj uważaną za narkotyk, a leki z pseudefedryną(praktycznie zerowy efekt psychoaktywny w stsunku do efedryny) są ograniczone w sprzedaży
MaxGaming (1:21, 16.10.18):
nawet jedząc. Nie trzeba wcale walić w nos nawet
MaxGaming (1:21, 16.10.18):
jego oczy są porobione jak nie wiem. Wojo czerwone oczy są po trawie nie po takich rzeczach. Uwierzcie że doskonale wiem jak człowiek się zachowuje po takich rzeczach i jakie ma oczy. Testy na narkotyki wykryją amfę ale jej nawet nikt nie stosuje. Nie wykryje za to np 3mmc, 4mmc, 3cmc, 4cmc, hexenu.... mam wymieniać dalej? Każdy z tych środków działa dokładnie jak na filmiku. Jest tego tyle że nie można sobie wybierać i przebierać. Każdy z nich można zażyć po prostu w płyni
I am Lord (0:09, 16.10.18):
Co ciekawe też pod nosem mnie najbardziej swędziało i tam często próbowałem się drapać
I am Lord (0:08, 16.10.18):
dodajmy do tego adrealinę w kosmicznych ilościach u niego
I am Lord (0:07, 16.10.18):
trzymało mnie dobrą godzinę, myślałem że umrę
I am Lord (0:06, 16.10.18):
wszystko przez to zasrane swędzenie które czujesz pod skóra i drapanie na nie nie pomaga
I am Lord (0:06, 16.10.18):
mi tak ryj też wykręcało jak napalmshota przedawkowałem, a to była dawka tylko dwukrotna
Wojo (22:18, 15.10.18):
A adbuster się po prostu popisywał przed kamerami
Wojo (22:14, 15.10.18):
To, że oczy mi się robią czerwone (zwłaszcza zimą) to nie jest wina narkotyków (ani przedtreningówek)
Wojo (22:13, 15.10.18):
Mnie cały czas podejrzewają o branie narkotyków ludzie, którzy mają o tym nikłe pojęcie
Wojo (22:12, 15.10.18):
Ale co wy w ogóle opowiadacie, w życiu nie widzieliście naćpanego człowieka. Spójrzcie na jego oczy, są one normalne. To, że robi z siebie głupa i jest pobudzony wygraną i przedtreningówkami to jest inny temat
Ignatus (21:06, 15.10.18):
Trenując 20 lat na siłowni testowałem chyba wszystkie przedtreningówki na rynku- żadna nawet w podwójnej dawce nie porabia tak jak Adbustera- naćpany jest jak z podręcznika, zresztą widziałem wszystkie jego filmiki-totalnie inaczej się zachowuje normalnie
MaxGaming (16:03, 15.10.18):
a to czy on wrąbał mefę albo inny rcek do przedtrenigówki i wypił czy walnął w nos to wszystko jedno. Raczej dziwne gdyby walnał w nos bo spożycie oralne cechuje się tym że działanie trwa od kilkudziesięciu minut do kilku godzin a noski działają maksymalnie kilkadziesiąt minut, no może godzinkę zależy co wiadomo
MaxGaming (16:02, 15.10.18):
każdy kto widział kogoś po mefie ten z kilometra rozpozna co z tym typem jest
MaxGaming (16:02, 15.10.18):
nieźle lata ta szczęka, niezłe oczka a zachowanie wgl. Na pewno przedtrenigówka standardowa Na kofeinie na pewno
MaxGaming (16:00, 15.10.18):
ale gdzie duch sportu? Naćpany że ledwo co mówi i cieszy się że zwyciężył
MaxGaming (15:59, 15.10.18):
i jest problem. ale to jest problem że ciężko zakazać wszystkiego bo jest tyle stimów że nie da się nawet tego ogarnąć
MaxGaming (15:59, 15.10.18):
tylko potem zawodnikowi pikawa za którymś razem pada
MaxGaming (15:59, 15.10.18):
w lidze amatorskiej najcześciej to legalne co jest najśmieszniejsze
MaxGaming (15:58, 15.10.18):
znam ludzi którzy walczą amatorsko z takimi przedtrenigowkami zaprawianymi RCekami
MaxGaming (15:58, 15.10.18):
Wojo wiem co mówię, on był naćpany jak meserszmit. Ta przedtreningówka to conajmnej z 3mmc była haha
I am Lord (11:37, 15.10.18):
rafonix chyba go jeszcze tam wyzwał jak go magicala na noszach zawijali
Wojo (9:46, 15.10.18):
i nie byl pod wplywem narkotykow tylko co najwyzej emocji oraz ewentualnie przedtreningówek
Wojo (9:46, 15.10.18):
niepotrzebnie wysmiewal binkowskiego
MaxGaming (23:25, 14.10.18):
ten jego wywiad, ja nie wiem ile on tej nocy skonsumował narkotyków ale powinni zrobić anty doping nawet jeśli to freak fight w stylu reality show a nie sportowe wydarzenie
MaxGaming (23:25, 14.10.18):
Adbuster naćpany tak że to była porażka
MaxGaming (23:04, 14.10.18):
dobrze pociśnięta ta walka z magicalem, 40 sekund i połamany a 4lata spiny
MaxGaming (23:03, 14.10.18):
ale z rafonixa psychopata
MaxGaming (19:30, 11.10.18):
ale nie takie było pytanie
MaxGaming (19:30, 11.10.18):
Da się konfigurować php.ini dla subdomeny? Wrzucene pliku php.ini do katalogu subdomeny nie działa. Obsługa technicna odpowiedziała po prostu że zmiany dokonywane w php.ini przez directpael są przeprowadzane dla całej domeny
MaxGaming (19:13, 11.10.18):
? haha
I am Lord (18:52, 11.10.18):
Sorry ale chodziło mi o zdjęcie z tą kulką papieru
MaxGaming (15:52, 11.10.18):
nie no jeśli chodzi o to w sidebardze no to nieźle wyszłeś, przyznaję
MaxGaming (15:52, 11.10.18):
Johny Depp przy Tobie to zwykły nerdziak haha
ANtY (6:44, 11.10.18):
to w sidebarze? xDD
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.02443 sekund ] [ Liczba zapytań MySQL: 13 ]