Dotaz: Hledání cesty

[poky74]

Ahoj všem :). Právě makám na jednom vcelku řekl bych zajímavém projektu a řeším docela zásadní problém, a to najití nejkratší cestu k cíli.

Situace: Máme čtvercovou mapu, polohu (x,y) objektu a polohu cíle - také x,y.

Posunovat se můžeme čtyřmi směry, nahoru dolu, doleva a doprava.

Na mapě je vcelku dost překážek, překážky v podstatě tvoří cestu.

Asi by to chtělo nějaký algoritmus, ale na to asi nemám hlavu, protože mě zatím nic nenapadá.

Může někdo nahodit směr? Prosím vás nějak jednoduše, s tímhle typem úloh nemám žádné zkušenosti...

Díky

---

---

Odpovědi

[Jendа]

Vlna?

[poky74]

Díky za link, konečně něco co jsem pochopil :D

Avšak, tímto způsobem se vyzkoušejí prakticky všechny možnosti, což je řekl bych dost složité, ale díky za nakopnutí, zatím to vypadá nejpravděpodobněji :)

[podlesh]

Moc jsem to podrobně nezkoumal, ale zřejmě se jedná o Dijkstrův algoritmus. Ten je obecně (tj. pro obecné grafy) optimální, nicméně toto je speciální případ kde je ideální A* algoritmus (viz odkaz dole). Rozdíl spočívá právě v tom, že A* zavádí heuristiku zajišťující že se nejprve vyzkoušejí možnosti vedoucí přímo směrem k cíli (což pravděpodobně stačí).

[hikikomori82]

a*

[vencour]

Jak přesně zní zadání? Co víš hned a co se dozvíš později? Překážky mají nějaké ohodnocení? Co vlastně víš o té mapě? Jak jsou body a uzly spojené?

Když jsem kdysi dostal řešit Jízdní řád na FAVce, tak jsem o orientovaných ohodnocených grafech moc nevěděl (začátek druháku).

[poky74]

Najít na mapě cestu z bodu A do bodu B.

Konkrétně je to dělané tak že se vypočítá cesta, bod A se na mapě přesune o jedno pole a provedou se další akce, takhle to bude v cyklu dokud souřadnice A se nebudou rovnat souřadnicím B.

Z databáze si mohu vytáhnout souřadnice všech objektů na mapě, tedy souřadnice bodů A,B dále souřadnice všech překážek a souřadnice "cest" - rozuměj polí kde nic není, nic nebrání průchodu.

Překážky ohodnocení nemají, jednoduše se na dané pole dá vstoupit (projít jím) nebo nedá.

Znám rozměry, dokážu si z databáze vytáhnout údaje o daném políčku.

Je to čtvercová mapa, jeden čtverec vedle druhého, horizontálně jich je 23 a vertikálně 13.

Je to tedy obdélník který obsahuje 299 políček.

[vencour]

A co ty překážky, jak je chceš vyjádřit? Nějakou penalizací?

Předpokládam, že meze mapy jsou tam proto, aby sis všim, že za roh to nejde.

Fakt Tě nic nenapadá, jak na to? Vzal bych pro začátek Googla a teorii grafů.

[poky74]

Překážky? Pole kde je překážka je jakoby uzamčené, vyplněné, nejde se na ně přesunou, musejí se obejít.

[vencour]

Ok, ale Ty chceš napsat program, ne? Proto musíš lidskou hodnotu a význam nějak přeložit pro počítač.

[poky74]

Ty informace tahám z databáze

[Josef Kufner]

BFS se dá napsat vcelku jednoduše tak, že na jeden select projdeš všechny možnosti vrámci jedné "vlny" (tj. pole o stejné vzdálenosti). Myslím, že v tomhle případě by to mohlo být asi nejrychlejší a přitom jednoduché.

[kouby]

23x13? Nepřemýšlet, vrazit BFS a je to.

[petr_p]

Metrice tohoto prostoru se také říká manhattanská. Zkuste hledat pod tímto názvem.

V podstatě všechny cesty, které se nevrací jsou stejně dlouhé (ať už jedete „úhlopříčkou“ nebo po hraně „obdélníku“).

Obecný algoritmus na hledání nejkratší cesty je Dijkstrův. Jistě není problém převést mapu do reprezentace grafu a pustit na ni Dijkstru. Ale taková reprezentace bude asi velmi hustá a Dijkstra má kvadratickou složitost, což asi nebude výpočetně nejrychlejší řešení.

Pro manhattonskou geometrii určitě bude existovat něco lepšího a asi bude i spousta ověřených implementací, protože to co chcete, je klasický příklad z her. Leč já nic takového neznám.

Pokud nehrozí řešení bludiště (přesné zadání jste nerozvedl), asi by šlo něco napsat přístupem dynamického programování, kde by se dalo dostat lepší než kvadratickou složitost.