Diskuze: algoritmus - nejkratší cesta

Ostatní jazyky Ostatní programovací jazyky algoritmus - nejkratší cesta

Avatar
Martin Konečný (pavelco1998):

Ahoj,

dokázal by mi někdo popsat (nebo stačí název) algoritmus, pomocí kterého se najde nejkratší cesta, když se potřebuji z bodu A dostat do bodu B?

Pro představu ukážu obrázek, na kterým jsou zobrazeny tři možné cesty, které zaberou 3, 4 a 5 kroků. Kroky jsou zobrazeny čarami a kruhy znamenají jednotlivé body.
Cílem je, aby algoritmus vybral tu nejkratší cestu - na obrázku tu spodní.

Obrázek:
http://www.imagehosting.cz/?…

Nevím, zda je to na podobný princip, ale jaký algoritmus funguje např. ve hrách, kde ovládáte nějaké jednotky (nejčastěji nějaké strategie) a chcete je přesunout na libovolnou část mapy? Algoritmus musí najít nejkratší cestu přes všechny překážky, jako je třeba nějaká voda nebo hory, přes které jednotky nemohou, a musí je tak obejít.

Děkuji

 
Odpovědět 3.4.2015 15:52
Avatar
Josef Kuchař (Pepa489):

Můžeš zkusit algoritmus vlny (http://www.itnetwork.cz/…y-v-bludisti), nebo toto http://www.itnetwork.cz/…-a-do-bodu-b
musíš si ty body poskládat do nějaké "mřížky" ;)

Nahoru Odpovědět  ±0 3.4.2015 15:57
2x piš, jednou debuguj
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Martin Konečný (pavelco1998)
Jan Vargovský:

Jestli to je graf, tak dijkstrův algoritmus.

 
Nahoru Odpovědět  +2 3.4.2015 16:01
Avatar
Martin Dráb
Redaktor
Avatar
Martin Dráb:

Vidím to na tyto možnosti:

  1. pokud by byly hrany (spojnice bodů) vždy jednotkové, stačí algoritmus vlny (je to v podstatě procházení grafu do šířky (BFS)),
  2. pokud hrany nejsou jednotkové, ale mají kladnou hodnotu, Dijstrův algoritmus bude fungovat dobře,
  3. pokud mohou existovat i záporně ohodnocené hrany (ale ne záporné cykly – pak může být nejkratší cesta nekonečně malá), Bellman-Fordův algoritmus by měl najít řešení,
  4. pokud bys chtěl najít nejkratší cesty mezi všemi dvojicemi vrcholů, Floyd-Warshall je na místě.
Nahoru Odpovědět 3.4.2015 19:22
2 + 2 = 5 for extremely large values of 2
Avatar
Martin Konečný (pavelco1998):

Díky všem za odpovědi. Koukám, že to zadání není úplně jasné (za to se omlouvám) - jsem rád, že jste mi naznačili více možných algoritmů.

 
Nahoru Odpovědět 3.4.2015 19:43
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 5 zpráv z 5.