Διαδρομή για TSP

[Mathletic]

Γειά σας!!

Έχουμε την είσοδο για το TSP με σημεία με τις εξής αποστάσεις:

distances.PNG (6.84 KiB) Προβλήθηκε 1326 φορές

Θέλω να βρω την προσέγγιση για μια TSP-διαδρομή χρησιμοποιώντας το NEAREST NEIGHBOR και το NEAREST INSERTION ξεκινώντας με τον κόμβο .

Από τον παραπάνω πίνακα έχουμε το εξής γράφημα, ή όχι;

travelling_salesman_problem.png (15.35 KiB) Προβλήθηκε 1326 φορές

Χρησιμοποιώντας το NEAREST NEIGHBOR ξεκινάμε από τον κόμβο και μετά επισκεπτόμαστε σε κάθε βήμα έναν κόμβο, που δεν έχει επισκεφθεί, με την μικρότερη απόσταση, σωστά;
Οπότε, χρησιμοποιώντας αυτόν τον αλγόριθμο παίρνουμε την εξής διαδρομή:
με συνολική απόσταση
ή
με συνολική απόσταση
σωστά;


Ο αλγόριθμος NEAREST INSERTION είναι ο εξής:

Κώδικας: Επιλογή όλων

T <- {1} 
while |T|<n do 
   j <- vertex with minimal d(T,j), j notin T 
   insert j with minimal cost into T 
return T

όπου και τα κόστη, να προσθέσουμε το ανάμεσα στα και είναι

Οπότε χρησιμοποιώντας αυτόν τον αλγόριθμο έχουμε:

Κώδικας: Επιλογή όλων

T = {1} 
j = 6 , d(1,6)=2 
T = {1,6} 
j = 2 , d(1,2)=3 
T = {1,6,2} 
j = 4 , d(1,4)=d(6,4)=4 
T={1,6,2,4} 
j = 3 , d(2,3)=d(4,3)=10  ή    j = 5 , d(4,5)=d(6,5)=10 
T = {1,6,2,4,3}                T = {1,6,2,4,5}
j = 5 , d(4,5)=d(6,5)=10       j = 3 , d(4,3)=d(2,3)=10
T = {1,6,2,4,3,5}              T = {1,6,2,4,5,3} 

με συνολική απόσταση .

Είναι σωστά αυτά που έχω κάνει;