Hi dear members
First of all please apologize my poor english , i’m french …
I’m working on greedies algorithms and, as you guess i need help !
My program is suppose to solve the famous Travelsalesman problem.
I managed to collect some fonctions but i’m having hard time with printing the right answer.
My program is supposed to return all the differents pathes in order to obtain 810 km.
Unfortunately its returns 503 km ;-(
I think my fonctions are okay but this idea of an issue in the buckles still persist.
May I ask you to have a look on my code please ?
Thank you very much for your help and your understanding …
Have a great day,
Williamme
***************My code **********************
town = [1,2,3,4,5]
dist = [[0 , 55 , 303 , 188 , 183],
[55 , 0 , 306 , 176 , 203],
[303, 306 , 0 , 142 , 155],
[188, 176 , 142 , 0 , 123],
[183, 203 , 153 , 123 , 0 ]]
n=len(town)
def greedy_circuit(town, dist, departure):
visited=[False]*n
total_distance=0
actual=departure
for i in range (n-1):
visited[actual] = True
next_town=closer(actual,dist, visited)
total_distance += sum_step(actual, next_town, dist)
actual = next_town
total_distance += sum_step(actual, next_town, dist)
print (' :', total_distance)
def closer(town, dist, visited):
c= None
for i in range(len(visited)):
if not visited[i]:
if c == None or dist[town][i] < dist[town][c]:
c = i
return c
def sum_step (actual,next_town,dist):
distance =dist[actual][next_town]
print ("we go from", town[actual], "to", town[next_town],'with',distance, "km")
return distance
print(greedy_circuit(1,dist,town[0]))