货郎问题 回溯法 python

以下是使用回溯算法解决货郎问题的Python示例代码：

import sys

# 计算两个城市之间的距离
def distance(city1, city2):
    # 这里假设city1和city2是城市的坐标，可以根据实际情况进行修改
    return abs(city1[0] - city2[0]) + abs(city1[1] - city2[1])

# 回溯函数
def tsp_backtracking(cities, current_path, current_cost, best_path, best_cost, visited):
    # 如果已经访问了所有城市，且当前路径的总距离更小，则更新最优路径和最优距离
    if len(current_path) == len(cities):
        if current_cost < best_cost:
            best_path[:] = current_path[:]
            best_cost[0] = current_cost
        return

    # 遍历所有未访问的城市
    for i in range(len(cities)):
        if not visited[i]:
            # 更新当前路径和总距离
            current_path.append(cities[i])
            current_cost += distance(current_path[-2], current_path[-1]) if len(current_path) > 1 else 0
            visited[i] = True

            # 递归调用回溯函数
            tsp_backtracking(cities, current_path, current_cost, best_path, best_cost, visited)

            # 回溯，恢复状态
            visited[i] = False
            current_cost -= distance(current_path[-2], current_path[-1]) if len(current_path) > 1 else 0
            current_path.pop()

# 主函数
def tsp(cities):
    # 初始化最优路径和最优距离
    best_path = []
    best_cost = [sys.maxsize]

    # 初始化当前路径、当前距离和访问状态
    current_path = []
    current_cost = 0
    visited = [False] * len(cities)

    # 从第一个城市开始回溯
    current_path.append(cities[0])
    visited[0] = True

    # 调用回溯函数
    tsp_backtracking(cities, current_path, current_cost, best_path, best_cost, visited)

    return best_path, best_cost[0]

# 示例用法
cities = [(0, 0), (1, 2), (3, 1), (2, 3), (4, 4)]
best_path, best_cost = tsp(cities)
print("Best path:", best_path)
print("Best cost:", best_cost)

这段代码使用回溯算法来解决货郎问题。它通过枚举所有可能的路径，并使用剪枝策略来减少不必要的计算。最终找到最短路径和最短距离。