+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: Traveller salesman backtracking (/thread-5788.html)
Traveller salesman backtracking - synced - Oct-21-2017
So I have the traveller salesman (backtracking) with a cost on the edges (I consider a full graph with 0 on the main diagonal and a cost in the rest, visiting every node just one time except starting node ), the problem is that my algorithm calculates the cost well ( cost = 13 ) but print 0 - 3 - 3 - 3 - 0 instead of the real solution ( I considered a 4 x 4 matrix starting from node 0 ) I am beginner in python, any help?
def posible(k):
global c
if k != n:
for i in range(0,k-1):
if x[k] == x[i]:
return False
else:
c = a[x[n-1]][x[n]]
if x[k] != x[0]:
return False
for i in range(1,k):
if x[k] == x[i]:
return False
c = c + a[x[i-1]][x[i]]
if k > 0:
if a[x[k-1]][x[k]] == 0:
return False
return True
def compare():
global cmin
global o
global c
if c < cmin:
cmin = c
o = x
def back(k):
for i in range(0,n):
x[k] = i
if posible(k) == True:
if k == n:
compare()
else:
back(k+1)
n = 4
a = [ [0,1,2,3],
[1,0,4,5],
[2,4,0,5],
[3,5,5,0]
]
c = 100
x = [ 0, 0 , 0 , 0 , 0 ]
o = [ 0, 0 , 0 , 0 , 0 ]
cmin = 1000
x[1] = 0
back(1)
o.append(0)
if cmin == 1000:
print('No solution')
else:
for i in range(0,n):
print(o[i],end= ' ')
print('0', end=' ')
print(" cost : " + str(cmin))
RE: Traveller salesman backtracking - sparkz_alot - Oct-22-2017
Sure. Let's start by saying, lose the single letter variables and use descriptive names instead. Python encourages this. In a few months time, with several programs under your belt, even you will forget what they stand for. Next, you have way to many 'globals' and they should be avoided as much as possible. You say the output of '0-3-3-3-0' is incorrect, what result were you expecting? It is often helpful, when you provide a snippet of the entire program, to include some "real" values we can test with as well as the actual output you are getting.
RE: Traveller salesman backtracking - synced - Oct-22-2017
Hi, u are completely right i should use other names for variables. I figured out what i did wrong, i just changed o = x with o = list(x) and now it's working fine, thanks for reply !
RE: Traveller salesman backtracking - sparkz_alot - Oct-22-2017
Glad you were able to arrive at a solution.