Válí se ti projekty v šuplíku? Dostaň je mezi lidi a získej cool tričko a body na profi IT kurzy v soutěži ITnetwork summer 2017!
Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

Šíření do šířky (Vlna)

Algoritmy Bludiště Šíření do šířky (Vlna)

ONEbit hosting Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

Určitě znáte hru Pac-man. Žlutý koláček, požírající bobulky, který je však pronásledován několika bubáky.

Pacman

Zajímá vás, jak docílit toho, aby bubák nalezl danou cestu ke koláčku? Přesně k tomu se používá tento algoritmus, známý také pod názvem "vlna". Slouží k vyhledání cesty mezi překážkami v dvourozměrném poli.

Průběh

Dejme tomu, že se potřebujeme dostat z bodu S do bodu F. Do fronty tedy zapíšeme bod S a dáme mu hodnotu 0.
Fronta : [4;7]

Vyjmeme 1. bod ve frontě (tedy [4;7]) a pokud je v jednom ze 4 směrů volno, uděláme tam hodnotu o jednu větší, než je bod sám (bod S je nula, takže tam napíšeme jedničku). Já jsem si zvolil, že první udělám tu nahoře, pak nalevo, dole a poslední tu vpravo. Políčka, na které jsme položili jedničky, si zapíšeme do fronty.
Fronta : [4;6][3;7][4;­8][5;7]

Opět vyjmeme 1. bod ve frontě ([4;6]) a systémem nahoru, doleva, dolů, doprava napíšeme do políček, které jsou prázdné, číslo, které je zase o jednu větší, než to z fronty (takže 2). Body opět přidám do fronty.
Fronta : [3;7][4;8][5;­7][5;6]

Toto se stále opakuje...
...

...dokud není kolem políčka, které jsme sebrali z fronty, políčko F. Teď je krásně vidět sestupně očíslovaná cesta od políčka F k políčku S. Nyní stačí jen projít se od F k S technikou: jestli je nahoře nebo vlevo nebo dole nebo vpravo číslo o jednu menší, než to, na kterém stojím. Čísla si ukládám obráceně do fronty, abych měl souřadnici políčka F na konci.
Tak a je to, ve frontě máme zapsanou cestu bod po bodu, jak se dostat od bodu S do bodu F.


 

 

Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
12 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Miniatura
Všechny články v sekci
Algoritmy pro bludiště
Miniatura
Následující článek
Generování náhodného bludiště
Aktivity (1)

 

 

Komentáře
Zobrazit starší komentáře (13)

Avatar
OBU
Redaktor
Avatar
OBU:21.11.2013 20:56

boží :D :D ... některý věci se jenom jako složité tváří :P

 
Odpovědět  +1 21.11.2013 20:56
Avatar
anonyimek
Člen
Avatar
anonyimek:24.12.2013 0:11

paradne diki moc :)

 
Odpovědět  +1 24.12.2013 0:11
Avatar
Iwitrag
Člen
Avatar
Iwitrag:18.1.2014 13:00

Tak to je super :D A teď pro non-grid aplikace :D

Odpovědět 18.1.2014 13:00
Učím se ostře vidět.
Avatar
a3228823
Člen
Avatar
a3228823:8.5.2014 10:00

Nejaký algoritmus na riešenie tohto hlavolamu?

CrazyCube - http://www.abelmartin.com/…zy_cube.html
alebo - http://www.superhry.cz/games/775/

Prípadne tip?

 
Odpovědět 8.5.2014 10:00
Avatar
PiskotPiskotovic
Redaktor
Avatar
PiskotPiskotovic:27.7.2014 18:13

Nikdy jsem nevěděl že je to tak lehký :D Úžasný článek, Davide ;)

Odpovědět  +1 27.7.2014 18:13
Error 404 - stránka motto.php nenalezena.
Avatar
Grimor
Člen
Avatar
Grimor:13.9.2014 22:45

Já to asi nechápu. "jestli je nahoře nebo vlevo nebo dole nebo vpravo číslo o jednu menší, než to, na kterém stojím." tak co? Ta věta není dokončena a z kontextu to nemůžu pochopit. Jestli začínáme od S a jdeme na jedničku nahoře, tak potom můžeme jen na dvojku a jsme někde úplně jinde a k tomu zaseknutí.

 
Odpovědět 13.9.2014 22:45
Avatar
koZis
Člen
Avatar
koZis:4.9.2015 15:35

Díky za úvod do problematiky, ušetřilo mi to mnoho šedin!

 
Odpovědět 4.9.2015 15:35
Avatar
rail52
Člen
Avatar
Odpovídá na Grimor
rail52:4.7.2016 17:26

Grimore jelikož si bot cestu značí pozpátku tak vždy dojde tam kam má :)

 
Odpovědět 4.7.2016 17:26
Avatar
hocikto19
Člen
Avatar
hocikto19:4.10.2016 12:54

nie je to klasicky djikstrov algoritmus - vyhladavanie do sirky?

Odpovědět 4.10.2016 12:54
Multum in parvo.
Avatar
Vlado Cukalovsky:4.10.2016 15:44

ano ak pouzijes dijkstru pri neohodnetom grafe(cize urcis kazdej hrane rovnaku hodnotu) tak ano je to rovnake ako vyhladvanie do sirky, ale dijkstra sa pouziva pri ohodnotenom grafe, kde cena cesty k jednemu bodu moze byt upravena, ak sa nasla lacnejsia cena

 
Odpovědět 4.10.2016 15:44
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 23. Zobrazit vše