Hoe goed is dit Traveling Salesman algoritme?

[user109731]

Ik heb laatst een algoritme gebruikt voor het oplossen van het Traveling Salesman Problem. Zoals de meesten hier vast wel weten is het de vraag om, gegeven een aantal punten, de kortste route te vinden waarmee je alle punten langsgaat en weer netjes terug komt op de plek waar je begon.

Nu had ik een Python versie gemaakt van het algo dat ik bedacht had, en die werkte iig beter dan brute-forcen. Ik had hier nog wat vragen over en heb toch maar besloten om het aan de mede-tweakers voor te leggen

Eerst mijn redenatie en het algoritme:

• Stel we hebben een graaf met daarin de onderling verbonden punten [a, b, c, d, e, f], en we beginnen in a.
• Als de optimale route begint met abcd, dan weten we dat altijd geldt: pathLength(abcd) <= pathLength(acbd). (de begin- en eindpunten (a en d hier) zijn immers hetzelfde en de tussenpunten (b en c) zijn ook hetzelfde maar dan in een andere volgorde) Als dat niet zo zou zijn zou de kortste route immers wel met acbd beginnen.
• Als we dit omzetten naar een algorithme krijg je zoiets als: we zijn in een punt p, we hebben een lijst steden todo, en we hebben een afgelegde route path. Stel we nemen sublengte 2, dan rekenen we alle pathLength(pxyz) uit, en vergelijken dit met pathLength(pyxz). Waarbij x, y, z in todo, en x != y != z). Als pxyz korter is dan pyxz, dan kunnen we de mogelijkheid pyxz.... laten vervallen, en hoeven we het algo enkel recursief op pxyz.... aan te roepen (z word dus de nieuwe p, todo word todo - x - y - z, en path word path + x + y + z...

Ik ben bang dat dit allemaal erg onduidelijk is, als er vragen zijn hoor ik dat graag

Hierover heb ik de volgende vragen:

1. Is dit een bekend algo, en zoja: hoe heet het? Ik heb Google/Wikipedia al ingezet maar kan niet echt iets vinden wat erop lijkt. Kan ook komen door gebrek aan trefwoorden/kennis...
2. Ik ga er vanuit dat het werkt, want mijn implementatie gaf dezelfde resultaten als de brute-force-methode. Klopt dit of maak ik toch ergens een denkfout?
3. Hoe efficient is dit? Je gooit bij elke stap de helft weg, dus dat is mooi, anderzijds moet je wel alle lengtes van de 'permutaties' uitrekenen (waarbij je wel kunt cachen denk ik). Ik wilde zelf al de complexiteit uitrekenen maar daar kom ik niet ver mee. Bij elke recursieve aanroep is het aantal steden die je nog moet bezoeken met 3 gedaald, en je roept de functie meestal recursief op de helft aan, veel verder kom ik niet

Alvast hartelijk bedankt

[ Voor 0% gewijzigd door user109731 op 07-05-2007 17:13 . Reden: 'algoritme' is toch zonder h in het nederlands... ]

[Verwijderd]

Ja, ik denk dat het laatste voorbeeld met p'en, x'en en y'en een beetje lastig is. Ik snap er niet zoveel van, zou je het verder kunnen uitleggen?

Verder kan ik er niets over zeggen, ik weet niet zoveel (lees: bijna nul) van algoritmes.

[Confusion]

Volgens mij past dit prima in SEA. Het is dan wel wetenschap, maar voor dit soort wetenschap hebben we op GoT gespecialiseerde fora .

W&L - > SEA

[Janoz]

Ik heb er even over nagedacht, en volgens mij klopt je redenatie wel redelijk. Je laat inderdaad wel een beslissingstak wegvallen waarvan je weet dat dat niet de oplossing is.

De winst die je haalt is echter nog steeds constant. In vergelijking met een simpele bruteforce heb je nog steeds dezelfde orde van complexiteit.

De complexiteit is dus ook met jou algoritme nog steeds O(n!)

[ Voor 9% gewijzigd door Janoz op 07-05-2007 17:38 ]

[Grijze Vos]

En hoe garandeer je dat de paar punten die je gaat gebruiken om je paden te vergelijken optimaal zijn over je totale pad? Als je punten A-G hebt bijvoorbeeld, en je komt tot de conclusie dat ABCD beter is dan ACBD, leuk, maar dan kan nog steeds pad ABGFECD korter zijn.

[Soultaker]

Is het niet gewoon een ingewikkelde manier om uit te leggen dat als je in punt d bent, en je hebt punten a, b, c al bezocht, het voor de rest van je tour niet uitmaakt in welke volgorde dat precies is gebeurt? Je geeft verder geen compleet algoritme, dus het is lastig om concreet aan te geven wat nu de verbetering is ten opzichte van brute force.

In pseudocode ziet brute-force er zo uit:

code:

KortstePad(onbezocht, i)
  als onbezocht leeg is:
    resultaat = 0
  anders:
    resultaat = oneindig
    voor elk punt j in onbezocht:
      d = afstand van i naar j + KortstePad(onbezocht zonder j, j)
      als d < resultaat:
        resultaat = d

Merk op dat jouw observatie hier al min of meer in verwerkt zit: de volgorde waarin bezochte de punten bezocht zijn is niet relevant voor het resultaat van KortstePad. Dit algoritme werkt in O(N!); als je de resultaten van KortstePad cachet (met de bijbehorende argumenten) dan is het O(2^NN²), wat aanzienlijk beter is dan het eerste, maar nog steeds ontzettend veel natuurlijk (plus dat je opeens ook O(2^NN) geheugen nodig hebt).

Wat verbetert jouw observatie specifiek aan dit algoritme, of heb je een ander algoritme waarbij je je observatie kunt gebruiken?

[netvor]

Janoz schreef op maandag 07 mei 2007 @ 17:34:
De winst die je haalt is echter nog steeds constant. In vergelijking met een simpele bruteforce heb je nog steeds dezelfde orde van complexiteit.

De complexiteit is dus ook met jou algoritme nog steeds O(n!)

En daar wil ik nog even aan toevoegen dat je niet al te veel moeite moet gaan doen om een sneller algoritme te vinden, TSP is nou eenmaal NP-C. Maar stel dat je wél een polynomisch algoritme weet te vinden, dan kan je heel veel geld verdienen, en een Turing Award of twee :-)

