算法-TSP旅行商问题-03 - jack

目录

• 问题的核心要素
• 问题的复杂性
• 常见的解法
• 对于大规模问题：
• 穷举
• 动态规划实现 (Held-Karp)

旅行商问题 (Traveling Salesperson Problem, TSP)
旅行商问题是计算机科学和运筹学领域一个非常经典且著名的组合优化问题，
给定一系列城市和每对城市之间的距离，找到一条最短的哈密顿回路，使得旅行商从一个城市出发，经过所有其他城市恰好一次，最后返回到起点。

例如：你带着一批货物，沿着一条线路，经过一系列城市，售卖货物，最后回到家里。

问题的核心要素

城市（Cities）: 问题的节点，你可以把它们看作图中的顶点。
路径/距离（Paths/Distances）: 连接城市之间的边，每条边都有一个权重，通常代表距离、成本或时间。
哈密顿回路（Hamiltonian Cycle）: 一条路径，它从一个城市出发，经过所有其他城市恰好一次，然后回到起点。
目标（Objective）: 在所有可能的哈密顿回路中，找到总距离最短的那一条

问题的复杂性

当城市的数量增加时，问题的难度会呈指数级增长。
假设有 n 个城市。从一个城市出发，你可以在剩下的 n−1 个城市中选择一个，然后从剩下的 n−2 个城市中选择一个，以此类推。因此，总的可能路径数量是 (n−1)!。
当城市数量较大时，暴力枚举所有可能的路径是不可行的，因为计算量会大到无法接受。

常见的解法

由于TSP的复杂性，通常我们会根据问题的规模，选择不同的方法：
对于小规模问题：
暴力穷举法（Brute-force）: 这是最直观的方法，通过生成所有可能的路径，然后计算每条路径的总距离，最后找出最短的那条。这种方法能保证找到最优解，但只适用于城市数量很少的情况（通常小于10）。

动态规划（Dynamic Programming）: 动态规划是一种更高效的精确解法，其中最著名的是Held-Karp算法。它利用子问题的最优解来构建整个问题的最优解，可以求解城市数量在20个左右的问题。

对于大规模问题：

当城市数量超过20个时，精确解法变得不可行。这时，我们会转向近似算法（Approximation Algorithms）或启发式算法（Heuristic Algorithms）。这些算法不能保证找到最优解，但可以在合理的时间内找到一个足够好的近似解。
最近邻算法（Nearest Neighbor Algorithm）: 从一个随机城市出发，每次都前往离当前城市最近的未访问城市，直到所有城市都被访问。这种方法简单快速，但结果可能不是最优的。
遗传算法（Genetic Algorithm）: 一种基于生物进化原理的搜索算法。它通过模拟“基因突变”和“自然选择”来不断优化解，适用于大规模复杂问题。
模拟退火算法（Simulated Annealing）: 借鉴了物理学中固体退火的过程，通过接受一些次优的解来跳出局部最优，从而寻找全局最优解。
蚁群优化算法（Ant Colony Optimization）: 灵感来源于蚂蚁寻找食物的路径行为。蚂蚁通过留下信息素来引导同伴，最终找到最短路径。

穷举

import itertools
import math# 假设城市坐标
# A=(0,0), B=(1,2), C=(3,1), D=(2,-1)
cities = {'A': (0, 0),'B': (1, 2),'C': (3, 1),'D': (2, -1)
}# 计算两点之间的欧几里得距离
def distance(p1, p2):return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)# 暴力穷举法求解 TSP
def solve_tsp_brute_force(cities):# 城市名称列表，固定起点为第一个city_names = list(cities.keys())start_city = city_names[0]other_cities = city_names[1:]min_distance = float('inf')best_path = None# 生成除起点外的所有城市排列for permutation in itertools.permutations(other_cities):current_path = [start_city] + list(permutation) + [start_city]current_distance = 0# 计算当前路径的总距离for i in range(len(current_path) - 1):from_city = current_path[i]to_city = current_path[i+1]current_distance += distance(cities[from_city], cities[to_city])# 检查是否是更短的路径if current_distance < min_distance:min_distance = current_distancebest_path = current_pathreturn min_distance, best_path# 运行代码
min_dist, best_path = solve_tsp_brute_force(cities)
print(f"最短总距离: {min_dist}")
print(f"最优路径: {' -> '.join(best_path)}")

动态规划实现 (Held-Karp)

# 示例：4个城市的距离矩阵
# [0]  [1]  [2]  [3]
distances_matrix = [[0, 10, 15, 20],  # 城市 0 到其他城市[10, 0, 35, 25],  # 城市 1 到其他城市[15, 35, 0, 30],  # 城市 2 到其他城市[20, 25, 30, 0]   # 城市 3 到其他城市
]def solve_tsp_dp(distances):n = len(distances)# 使用字典作为备忘录# 键为 (visited_mask, current_city) 当前在哪里 去过哪里memo = {}# 城市编号	3	 2	 1	 0# 二进制位	b_3	b_2	b_1	b_0# visited_mask = 5 二进制表示[0101] 则代表0,2两个城市已经访问过def tsp_recursive(mask, pos):  # 子问题 在mask情况下 pos出发  访问剩余城市 回到起点 的最小总距离# 递归终止条件：所有城市都被访问if mask == (1 << n) - 1:  # 1111return distances[pos][0]  # pos返回到起点0 的距离# 检查备忘录if (mask, pos) in memo:return memo[(mask, pos)]min_cost = float('inf')# 遍历所有未访问的城市for next_city in range(n):# 检查 next_city 是否未被访问if not (mask & (1 << next_city)):  # 查看mask中next_city位置是否为1# 如果没有访问过，则继续递归new_mask = mask | (1 << next_city)  # mask中next_city位置标记为1new_cost = distances[pos][next_city] + tsp_recursive(new_mask, next_city)min_cost = min(min_cost, new_cost)# 将结果存入备忘录memo[(mask, pos)] = min_costreturn min_costreturn tsp_recursive(1, 0)# 运行代码
min_dist_dp = solve_tsp_dp(distances_matrix)
print(f"动态规划求解的最短总距离: {min_dist_dp}")

import mathdef solve_tsp_dp_with_path(distances):n = len(distances)# 备忘录：存储最小成本memo_cost = {}# 备忘录：存储下一个最佳城市memo_path = {}def tsp_recursive(mask, pos):# 递归终止条件：所有城市都被访问if mask == (1 << n) - 1:return distances[pos][0]# 检查成本备忘录if (mask, pos) in memo_cost:return memo_cost[(mask, pos)]min_cost = float('inf')best_next_city = -1# 遍历所有未访问的城市for next_city in range(n):if not (mask & (1 << next_city)):new_mask = mask | (1 << next_city)current_cost = distances[pos][next_city] + tsp_recursive(new_mask, next_city)if current_cost < min_cost:min_cost = current_costbest_next_city = next_city# 将结果存入两个备忘录memo_cost[(mask, pos)] = min_costmemo_path[(mask, pos)] = best_next_cityreturn min_cost# 1. 计算最小距离min_dist = tsp_recursive(1, 0)# 2. 回溯并构建路径path = [0]  # 从城市 0 开始current_mask = 1  # 初始掩码为 1 (1 << 0)current_pos = 0  # 当前位置为 0while len(path) < n:# 从路径备忘录中获取下一个最佳城市next_city = memo_path[(current_mask, current_pos)]path.append(next_city)# 更新掩码和当前位置，以便下一次循环current_mask |= (1 << next_city)current_pos = next_citypath.append(0)  # 添加起点作为终点，形成闭环return min_dist, path# 示例：4个城市的距离矩阵
distances_matrix = [[0, 10, 15, 20],  # 城市 0 到其他城市[10, 0, 35, 25],  # 城市 1 到其他城市[15, 35, 0, 30],  # 城市 2 到其他城市[20, 25, 30, 0]  # 城市 3 到其他城市
]# 运行代码
min_dist, best_path = solve_tsp_dp_with_path(distances_matrix)
print(f"动态规划求解的最短总距离: {min_dist}")
print(f"最优路径: {' -> '.join(map(str, best_path))}")

动态规划求解的最短总距离: 80
最优路径: 0 -> 1 -> 3 -> 2 -> 0