Dotaz: Obchodní cestující vs. reálný svět

[Josef Kufner]

Ahoj,

mám GPS souřadnice své aktuální polohy, cílové polohy a pak několik dalších míst, která chci v libovolném pořadí navštívit. Jak najít optimální cestu?

Neznám cesty mezi jednotlivými body ani jejich vzdálenosti či dobu za jak dlouho trvá přesun mezi nimi. Jediné, co mám je jejich vzdálenost vzdušnou čarou.

Pokud zadám pevné pořadí bodů, je už celkem lehké předat seznam Google Maps a nechat si cestu nakreslit (příklad). Otázkou však je, jak seřadit místa po cestě tak, aby cesta byla nejlepší, hlavně v případě, kdy chci použít hromadnou dopravu a nikoliv vlastní auto – návaznosti spojů můžou jednoduchým odhadem celkem hodně zamávat.

Odpovědi

[kuka]

Jestli jsem to spravne pochopil tak neznas cenu cesty mezi uzly (dokonce ani jestli existuje). Tzn. takove zadani nema reseni. Vuci jake metrice by tedy cesta mela byt "nejlepsi" - cena, delka, doba? Jak to souvisi s programovanim?

[Josef Kufner]

Otázka je o tom, jak takovou cenu automatizovaně zjistit, abych při zadání několika míst dostal cestu, kudy a v jakém pořadí kam jít.

Metriku jsem neuváděl konkrétní, protože na ní v podstatě až tak nezáleží a prakticky to je kombinace ceny a doby.

[Michy]

Problém obchodního cestujícího nespočívá v obtížnosti nalezení algoritmu, ale v tom, že složitost triviálního algoritmu exponenciálně roste s počtem míst, která je třeba projít. Efektivnější algoritmus zatím nikdo nevymyslel. Více viz. wiki

[petr_p]

Nikoliv algoritmus, ale problém. Tudíž efektivnější algoritmus vymyslet nelze.

[karel]

To se právě neví. Pokud by se někomu podařilo najít efektivnější algoritmus, tak by to znamenalo, že P=NP. A to je zatím nerozhodnutý problém.

[Martin Tůma]

Ale tu metriku musíš definovat, jinak neřešíš problém obchodního cestujícího, ale problém "ženská" - nevim co chci. Nelze zkrátka hledat to nejlepší, když ani nevíš co je dobrý...

[poky74]

To je naprosto perfektní hláška, dávám do bookmarků

[NeoV]

+1

[JS]

Kolik je tech bodu? Pokud jich je min nez 8, proste vyzkousej vsechny moznosti..

Pokud jich je vic, asi by se vyplatilo pouzit geneticky algoritmus, protoze tam se dobre zadavaji a meni kriteria, a neni to slozite naprogramovat (ale zas je to celkem pomale).

[Josef Kufner]

No, koukám, že jsem si s tím titulkem pěkně zadělal

Samotné seřazení bodů je v pohodě, to z wikipedie vemu njaký pěkný algoritmus a je hotovo. To oč mi jde je, jak k té hromádce bodů sehnat hrany. Tedy jde o doplnění grafu o hrany těsně před tím, než na to pustím algoritmus obchodního cestujícího.

Jako takové polovičaté řešení se nabízí použít jako metriku vzdálenosti vzdušnou čarou a takto seřazené body předat plánovači cesty v Google Maps. Ovšem při použití hromadné dopravy to není příliš užitečné.

[NeoV]

no tak si z google maps dotiahni informaciu o vzdialenosti (autom) medzi kazdymi dvoma bodmi a a tieto vystupy vzdialenosti ti budu tvorit hrany....

[JS]

To prave neudelas, protoze volba tech hromadnych prostredku je soucast te optimalizacni ulohy (neni to obchodni cestujici, protoze v tve uloze maji prestupy v uzlech ruznou cenu, a navic zalezi na case, kdy se tam dostanes). Neda se tedy udelat ani to, ze by se vybiraly dve po sobe jdouci hrany (tedy trojice vrcholu) a s nimi se to vyzkouselo, a tato data pouzit jako vstup pro reseni.

Ale ja bych to proste bruteforcoval (popr. muzes zvolit par nahodnych reseni a ta pak mirne perturbovat). Ono se Googlu nic nestane, a clovek s tim nestravi tolik casu.

[AraxoN]

Google Directions API