使用加权图的旅行推销员问题（Python）

Question

我正在尝试使用加权图来实现旅行商问题。

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

Answer 1

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]