Python回溯法求解旅行商问题，输出最优路线和路线长度

以下是使用 Python 进行回溯法求解旅行商问题，并输出最优路线和路线长度的代码：

import sys

def tsp_bt(graph):
    n = len(graph)
    visited = [False] * n
    best_path = []
    best_dist = sys.maxsize

    # 从当前节点出发，走过的路径长度
    def dfs(curr, total_dist, visited_cnt, path):
        nonlocal best_dist, best_path

        # 如果已经访问过所有节点，更新最优解
        if visited_cnt == n:
            total_dist += graph[curr][0] # 回到起点
            if total_dist < best_dist:
                best_dist = total_dist
                best_path = path + [0] # 加上起点
            return

        # 搜索下一个节点
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                dfs(i, total_dist + graph[curr][i], visited_cnt + 1, path + [i])
                visited[i] = False

    # 从起点开始搜索
    visited[0] = True
    dfs(0, 0, 1, [0])

    return best_path, best_dist

其中，`graph` 是一个二维列表，表示各个点之间的距离。例如，`graph[i][j]` 表示从第 `i` 个点到第 `j` 个点的距离。这个函数返回的是最优路径以及对应的路线长度。