旅行商问题分支限界法的代码以及时间复杂度分析

以下是旅行商问题分支限界法的 Python 代码：

import heapq

def tsp(graph, start):
    n = len(graph)
    priorityQueue = [(0, start, [start])]
    minCost = float("inf")
    while priorityQueue:
        (cost, node, path) = heapq.heappop(priorityQueue)
        if len(path) == n:
            minCost = min(minCost, cost + graph[node][start])
        for nextNode in range(n):
            if nextNode not in path:
                nextPath = path + [nextNode]
                nextCost = cost + graph[node][nextNode]
                lowerBound = nextCost + min(graph[nextNode][i] for i in range(n) if i not in nextPath)
                if lowerBound < minCost:
                    heapq.heappush(priorityQueue, (nextCost, nextNode, nextPath))
    return minCost

graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
start = 0
print(tsp(graph, start))

时间复杂度分析：

在最坏情况下，我们需要遍历所有可能的路径，即 $n!$ 种路径，因此时间复杂度为 $O(n! \times n^2 \log n)$。实际上，由于分支限界法可以剪枝，因此实际运行时间通常比最坏情况下要好得多。