Van valakinek ötlete, milyen algoritmust kell használni egy olyan optimalizálási feladat megoldására, amikor a gráfban szereplő összes ponton át kell haladni egy bizonyos kiinduló ponttól egy bizonyos végcélig, de a lehető legrövidebb úton.
A minimális útkereső algoritmus kilőve, hiszen nem megy át minden ponton.
De az utazó ügynök sem használható, mert annak végcélja a kiindulási pontban van. Nem egy másik városban.
Valahogy ötvözni kellene a kettőt? Nem tudom.
- 4374 megtekintés
Hozzászólások
Az utazo ugynokkel ekvivalens a problemad (szoval np-teljes, jo lassu lesz).
Kiegeszited kepzeletben egy uj ponttal, ami a kiindulo- es vegponttal ossze van kotve, mindkettovel azonos (mondjuk 0) sulyu ellel. Az osszes tobbi csucshoz vagy nem vezet el, vagy hatalmas koltseget adsz neki.
Ha most lefuttatod az utazo ugynokre adott algoritmust, es kitorlod a felvett segedpontot, akkor pont egy olyan Hamilton-utat kapsz, ami a megadott kezdoponttol megy a megadott vegpontig.
Ha nem kell feltetlenul a legjobb megoldas, akkor valoszinuleg megoldhato nagy grafokra is esszeru idon belul. Ha optimalis megoldas kell, akkor vagy a merete ne legyen tul nagy, vagy sok gepre lesz szukseged, vagy sokaig fog futni. Mindenesetre az utazo ugynokre visszavezetheto, szoval eleg, ha annak utanaolvasol.
--
I don't always dress in a T-shirt and jeans. Sometimes people give me awards, and I dress like a penguin instead. - Linus Torvalds
- A hozzászóláshoz be kell jelentkezni
Arra gondolsz, hogy rákényszerítem az utazó ügynök algoritmust, hogy egyből a végpontból a kezdő pontba ugorjon, és természetesen így a végpontban fog újra befejeződni az algoritmus.
Két további kérdésem lenne:
- Nem lenne-e elég közvetlenül a végpontot és a kezdőpontot összekötni egy képzetes 0 súlyú élell? Elvileg ennek elégnek kell lennie, ahhoz hogy a végpontból egyből a kezdőpontba ugorjon.
A második:
Említed, hogy:
Az osszes tobbi csucshoz vagy nem vezet el, vagy hatalmas koltseget adsz neki.
Ezt úgy gondolod, pl. hogy minden valós élhosszt modjuk megnövelek 1000-vel? Így valószínűleg nem akar majd másfelé menni. Nyílván fontos lenne, hogy a minimális utat találja meg egyébként.
Továbbá: nem tudom, biztos-e, hogy az algoritmust ezáltal tényleg rákényszerítjük arra, hogy a végpontból rögtön a kezdőpontba ugorjon.
- A hozzászóláshoz be kell jelentkezni
Nem lenne-e elég közvetlenül a végpontot és a kezdőpontot összekötni egy képzetes 0 súlyú élell?
Gondolkodtam ezen a kérdésen, és rájöttem, hogy a te (Nyosigomboc) javaslatod a jobb. Ugyanis egy olyan extrém helyzetben, amikor a kiinduló pontból csak a végpontba lehet menni, az én javaslatom csődöt mondana.
- A hozzászóláshoz be kell jelentkezni
+1
Minimális súlyú Hamilton-utat keresel.
NP-nehéz, megfelelő skálázással és átfogalmazással NP-teljes.
Utazó ügynök algoritmus nincs, utazó ügynök probléma van. Lehetséges ismert megoldó algoritmus, amely a helyes eredményt adja: teljes esetleszámlálás, amennyiben semmi mást nem tudunk az input gráfról. Okosítani ad-hoc módon lehet, pl. az első Hamilton-út megtalálása után korlátozni annak súlyával a többi ösvényt...
ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne
- A hozzászóláshoz be kell jelentkezni