Έχουμε την είσοδο για το TSP με σημεία με τις εξής αποστάσεις:
Θέλω να βρω την προσέγγιση για μια TSP-διαδρομή χρησιμοποιώντας το NEAREST NEIGHBOR και το NEAREST INSERTION ξεκινώντας με τον κόμβο .
Από τον παραπάνω πίνακα έχουμε το εξής γράφημα, ή όχι; Χρησιμοποιώντας το 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}
Είναι σωστά αυτά που έχω κάνει;