分支限界法求解旅行商问题代码（必须有每行注释），可以直接运行的

以下是Python实现旅行商问题分支限界法的代码，每行都有注释说明：

import heapq
import math

# 定义旅行商问题类
class TSP:
    # 初始化函数，传入城市数量和距离矩阵
    def __init__(self, n, d):
        self.n = n  # 城市数量
        self.d = d  # 距离矩阵
        self.best_path = None  # 最优路径
        self.best_cost = math.inf  # 最优路径长度
        self.visited = [False] * n  # 标记城市是否被访问过

    # 分支限界法求解旅行商问题
    def solve(self):
        # 将起点加入堆中，距离为0
        heap = [(0, 0, [0])]
        while heap:
            # 取出堆顶元素
            cost, city, path = heapq.heappop(heap)
            # 如果当前路径已经超过最优路径，直接返回
            if cost >= self.best_cost:
                continue
            # 如果已经遍历完所有城市，更新最优路径
            if len(path) == self.n:
                cost += self.d[path[-1]][0]  # 加上回到起点的距离
                if cost < self.best_cost:
                    self.best_cost = cost
                    self.best_path = path
                continue
            # 遍历当前城市的所有邻居
            for i in range(self.n):
                if not self.visited[i]:
                    # 计算到邻居城市的距离
                    new_cost = cost + self.d[city][i]
                    # 将新路径加入堆中
                    new_path = path + [i]
                    heapq.heappush(heap, (new_cost, i, new_path))
            # 标记当前城市为已访问
            self.visited[city] = True

# 测试代码
if __name__ == '__main__':
    n = 4
    d = [[0, 2, 9, 10],
         [1, 0, 6, 4],
         [15, 7, 0, 8],
         [6, 3, 12, 0]]
    tsp = TSP(n, d)
    tsp.solve()
    print(tsp.best_path, tsp.best_cost)

在上述代码中，我们定义了一个 `TSP` 类，表示旅行商问题。在初始化函数中，我们传入城市数量和距离矩阵。`best_path` 和 `best_cost` 分别表示最优路径和最优路径长度，初始值分别为 `None` 和正无穷。`visited` 列表用于标记城市是否被访问过。

`solve` 函数是分支限界法求解旅行商问题的核心函数。我们使用一个堆来存储当前需要扩展的节点，每个节点包括当前路径长度、当前节点、当前路径。每次从堆中取出路径长度最小的节点进行扩展，如果当前路径已经超过最优路径长度，直接返回。如果已经遍历完所有城市，更新最优路径。否则遍历当前城市的所有邻居，计算到邻居城市的距离，并将新路径加入堆中。最后标记当前城市为已访问。

在测试代码中，我们定义了一个 $4$ 个城市的旅行商问题，并求解最优路径和最优路径长度。