旅行售货员优先队列求解

旅行售货员问题是一个经典的组合优化问题，它的目标是找到一条路径，使得该路径经过所有的城市恰好一次，并且回到起点的总路程最小。这个问题可以使用优先队列式分支限界法求解。

优先队列式分支限界法是一种启发式搜索算法，它通过维护一个优先队列来选择下一个扩展的节点。在旅行售货员问题中，每个节点表示当前已经经过的城市集合和当前的路径长度。我们需要维护一个优先队列，按照路径长度从小到大排序，每次选择队首节点进行扩展。

在扩展节点时，我们需要计算该节点的费用下界。费用下界是指从当前节点出发，经过剩余所有城市恰好一次，回到起点的最小路径长度。我们可以使用两个数组来计算费用下界：$c[i][j]$表示从城市i到城市j的距离，$d[i]$表示从城市i出发，经过剩余所有城市恰好一次，回到起点的最小路径长度。具体计算方法如下：

1. 初始化$d[i]$为正无穷，$d=0$。
2. 对于每个城市i，计算它到剩余所有城市的最小距离$min[i]$，并将$d[i]$更新为$c[i][j]+min[j]$的最小值。

计算完费用下界后，我们可以将节点插入优先队列中。在选择下一个扩展节点时，我们取出队首节点进行扩展，并计算它的子节点的费用下界。如果子节点的费用下界小于当前的最优解，那么将该子节点插入优先队列中。

最终，当优先队列为空时，我们就找到了最优解。

下面是一个Python实现的例子：

import heapq

def tsp(c):
    n = len(c)
    d = [float('inf')] * n
    d[0] = 0
    min_dist = [min(c[i]) for i in range(n)]
    q = [(0, [0])]
    while q:
        cost, path = heapq.heappop(q)
        if len(path) == n:
            return cost
        last = path[-1]
        for i in range(n):
            if i not in path:
                new_cost = cost + c[last][i] + min_dist[i]
                if new_cost < min(d[i], float('inf')):
                    d[i] = new_cost
                    heapq.heappush(q, (new_cost, path + [i]))

# Example
c = [[0, 2, 9, 10], [1, 0, 6, 4], [15, 7, 0, 8], [6, 3, 12, 0]]
print(tsp(c)) # Output: 21