As part of the last assignment in a beginner python programing class, I have been assigned a traveling sales man problem. I settled on a recursive function to find each permutation and the sum of the distances between the destinations, however, I am have a lot of problems with references. Arrays in different instances of the Permute and Main functions of TSP seem to be pointing to the same reference.
from math import sqrt
class TSP:
def __init__(self):
self.CartisianCoordinates = [['A',[1,1]], ['B',[2,2]], ['C',[2,1]], ['D',[1,2]], ['E',[3,3]]]
self.Array = []
self.Max = 0
self.StoredList = ['',0]
def Distance(self, i1, i2):
x1 = self.CartisianCoordinates[i1][1][0]
y1 = self.CartisianCoordinates[i1][1][1]
x2 = self.CartisianCoordinates[i2][1][0]
y2 = self.CartisianCoordinates[i2][1][1]
return sqrt(pow((x2 - x1), 2) + pow((y2 - y1), 2))
def Evaluate(self):
temparray = []
Data = []
for i in range(len(self.CartisianCoordinates)):
Data.append([])
for i1 in range(len(self.CartisianCoordinates)):
for i2 in range(len(self.CartisianCoordinates)):
if i1 != i2:
temparray.append(self.Distance(i1, i2))
else:
temparray.append('X')
Data[i1] = temparray
temparray = []
self.Array = Data
self.Max = len(Data)
def Permute(self,varray,index,vcarry,mcarry): #Problem Class
array = varray[:]
carry = vcarry[:]
for i in range(self.Max):
print ('ARRAY:', array)
print (index,i,carry,array[index][i])
if array[index][i] != 'X':
carry[0] += self.CartisianCoordinates[i][0]
carry[1] += array[index][i]
if len(carry) != self.Max:
temparray = array[:]
for j in range(self.Max):temparray[j][i] = 'X'
index = i
mcarry += self.Permute(temparray,index,carry,mcarry)
else:
return mcarry
print ('pass',mcarry)
return mcarry
def Main(self):
out = []
self.Evaluate()
for i in range(self.Max):
array = self.Array[:] #array appears to maintain the same reference after each copy, resulting in an incorrect array being passed to Permute after the first iteration.
print (self.Array[:])
for j in range(self.Max):array[j][i] = 'X'
print('I:', i, array)
out.append(self.Permute(array,i,[str(self.CartisianCoordinates[i][0]),0],[]))
return out
SalesPerson = TSP()
print(SalesPerson.Main())
It would be greatly appreciated if you could provide me with help in solving the reference problems I am having. Thank you.
