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

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.

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.

Zpět na hlavní stránku

03.03.2010 21:49:50
mishan	Dik, hodilo se mi to pri simulaci dopravniho systemu co sme dostali za ukol. Bylo to rychlejsi nez to co nas ucil ucitel. Odpovědět

17.11.2009 14:06:30
franta	tohle je moc hezky udelané. Děkuju Odpovědět

Přidat novou zprávu:

Jméno:
E-mail:	Odpověď zaslat na můj email
Web:
Pro kontrolu prosím opište text z obrázku:

Odkazy v textu se automaticky zaktivní a všechny html tagy se pouze zobrazí.
Pokud zpráva obsahuje text "a href" nebo více než 2 odkazy, bude označena jako spam.