Autor | Zpráva | ||
---|---|---|---|
Lenin04 Profil * |
#1 · Zasláno: 27. 5. 2007, 11:13:38
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 |
#2 · Zasláno: 27. 5. 2007, 11:17:28
jakou figurou?
vež? střelac? kůň? dáma? |
||
WertriK Profil |
#3 · Zasláno: 27. 5. 2007, 11:45:31
Tipuju na koně, určitě by to šlo pomocí rekurze nebo tak nějak. My to děláme v pascalu :)
|
||
Lenin04 Profil * |
#4 · Zasláno: 27. 5. 2007, 11:55:34
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 |
#5 · Zasláno: 27. 5. 2007, 12:01:20
V céčku se na to používaly tuším binární stromy
|
||
Peca Profil |
#6 · Zasláno: 27. 5. 2007, 13:15:14
souki
Binární stromy? To nedává smysl... Lenin04 Nejlepší řešení bude asi řešit to průchodem grafu do šířky. |
||
souki Profil |
#7 · Zasláno: 27. 5. 2007, 13:18:04
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 |
#8 · Zasláno: 27. 5. 2007, 13:21:36
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 |
#9 · Zasláno: 27. 5. 2007, 13:21:56 · Upravil/a: Peca
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 |
#10 · Zasláno: 27. 5. 2007, 13:23:08
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 |
#11 · Zasláno: 27. 5. 2007, 13:30:34
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 |
#12 · Zasláno: 27. 5. 2007, 15:14:21
Peca
Vím |
||
Časová prodleva: 17 let
|
Toto téma je uzamčeno. Odpověď nelze zaslat.
0