Autor Zpráva
Lenin04
Profil *
Zdar, zajímá mě jestly by se nějak dala v php najít nejkratší cesta na šachovnici z bodu A do bodu B a to i když jsou nějaká políčka nepřiztupná. Uměl bych to udělat tak že vyzkoušim všechny možnosti a vyberu tu nejkratší, ale to je dost náročný. Neznáte nějakej jednodušší způsob jak na to?
Alphard
Profil
jakou figurou?
vež? střelac? kůň? dáma?
WertriK
Profil
Tipuju na koně, určitě by to šlo pomocí rekurze nebo tak nějak. My to děláme v pascalu :)
Lenin04
Profil *
Ne vůbec mi nejde o šachy jenom mám pole třeba 10x10 políček, přes něktrá pole se nesmí a já bych zadal z jákého bodu do kterého a ono to zjistí nejlepśí cestu.
souki
Profil
V céčku se na to používaly tuším binární stromy
Peca
Profil
souki
Binární stromy? To nedává smysl...

Lenin04
Nejlepší řešení bude asi řešit to průchodem grafu do šířky.
souki
Profil
Peca
Proč ne? Vytvoříš strom možností kudy můžeš jít. Pak ho projdeš a najdeš si nejkratší cestu. Ale nijak úsporné řešení to není
WertriK
Profil
Binární stromy? To nedává smysl...
Dává ;)
Budeš mít nějaký výchozí bod a z toho budeš moci na další třeba 4 ( to je : jeden uzel a čtyři větve )
takže půjdeš na jeden z tama můžeš jít zase na 4 ale třeba ani jeden není už na "šachovnici" nebo prostě jsou to zakázané pole. Takže se vracíš do toho výchozího a jdeš na druhý dostupný bod zase zkontroluješ jestli na něj vůbec můžeš a půjdeš zasa na další atd.
Takže se ti to pěkně rozvětvý a udělá krásný stromeček :)
Peca
Profil
souki, WertriK
Víš, co je to binární strom? Každý uzel má nejvýše dva podstromy. Trochu nevhodné řešení: buď půjdu nahoru, nebo půjdu jinam.
Timy
Profil
WertriK
Zrovna tohle ale není binární strom, ne? Binární strom by měl mít pouze dva další uzly, pokud si dobře vzpomínám na přednášku z algoritmiky.
souki
Profil
Peca
Jo sorry...Já zs odpovídám na něco jinýho.. Zapomněl jsem, že je víc 2 možnsti
WertriK
Profil
Peca
Vím
Toto téma je uzamčeno. Odpověď nelze zaslat.