# 旅行推销员问题

> 旅行商问题（英語：Travelling salesman problem，縮寫：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每對城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。” TSP是旅行购买者问题与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式（可能是指数）级别增长。 问题在1930年…

- ID: m04059
- 分类: technical
- 领域: 算法

## 定义

给定一系列城市和距离，寻找一条访问每个城市一次并返回起点的最短路径。随着城市数量增加，计算路径的复杂度呈指数级爆炸（NP难问题），无法通过穷举法找到最优解。脚手架作用：次优解的智慧。在面对复杂的物流、排程或人生规划时，不要试图寻找"绝对最优解"（那会耗尽你的一生来计算）。接受"启发式算法"找到的"足够好"的次优解，行动优于完美的规划。

## 机制

求访问 n 个城市各一次并回到起点的最短回路，是经典的组合优化 NP 难问题，城市数稍增解空间即阶乘级爆炸。

## 练习

建模为完全图上的最小费用回路；小规模用精确法（分支定界），大规模用近似/启发式（贪心、遗传、模拟退火）。

## 脚手架用法

次优解的智慧。在面对复杂的物流、排程或人生规划时，不要试图寻找"绝对最优解"（那会耗尽你的一生来计算）。接受"启发式算法"找到的"足够好"的次优解，行动优于完美的规划。

[阅读网页](https://thinkingmodels.site/entries/detail/m04059)