TDDD86 Datastrukturer, algoritmer och programmeringsparadigm

Labb 3 Alternativa TSP-heuristiker

Labb 3: Alternativa TSP-heuristiker

Nedan följer några idéer för att hitta bättre TSP-turer. Dessa metoder kan behöva kompleteras för att klara de extra laborationsuppgifter. Inga av metoderna är garanterade att hitta en optimal tur, men de leder ofta till bra turer i praktiken.

Node interchange local search.

Kör någon heuristik. Upprepa sedan följande:

• Välj ett par städer.
• Byt plats på städerna om det förbättrar turens längd. Om till exempel den första heurisitken returnerar 1-5-6-2-3-4-1, kan du överväga att byta plats på 5 och 3 för att få turen 1-3-6-2-5-4-1.

Edge exchange local search.

Kör någon heuristik. Upprepa sedan följande:

• Välj ett par steg i turen, säg 1-2 och 3-4. (Vi antar att turen är 1-2-3-4-5-6-...)
• Ersätt dem med 1-3 och 2-4 om det förbättrar turens längd.

Här gäller det att vara noggrann eftersom du kommer att behöva ändra riktning på steget mellan nod 3 och nod 2 så att datastrukturen fortsätter att vara en cirkulär länkad lista.

3-opt local search

Kör någon heuristik. Upprepa sedan följande:

• Välj tre steg i turen, säg ab, cd och ef. (där a,b,c,d,e och f är olika noder och a är granne med b, etc)
• Jämför distansen "ab + cd + ef" med de distanser man får om man ändra på kopplingen mellan noderna a,b,c,d,e och f: e.g., "ac+bd+ef", eller "ab+ce+df" eller "ad+eb+cf" eller "fb+cd+ea".
• om en av dem ge en minskning, välj den.

Här också gäller det att vara noggrann eftersom du kommer att behöva ändra riktning på stegen så att datastrukturen fortsätter att vara en cirkulär länkad lista.

Sidansvarig: Ahmed Rezine
Senast uppdaterad: 2024-08-29