Nasze strony: gmclan.org gameonly.pl ps-plus.pl gameswithgold.pl n-switch.pl hmt.pl
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
7 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 7, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
Shoutbox
AnacondaAnaconda (17:02, 21.07.22):
Działa, działa. Aż mi się młodość przypomniała. Kiedyś to były czasy, teraz to nie ma czasów
gnysekgnysek (17:45, 20.07.22):
Czyli wysyłka mejli działa
PieterPieter (14:28, 20.07.22):
cześć tylko sprawdzam, czy nadal konto mi działa po tylu latach
gnysekgnysek (13:45, 20.07.22):
Kto może, niech dołącza - meetup.com/gamemaker-polska
gnysekgnysek (15:09, 18.07.22):
Enigma to jest port GM8 w open source i jak widać niezbyt się rozwija
BorekBorek (8:18, 15.07.22):
Wtyczki Open Source to chyba najlepsze rozwiązanie w takiej sytuacji. Ciekaw jestem co by się stało z GMS jakby był w całości Open Source
gnysekgnysek (13:02, 14.07.22):
Ale! Te wtyczki do reklam mają być open source, to na pewno community je naprawi, jest nadzieja!
gnysekgnysek (10:08, 14.07.22):
Opera ich ciśnie, to robią
BorekBorek (13:58, 13.07.22):
I nie czepiałbym się, gdyby rzeczywiście wszystko w GM było przynajmniej up-to-date, a nie jest... niestety. To nie czas na zajmowanie się takimi pierdołami, gdy ludzie do nich piszą, że ich gry są blokowane z powodu starych funkcji, albo ferelnej wersji stable programu, która rozpieprza cały projekt....
BorekBorek (13:56, 13.07.22):
Ja osobiście nie jestem zwolennikiem takich rzeczy. Tracą czas na funkcje, które i tak nie pozwolą na nic bardziej rozbudowanego... Znowu Yoyo ma podejście tworzenia programu dla dzieci, zamiast ulepszać obecny system sieciowy i porobić fajne tutoriale uczące programować gry sieciowe, to wolą stworzyć klocek, który sam wszystko załatwi... a dobrze wiemy, że i tak wszystkiego nie załatwi...
AdriannAdriann (10:13, 12.07.22):
Ciekawe jak to rozwiną, z tego co kojarzę narazie można mieć i tak max 4 graczy więc nie ma szału. Ale gdyby było z 10-15 to możnaby się już pokusić o zrobienie jakiejś małej strzelanki :d
gnysekgnysek (20:49, 11.07.22):
Problem polega na tym, ze to jest do takiego multi gdzie między rozgrywkami nic nie przenosisz. Do Aliensów by zadziałało
I am LordI am Lord (18:19, 11.07.22):
Gnysek, Almorę przepisz haha
I am LordI am Lord (18:02, 11.07.22):
Jednolinikowy multik wtf 🤣
UzjelUzjel (20:00, 2.07.22):
Zrobiłem test i działa naprawdę spoko, można wydać coś małego na GXa
gnysekgnysek (19:40, 30.06.22):
Polecam newsa o multiplayerze, fajny przykład jak robić sterowanie w grze w betach GM 2022.6+ (i zapewne w GM 2022.8 już normalnie)
ChellChell (11:14, 29.06.22):
słyszałem już o ludziach biorących kredyty na drugą połówkę, ale o subskrybujących GMa na ich kartę pierwsze słyszę
gnysekgnysek (9:14, 28.06.22):
A nie masz jakiegoś 3D secure czy coś, którego może Stripe nie obsługuje?
IgnatusIgnatus (20:14, 26.06.22):
Hmm coś nie tak z kartą (co dziwne bo są mam na niej inne, działające subskrypcje), na żony zadziałało XD
IgnatusIgnatus (11:41, 26.06.22):
Hmm, Jak mam zapłacić za subskrypcję GM? Polska nie jest obsługiwana? Odrzuca kartę i Gpay..
ThreefThreef (19:08, 25.06.22):
Zmienna keyboard_string zawiera wszystkie klawisze jakie wciśnięto. Możesz ją sobie wyzerować przed wpisywaniem keyboard_string = ""
IgnatusIgnatus (18:03, 25.06.22):
Jak w najprostszy sposób zapisać wpisany z klawiatury tekst jako zmienną którą mogę potem z czymś porównać?
IgnatusIgnatus (21:42, 24.06.22):
Tak. Kwestia jest taka że poza GM nie umiem totalnie nic (a GM używałem 5 lat temu). Może ktoś wie jak się do tego zabrać w GM (w sensie tutoriali lub assetów do kupienia)
ChellChell (17:13, 24.06.22):
podejrzewam że dużo prościej byłoby Ci zrobić to po webowo
ChellChell (17:13, 24.06.22):
hej 👋 dobrze rozumiem że chcesz robić prostą aplikację przeglądarkową w GM?
IgnatusIgnatus (21:39, 23.06.22):
Hello! Mam małą misję. Potrzebuje stworzyć apkę na www która będzie otwierała obrazki po wpisaniu ich dwu-członowej nazwy. To będzie trudne w GM? z 5 lat go nie ruszałem ;p
AdriannAdriann (19:34, 21.06.22):
o, naprawili
gnysekgnysek (16:00, 21.06.22):
Help > Report bug Samo sie nie naprawi Ale dzisiejsza beta ma jakiś fix na Spine.
AdriannAdriann (17:50, 20.06.22):
w sumie nawet nie sprawdzałem gdzie się to zgłasza :o
gnysekgnysek (13:54, 20.06.22):
A zgłoszone?
AdriannAdriann (22:08, 14.06.22):
Ech! Spine dalej nie naprawione :<
HunterHunter (13:36, 8.06.22):
Pytanie do starych wyjadaczy jest jeszcze gdzieś dostępna gra MAGI od TeeGee ?
gnysekgnysek (11:25, 8.06.22):
Ja pamiętam, jak była funkcja draw_image_alpha i po 5-6 grafikach FPS spadał.
expexp (18:27, 7.06.22):
i uruchamiała się jedną sekundę
expexp (18:25, 7.06.22):
łezka w oku się kręci jak wspominam czasy kiedy nowa wersja GM wychodziła raz na x lat i było zero problemów
AdriannAdriann (14:32, 4.06.22):
No i gdzie te aktualizacje:| Popsuli i zostawili
gnysekgnysek (12:24, 30.05.22):
A mogli wydać we wtorek, to jeszcze byłby nadal maj...
gnysekgnysek (12:24, 30.05.22):
Obstawiam, że kolejny raz między ostatnią betą a wydaniem stabilnym dodali "jeszcze dwa małe fixy" i wszystko się sypnęło. Ze spine to jest potwierdzony już błąd.
BorekBorek (20:32, 27.05.22):
Oczywiście jest weekend, także wywalona kiełbasa Jedynie można wrócić do poprzedniej wersji i cieszyć się, że ta wersja akurat nie była wymyagana np. dla nowszych wersji Google API Już raz mnie tak załatwili...
BorekBorek (20:29, 27.05.22):
Ostatnie stable jest bardziej rozwalone niż beta. Większość użytkowników nie może odpalić swoich projektów po wczorajszym stable Kocham GM Dobrze, że nie robiłem aktualizacji...
AdriannAdriann (11:23, 27.05.22):
I postacie ze spine zaczęły dziwnie się zachowywać(nie ruszałem w nich nic poza aktualizacjami na bieżąco) A dziwnie znaczy grafiki na różnych layerach często się nie przełączają mimo że powinny
AdriannAdriann (11:22, 27.05.22):
Mam wrażenie że coś się popsuło po ostatnich aktualizacjach gma Bardzo często nie działa mi room_restart() tj raz odpalę grę i działa raz nie
gnysekgnysek (22:58, 11.05.22):
ale tam 39dll chyba też dział, tylko trzeba było dodać brakujące argumenty z numerem bufora (bo GMS nie umiał już ustawiać niezdefiniowanych zmiennych na 0).
SutikkuSutikku (18:34, 11.05.22):
tfu, gms w ogóle, nie gms2
SutikkuSutikku (18:34, 11.05.22):
jak nauczyłem się korzystać z 39dll, to gms2 wyszedł o i tyle z moich nauk
gnysekgnysek (23:29, 9.05.22):
Pisałem już, że przekompilowałem 39dll do x64 i działa w GMS2 ?
gnysekgnysek (21:28, 28.04.22):
Pusty WP - 30-40mb ramu na 1 request.
ChellChell (14:25, 27.04.22):
narzeczona troche bardziej oblatana w temacie mi powiedziala co tam moge poinstalowac i na co zwrocic uwage zeby to zabezpieczyc, ale wciaz smiech na sali
ChellChell (14:24, 27.04.22):
stawialem ostatnio jeden landing na wp dla klienta (wykonany przez jakiegos zewnetrznego kontraktora), w tydzien jakies boty pozmienialy podstrony
Ankieta
» Kiedy wyjdzie GameMaker 3.0?
Q1 2022
Q2 2022
Q3 2022
Q4 2022
2023 albo i później

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

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