NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
Martin Konečný (pavelco1998)
Tvůrce
Avatar
Martin Konečný (pavelco1998):3.4.2015 15:52

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
Aktuálně připravuji browser RPG, FB stránka - https://www.facebook.com/AlteiraCZ
Avatar
Josef Kuchař - Pepa489
Tvůrce
Avatar
Josef Kuchař - Pepa489:3.4.2015 15:57

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
3.4.2015 15:57
2x piš, jednou debuguj
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na Martin Konečný (pavelco1998)
Jan Vargovský:3.4.2015 16:01

Jestli to je graf, tak dijkstrův algoritmus.

 
Nahoru Odpovědět
3.4.2015 16:01
Avatar
Martin Dráb
Tvůrce
Avatar
Martin Dráb:3.4.2015 19:22

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)
Tvůrce
Avatar
Martin Konečný (pavelco1998):3.4.2015 19:43

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
Aktuálně připravuji browser RPG, FB stránka - https://www.facebook.com/AlteiraCZ
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.