Dus eigenlijk maakt het niet veel uit of je een geavanceerd algoritme gebruikt of een naïeve bruteforce. De kunst van algoritmes ontwerpen ligt AFAIK meer in de hoek van de heuristiek en de suboptimale algoritmen.

[Janoz]

@grijze vos: Het algorithme gaat alle mogelijke combinaties van 4 punten af. Hiervan kan echter volgens de stelling in het eerste punt de helft al afvallen en dit hoeft dus niet meegenomen te worden in de volgende iteratie.

[user109731]

Grijze Vos schreef op maandag 07 mei 2007 @ 18:40:
Als je punten A-G hebt bijvoorbeeld, en je komt tot de conclusie dat ABCD beter is dan ACBD, leuk, maar dan kan nog steeds pad ABGFECD korter zijn.

ACBD en alle volgende recursies daarop zullen afvallen... Het pad ABGFECD komt aan bod wanneer we ABGF met AGBF vergelijken, waarbij de laatste tak zal afvallen dus...

Soultaker schreef op maandag 07 mei 2007 @ 18:48:
In pseudocode ziet brute-force er zo uit:

code:

KortstePad(onbezocht, i)
  als onbezocht leeg is:
    resultaat = 0
  anders:
    resultaat = oneindig
    voor elk punt j in onbezocht:
      d = afstand van i naar j + KortstePad(onbezocht zonder j, j)
      als d < resultaat:
        resultaat = d

Wat verbetert jouw observatie specifiek aan dit algoritme, of heb je een ander algoritme waarbij je je observatie kunt gebruiken?

Ik ben nu bezig met een andere versie maar dit is een snippet uit mn eerste prototype in Python (ranzig, ik weet het, maar het gaat om het idee ). Heb 'm trouwens nog wel iets aangepast en commentaar toegevoegd, maar het principe is hetzelfde.

code:

