分支限界法求解旅行商问题代码（必须有每行注释）

以下是使用分支限界法求解旅行商问题的Python代码，每行都有注释：

import queue

def tsp_branch_and_bound(graph):
    """
    使用分支限界法求解旅行商问题
    :param graph: 以邻接矩阵表示的完全图
    :return: 最短路径长度
    """
    n = len(graph)
    # 初始化队列和最小路径长度
    q = queue.PriorityQueue()
    min_dist = float('inf')
    # 初始化根节点
    root = Node(graph, 0, [0], 0)
    q.put(root)
    # 不断取出队列中的节点进行扩展
    while not q.empty():
        node = q.get()
        # 如果当前路径已经超过最小路径长度，则剪枝
        if node.lower_bound >= min_dist:
            continue
        # 如果当前节点已经遍历完所有城市，则更新最小路径长度
        if len(node.visited) == n:
            min_dist = node.lower_bound
            continue
        # 对当前节点的所有未遍历城市进行扩展，并加入队列中
        for i in range(n):
            if i not in node.visited:
                new_visited = node.visited + [i]
                new_lower_bound = node.lower_bound + graph[node.current_city][i]
                new_node = Node(graph, i, new_visited, new_lower_bound)
                q.put(new_node)
    return min_dist

class Node:
    """
    节点类，包含当前所在城市、已遍历城市列表和下界
    """
    def __init__(self, graph, current_city, visited, lower_bound):
        self.graph = graph
        self.current_city = current_city
        self.visited = visited
        self.lower_bound = lower_bound
        # 计算下界
        self.calculate_lower_bound()

    def calculate_lower_bound(self):
        """
        计算下界
        """
        n = len(self.graph)
        # 计算已遍历城市到未遍历城市的最小边权和
        visited_set = set(self.visited)
        unvisited_set = set(range(n)) - visited_set
        min_dist = float('inf')
        for i in visited_set:
            for j in unvisited_set:
                if self.graph[i][j] < min_dist:
                    min_dist = self.graph[i][j]
        self.lower_bound += min_dist
        # 计算未遍历城市到已遍历城市的最小边权和
        min_dist = float('inf')
        for j in visited_set:
            for i in unvisited_set:
                if self.graph[i][j] < min_dist:
                    min_dist = self.graph[i][j]
        self.lower_bound += min_dist

该算法使用优先队列来实现节点的扩展，每次取出下界最小的节点进行扩展。节点类中包含当前所在城市、已遍历城市列表和下界。在计算下界时，首先计算已遍历城市到未遍历城市的最小边权和，然后计算未遍历城市到已遍历城市的最小边权和，两者相加即为下界。在扩展节点时，如果当前路径已经超过最小路径长度，则剪枝；如果当前节点已经遍历完所有城市，则更新最小路径长度。最终返回最短路径长度。