旅行商问题python代码分支限界法

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

import numpy as np

class Node:
    def __init__(self, path, bound, cost):
        self.path = path
        self.bound = bound
        self.cost = cost

def tsp_branch_bound(graph):
    n = graph.shape[0]
    nodes = []
    for i in range(n):
        path = [i]
        bound = bound_func(graph, path)
        cost = 0
        node = Node(path, bound, cost)
        nodes.append(node)
    nodes.sort(key=lambda x: x.bound)

    best_path = None
    best_cost = np.inf

    while nodes:
        node = nodes.pop(0)
        if node.bound >= best_cost:
            continue
        if len(node.path) == n:
            cost = node.cost + graph[node.path[-1], node.path[0]]
            if cost < best_cost:
                best_cost = cost
                best_path = node.path + [node.path[0]]
        else:
            for i in range(n):
                if i not in node.path:
                    path = node.path + [i]
                    bound = bound_func(graph, path)
                    cost = node.cost + graph[path[-2], i]
                    child = Node(path, bound, cost)
                    nodes.append(child)
            nodes.sort(key=lambda x: x.bound)

    return best_path, best_cost

def bound_func(graph, path):
    n = graph.shape[0]
    bound = 0
    last = path[-1]
    for i in range(n):
        if i not in path:
            bound += min(graph[last, i])
    for i in range(len(path) - 1):
        bound += graph[path[i], path[i+1]]
    return bound

# 示例
graph = np.array([[0, 10, 15, 20],
                  [10, 0, 35, 25],
                  [15, 35, 0, 30],
                  [20, 25, 30, 0]])
best_path, best_cost = tsp_branch_bound(graph)
print("最短路径为：", best_path)
print("最短路径长度为：", best_cost)