问题定义
经典旅行商问题（Traveling Salesman Problem，TSP）的描述是：一个旅行商要访问 n 个城市，每个城市必须访问且仅访问一次，最后再回到出发城市。已知每两个城市之间的距离，要求找出一条总路程最短的访问路径。
我们也可以把它理解成一个“销售员跑客户”的场景：销售员从公司出发，拜访所有客户城市各一次后返回公司，目标是总行程最短。问题的核心完全一致。
问题抽象与暴力解法
在思考算法之前，我们可以将问题抽象为一个带权完全图：每个城市是一个顶点，两个城市之间有一条边，边的权重就是它们之间的距离。
如果城市数量非常少（例如 4 个），最直观的解法是暴力枚举所有可能的访问顺序（即全排列），计算每种顺序的总路程，然后取最小值。
在 Python 中，我们可以借助 itertools.permutations 轻松实现这一思路。
import itertools
def tsp_bruteforce(dist):
n = len(dist)
cities = range(1, n) # 0 作为出发城市
best = float('inf')
best_path = None
for perm in itertools.permutations(cities):
# 构造完整路径：从 0 出发，按排列顺序访问，最后回到 0
path = (0,) + perm + (0,)
total = 0
for i in range(len(path) - 1):
total += dist[path[i]][path[i + 1]]
if total < best:
best = total
best_path = path
return best, best_path
暴力枚举法的优点是思路简单、绝对准确。但它的致命缺点是时间复杂度为 O(n!)，一旦城市数量 n 超过 10，计算量就会急剧膨胀至无法接受的程度。
动态规划解法详解
当面试官问及“城市多了怎么办”时，答案通常指向基于动态规划的高效解法。
核心状态定义
动态规划解法的核心在于状态的设计。我们需要记录的关键信息是：
- 已经访问过哪些城市 (集合 S)。
- 当前位于哪个城市 (城市 i)。
定义 dp[mask][i]：表示从起点城市 0 出发，已经访问过 mask 所代表的城市集合（包含起点 0），并且最后停留在城市 i 时的最短路程。
这里用状态压缩技术，用一个整数的二进制位（mask）来表示城市集合。例如，对于城市 0,1,2,3，mask = 0b1101 表示已经访问过城市 0、2、3（二进制位从右向左看，第 0、2、3 位为 1）。
状态转移方程
状态转移的思路是：从已知状态 dp[mask][j] 出发，我们可以前往一个尚未访问的城市 k。
新的状态为 new_mask = mask | (1 << k)。
新的路程为 dp[mask][j] + dist[j][k]。
因此，状态转移方程为：
dp[new_mask][k] = min(dp[new_mask][k], dp[mask][j] + dist[j][k])
def tsp_dp(dist):
n = len(dist)
ALL = 1 << n # 所有城市都访问过的状态掩码
INF = float('inf')
# 初始化 DP 表
dp = [[INF] * n for _ in range(ALL)]
dp[1][0] = 0 # 状态：只访问过城市0（mask=1），且停在城市0，路程为0
# 遍历所有状态
for mask in range(ALL):
for i in range(n):
if dp[mask][i] == INF: # 无效状态，跳过
continue
# 尝试从城市 i 前往下一个未访问的城市 j
for j in range(n):
if mask & (1 << j): # 城市 j 已在集合中，跳过
continue
new_mask = mask | (1 << j)
new_cost = dp[mask][i] + dist[i][j]
if new_cost < dp[new_mask][j]:
dp[new_mask][j] = new_cost
# 计算最终答案：所有城市都访问后，从最后一个城市返回起点0
end_mask = ALL - 1
ans = INF
for i in range(n):
if dp[end_mask][i] == INF:
continue
ans = min(ans, dp[end_mask][i] + dist[i][0])
return ans
复杂度分析
该算法的时间复杂度为 O(n² 2ⁿ)，空间复杂度为 O(n 2ⁿ)。虽然仍然是指数级，但相比 O(n!) 已有巨大提升，通常可以处理 n ≤ 20 左右规模的问题。
总结与应用场景
动态规划是解决精确 TSP 问题的经典方法。理解其“状态压缩”和“状态转移”的思想，是应对此类面试题的关键。
在实际工程中，如果城市数量达到上百甚至上千，精确算法将不再可行，此时需要借助启发式算法（如模拟退火、遗传算法）或近似算法来寻找一个较优解，这属于另一个层面的工程优化范畴。
掌握从暴力枚举到动态规划的优化思路，不仅能解决 TSP 问题，其背后的“子集 DP”思想在解决许多组合优化问题时都大有裨益。
发表于 4 天前
|
查看: 17|
回复: 0
