Gráf bejárása 2 párhuzamos úton

Gráf bejárása 2 párhuzamos úton
2013-03-24T13:13:58+01:00
2013-03-29T09:55:33+01:00
2022-11-28T16:00:37+01:00
Martinbacsi
Hali!
a feladat a következő: van 13 falu minden faluból minden faluba van egy út különböző menetidővel. (teljes, irányítatlan, súlyozott gráf) "A" faluból kell indítani 2 buszt, ami bejárja az összes falut majd vissszaér "A" faluba, úgy, hogy "A" falun kívül minden falun csak egyszer jelenik meg busz.
Meg kell határozni azt az útvonal-párost, ahol 2 busz közül a hosszabb menetidejű menetideje minimális.
Bruteforce módszerrel próbáltam meg az összes permutációt végigjátszani, de így több nap a program futási ideje.
valakinek valami jobb ötlet ?
Mutasd a teljes hozzászólást!

  • Én azzal kezdeném, hogy a gráfot két független gráffá alakítanám úgy, hogy a két gráfban az összes utak összege a legkisebb legyen.
    (Tehát ezzel a legtávolabbi pontok összekötése megszűnik.)
    Szemléletesen pl. grafikusan ábrázolnám a települések helyét x,y koordinátákkal és első közelítéssel egy egyenessel osztanám szét két halmazra, második közelítéssel egy görbével. A kettő között szerintem %-ban nem lesz nagy különbség.
    A két "halmaz", gráf megtalálásához az elválasztó vonalat az "A falura" és a többi település súlypontjára raknám. Görbe vonal esetén a vonal mellett közvetlenül lévő településeket variálnám.
    Mutasd a teljes hozzászólást!
  • Én arra gondolok, hogy a gráfba beszúrsz egy A' falut, és ehhez minden faluba húzol utat mint ami A-ból is elérhető, ugyanazokkal a súlyokkal. Ekkor egy sima TSP lesz a feladat.
    A körön valahol előfordul A' is. Tehát a körút A ... A' ... A. innen a két kör A... A' és A'...A. Mivel A és A' megegyezik, teljesülnek a feltételek.
    Nemtudom érthető-e mire gondolok.
    Szerk.: Ezt még átgondolom, lehet hogy hülyeséget mondtam.
    Mutasd a teljes hozzászólást!
  • Első ránézésre ez egy tipikus utazóügynök probléma, azaz egy minimális súlyú Hamilton kört kell keresni a gráfban. A jó hír, hogy erre nem létezik polinomiális időben futó optimális algoritmus. Csak közelítő algortimusok léteznek a metrikus esetre, azaz amikor bármely x,y,z pontra teljesül,
    c(x,y) <= c(x,z)+c(y,z), ahol c az élsúly.
    A Jordán, Szeszlér, Recski: Rendszeroptimalizálás c. könyv tárgyalja a témát, régebben én az alapján implementáltam egy algot egy hasonló feladatnál.
    A könyvért lehet hogy kell egy kicsit guglizni...
    Mutasd a teljes hozzászólást!
  • ennek az algoritmizálást átgongolom, mert kiindulásnak jónak tűnik, csak a rajzolós módszer nem jó, mert nem koordináták vannak megadva, hanem távolságok
    Mutasd a teljes hozzászólást!
  • szerintem, ha jól értem a problémát:

    csatlakozok az előttem (csgb 2013.03.25. 00:42) szólóhoz: ez egy tipikus utazóügynök probléma (csak "két útra") és szerintem sincs polinomiális időben futó optimális algoritmusa, azaz "csodát" ne várj, esetleg dinamikus programozás témakörében keresgélhetsz...

    egyébként nem tudom, hogy milyen gépen, milyen bruteforce-szal álltál neki, de,
    ha az egyik csoportba k falut választasz, akkor, ha jól számolom: (12 alatt a k) * (k! + (12 - k)!) lehetőséget kellene egyáltalán számba venned (k = 1..11), hiszen 12-ből k-t (12 alatt a k)-féleképpen vehetsz, ezeket k!-képpen rakhatod sorba, a másik útra esőket meg (12 - k)!-képpen (és egy adott k-st választva nyilván a két sorozatot már egymástól független számolhatod, mindegyikben a legrövidebb útra törekedve), ez alapján, ha jól számoltam, akkor maximum 1.646.119.488 lehetőséget kellene megvizsgálnod, sőt valójában elég k=6-ig menni, hiszen, a két "oldalra" "szimmetrikus" (pld. a k=1-nél a másik körre eső 11-et véve ugyanaz a helyzet, mintha k=11 lenne, és a másik körön 1), ez persze még így is sok lehetőségnek tűnik (kb. 830 millió), de azért ez nem olyan sok (szerintem), hogy napokig fusson (egy mai átlagos gépen),
    esetleg visszalépéses kereséssel (ha már van egy korlátod) csökkenthetsz rajta,
    Mutasd a teljes hozzászólást!
  • Javaslom, hogy rendezd sorba az összes utat növekvő idővel sorrendbe.
    Ebben a sorrendben érdemes elhasználni a szakaszokat.
    Ebből listából keresd meg azt a minimális részhalmazt az elejétől kezdődően, amelyből az egy vagy két kör kialakítható.
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd