1
作爲初學者python編程類的最後一項任務的一部分,我被分配了一個旅行銷售人員問題。我決定使用遞歸函數來查找每個排列和目標之間距離的總和,但是,我在引用時遇到了很多問題。在排列順序和主要功能的TSP的不同實例中的陣列似乎指向相同的參考。在python 3.1.1中引用數組的初學者問題
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())
這將不勝感激,如果你可以提供我幫助解決我有的參考問題。謝謝。