def getPathLength(path):
    rv = 0
    for i in range(len(path) - 1):
        rv += path[i].getDistanceToAtom(path[i+1])
    return rv

def travel(atoms):
    best = None
    start = atoms[0]
    results = {}

    # alle andere atoms...
    for target in atoms:
        if target == start: continue
        others = atoms + [] # copy
        others.remove(start)
        others.remove(target)
        
        perms = combine(others, others)

        for c in perms:
            a, b = c
            thisLength = getPathLength([start, a, b, target])
            reversed = results.get((b, a, target), None)
            if reversed == None:
                results[(a, b, target)] = thisLength
            else:
                if (reversed > thisLength):
                    del results[(b, a, target)]
                    results[(a, b, target)] = thisLength

    for c, d, e in results:
        leng, path = e.findShortestPath([start, c, d], results[(c, d, e)])

Nogmaals, dit is vrij ranzig en ik weet dat het veel beter kan (wat ik ook gedaan heb, maar die versie is nog niet af dus ). Deze roept zichzelf nog niet recursief aan, maar gebruikt de findShortestPath (de bruteforce) voor de volgende iteraties.

Maar zoals je ziet gooi ik dus de helft weg (de del results[] hierboven), dat doe jij niet in je pseudo-code, daar zit dan wel een verschil in toch? En als het principe gelijk blijft, dan vraag ik me af waarom zelfs deze ranzige, niet-cachende, geheugen intensieve code dan sneller is dan brute-force?

[ Voor 4% gewijzigd door user109731 op 07-05-2007 20:05 ]

[Voutloos]

Jij maakt al keuzes terwijl je maar 3 stappen diep gegaan bent (naar a, b, target), de brute-force berekent de totale paden.

[Janoz]

In het eerste punt geeft JanDM al aan waarom die keuzes gemaakt kunnen worden na 3 stappen. Je kunt zijn algorithme vergelijken met het brute forcen, alleen weet hij al na 3 stappen welke helft nooit meer een kortere route op kunnen leveren. Helaas is het Brute Forcen van TSP een O(n!) operatie dus dit met de helft verminderen heeft eigenlijk nauwlijks invloed op de onhaalbaarheid van het oplossen van grote problemen De complexiteit blijft O(n!). Middels dynamisch programmeren is een betere complexiteit te behalen. Dan is een complexiteit van O(n²* 2ⁿ) te behalen (schaamteloos gejat van wikipedia )

[Voutloos]

Ja, ik snapte je eerdere opmerking mbt de compexiteit ook al, ik zeg alleen waarom dat algoritme 'iets' sneller kan zijn. JanDM zegt ook niet hoeveel sneller zijn algoritme is en hoe groot de problem size was. In de TS staat een set van 6 punten, wat nog niet een echt spannend aantal is.
Sterker nog, 6! < 6²*2⁶ en dus is de set kleiner dan waar de beste algoritmes voor bedoeld zijn.

[Soultaker]

JanDM schreef op maandag 07 mei 2007 @ 19:58:
Maar zoals je ziet gooi ik dus de helft weg (de del results[] hierboven), dat doe jij niet in je pseudo-code, daar zit dan wel een verschil in toch? En als het principe gelijk blijft, dan vraag ik me af waarom zelfs deze ranzige, niet-cachende, geheugen intensieve code dan sneller is dan brute-force?

Dat klopt; doordat je niet cachet bereken je ontzettend veel dubbel, en met je hack halveer je dat dubbele werk weer.

Maar als je nu een wél cachend algoritme zou gebruiken, valt het voordeel weg. Een extra call naar findShortestPath met dezelfde argumenten is namelijk niet kostbaar als je 'm al eerder gecacht hebt. Als je de het brute force algoritme met cache implementeert is het zeker weten sneller dan jouw code, zelfs als je die ook laat cachen.

Wat dat betreft sluit ik me trouwens aan bij Netvor: de worst case valt toch niet te verbeteren, maar er zijn wel algoritmen die in de praktijk redelijk snel convergeren naar een optimale oplossing. Dan kun je daar beter je tijd aan besteden dan aan het verbeteren van een algoritme dat al erg traag is.

[ Voor 15% gewijzigd door Soultaker op 08-05-2007 14:52 ]