Göm menyn

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.

Farthest insertion.

Beter sig som smallest insertion-heuristiken i labben förutom att städerna inte behöver sättas in i samma ordning som i indata. Börja med en tur bestående av de två städer som är längst ifrån varandra. Upprepa följande:

  • Bland alla städer som inte är med i turen, välj den som är längst ifrån städerna som redan är med i turen.
  • Sätt in staden på den position där den orsakar minst ökning av turens längd.
Du kommer att behöva lagra alla oanvända städer i en lämplig datastruktur till de blir insatta i turen. Om din kod blir långsam använder den antagligen ungefär N3 beräkningssteg. Om du är noggrann och klurig kan detta förbättras till N2 beräkningssteg.

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", ekker "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: 2020-09-23