我正在尝试使用加权图来实现旅行商问题。
import random
def randomSolution(tsp):
cities = list(range(len(tsp)))
solution = []
for i in range(len(tsp)):
randomCity = cities[random.randint(0, len(cities) - 1)]
solution.append(randomCity)
cities.remove(randomCity)
return solution
def routeLength(tsp, solution):
routeLength = 0
for i in range(len(solution)):
routeLength += tsp[solution[i - 1]][solution[i]]
return routeLength
def getNeighbours(solution):
neighbours = []
for i in range(len(solution)):
for j in range(i + 1, len(solution)):
neighbour = solution.copy()
neighbour[i] = solution[j]
neighbour[j] = solution[i]
neighbours.append(neighbour)
return neighbours
def getBestNeighbour(tsp, neighbours):
bestRouteLength = routeLength(tsp, neighbours[0])
bestNeighbour = neighbours[0]
for neighbour in neighbours:
currentRouteLength = routeLength(tsp, neighbour)
if currentRouteLength < bestRouteLength:
bestRouteLength = currentRouteLength
bestNeighbour = neighbour
return bestNeighbour, bestRouteLength
def hillClimbing(tsp):
currentSolution = randomSolution(tsp)
currentRouteLength = routeLength(tsp, currentSolution)
neighbours = getNeighbours(currentSolution)
bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours)
while bestNeighbourRouteLength < currentRouteLength:
currentSolution = bestNeighbour
currentRouteLength = bestNeighbourRouteLength
neighbours = getNeighbours(currentSolution)
bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(
tsp, neighbours)
return currentSolution, currentRouteLength
tsp = [
('A', 'B', 9),
('A', 'C', 3),
('A', 'D', 2),
('A', 'E', 10),
('B', 'C', 8),
('B', 'D', 7),
('B', 'E', 5),
('C', 'D', 4),
('C', 'E', 11),
('D', 'E', 6)
]
print(hillClimbing(tsp))
这里A、B、C、D、E是节点,tsp中的第三个参数是该节点的权重。 例如:从节点A到B,权重为9。 问题是,当我以成本使用 TSP 时,它工作得很好。
tsp = [
[923, 529, 297, 693, 907],
[542, 693, 401, 280, 785],
[272, 470, 988, 509, 592],
[913, 831, 740, 858, 451]
]
但是对于图表,它会产生如下错误:
routeLength += tsp[solution[i - 1]][solution[i]] IndexError: tuple index out of range
tsp
有 10 个元组,每个元组有 3 个成员。 tsp[solution[i - 1]][solution[i]]
您正在尝试访问第solution[i]
元组的第solution[i - 1]
成员。它可能高于 3。因此它会给出 IndexError: tuple index out of range
错误。
我想应该是
routeLength += tsp[solution[i - 1]][2]