import numpy as np

def tsp_backtracking(distances):
    num_cities = len(distances)
    path = [0]  # 起始城市为0
    visited = [False] * num_cities
    visited[0] = True
    min_distance = float('inf')
    shortest_path = None

    def backtrack(curr_city, curr_distance, visited, path):
        nonlocal min_distance, shortest_path
        if len(path) == num_cities:
            # 到达所有城市，更新最短路径
            if curr_distance + distances[curr_city][0] < min_distance:
                min_distance = curr_distance + distances[curr_city][0]
                shortest_path = path + [0]
        else:
            for next_city in range(num_cities):
                if not visited[next_city]:
                    # 选择下一个未访问的城市
                    visited[next_city] = True
                    path.append(next_city)
                    new_distance = curr_distance + distances[curr_city][next_city]
                    # 剪枝条件：当前路径已经大于最短路径，不继续搜索
                    if new_distance < min_distance:
                        backtrack(next_city, new_distance, visited, path)
                    # 回溯
                    visited[next_city] = False
                    path.pop()
    backtrack(0, 0, visited, path)
    return shortest_path
# 示例用法
# distances = np.array([
#     [np.inf, 50, 99, np.inf, 64, np.inf],
#     [50, np.inf, 12, 45, 74, 13],
#     [99, 12, np.inf, 25, np.inf, 61],
#     [np.inf, 45, 25, np.inf, 45, 47],
#     [64, 74, np.inf, 45, np.inf, np.inf],
#     [np.inf, 13, 61, 47, np.inf, np.inf]
# ])
# inf = np.inf
# distances = np.array(
#     [[inf, 69, 48, inf, 41, 78],
#      [69, inf, 48, 53, 91, inf],
#      [48, 48, inf, 19, 86, inf],
#      [inf, 53, 19, inf, 96, 10],
#      [41, 91, 86, 96, inf, inf],
#      [78, inf, inf, 10, inf, inf]]
# )

inf = float('inf')

distances = np.array([
    [inf, 72, inf, inf, 81, 67],
    [72, inf, 26, inf, 61, inf],
    [inf, 26, inf, 53, 97, inf],
    [inf, inf, 53, inf, inf, inf],
    [81, 61, 97, inf, inf, 38],
    [67, inf, inf, inf, 38, inf]
])
path = tsp_backtracking(distances)
if path:
    print(path)
else:
    print('不存在')