# Summary
TSP 是巡游
[Dijkstra](Dijkstra.md)是某点 A 到某点 B 的最短路径
Floyd是一个距离矩阵，能查到任意两点之间的距离
# Notes
| **算法** | **解决什么问题** | **生活类比** | **时间复杂度** |
| ------------ | ---------- | ------------ | --------- |
| **Dijkstra** | 1个起点到所有终点 | 从家出发到各地的最短路线 | O(V²) |
| **Floyd** | 所有起点到所有终点 | 制作完整的城市距离查询表 | O(V³) |
| **TSP** | 访问所有点一次并返回 | 快递员送完所有货返回 | NP-hard |
| **对比维度** | **Dijkstra 算法** | **TSP（旅行商问题）** |
| ---------- | ------------------------------------------ | -------------------------------------------------------- |
| **问题类型** | 单源最短路径问题 | [[哈密尔顿回路]]优化问题 |
| **实例** | A到D最短路径：A→B→D（2步）| 访问ABCD：A→B→C→D→A（4步，必须全访问）|
| **目标** | 找从源点到所有其他点的最短路径 | 找访问所有城市恰好一次并返回的最短回路 |
| **典型应用** | • GPS导航<br>• 网络路由<br>• 最短路径查询 | • 物流配送<br>• 电路板制造<br>• 旅游[[行程规划]] |
| **访问要求** | 不需要访问所有节点 | 必须访问每个节点恰好一次 |
| **路径形态** | 生成最短路径树（无环）| 形成哈密尔顿回路（闭环）|
| **是否返回起点** | 不需要 | 必须返回 |
| **复杂度类别** | P 类问题 | NP-hard 问题 |
| **时间复杂度** | O(V²) 或 O((V+E)logV) | O(n!) 暴力搜索，O(n²·2ⁿ) 动态规划 |
| **精确解** | 存在高效精确算法 | 大规模问题通常无法获得精确解 |
| **常用算法** | • 原始Dijkstra<br>• 优先队列优化<br>• Fibonacci堆优化 | • 暴力搜索<br>• 动态规划<br>• 分支限界<br>• 遗传算法<br>• 模拟退火<br>• 蚁群算法 |
| **边权要求** | 非负权重 | 可以是任意权重 |
| **适用规模** | 可处理百万级节点 | 精确解通常只能处理几十个节点 |
| **输出结果** | 源点到各点的最短距离和路径 | 一条经过所有点的最优回路 |
| **贪心性质** | 具有贪心选择性质 | 不具有贪心选择性质 |
| **子问题重叠** | 具有最优子结构 | 具有最优子结构但计算复杂 |
这个表格清晰地展示了两个算法在各个维度上的根本差异，特别是问题复杂度的巨大差别使得它们的求解方法和应用场景完全不同。
带固定起终点的旅行商问题变体
**旅行商问题（Traveling Salesman Problem, TSP）就是：**
给定若干城市及两两之间的距离，找一条**最短**的闭合路线（起点 = 终点），要求**恰好**访问每个城市一次。
下面先用一句话回答你的直觉，再分层展开——
> **旅行商问题（Traveling Salesman Problem, TSP）就是：**
> 给定若干城市及两两之间的距离，找一条**最短**的闭合路线（起点 = 终点），要求**恰好**访问每个城市一次。
---
# 1. “一条线连所有点”≠随便连
- **随便连**：任意把点串成折线当然也能把所有点“连起来”，但距离往往冗长。
- **TSP 要求**：
1. **过且只过一次**——不能跳过，也不能重复。
2. **总长度最短**——这才是难点。
3. **回到出发点**（如果是 **Hamilton 路径** 而非 **Hamilton 回路**，可不回到起点）。
---
# 2. Hamilton 路径 / 回路 vs. TSP
|概念|约束|目标|难度|
|---|---|---|---|
|**Hamilton 路径**|过所有点一次，不必回起点|只问“是否存在”|NP-Complete|
|**Hamilton 回路**|过所有点一次，最后回起点|同上|NP-Complete|
|**TSP**|过所有点一次，最后回起点|**长度/成本最小**|NP-Hard (更难)|
> 可以把 TSP 看作“带权 Hamilton 回路”的最优化版。
---
# 3. 为什么 TSP 难？
- **可能路线数**：对 n 个城市，可能的回路有 (n − 1)! / 2 条。
- 10 个城市 ≈ 181 440 条
- 20 个城市 ≈ 1.2 × 10^18 条
- 穷举几乎不现实；TSP 被证明是 **NP-Hard**：目前没人找到对所有实例都能在多项式时间里给出最优解的算法。
---
# 4. 经典算法与套路
|类型|思路|复杂度/误差|备注|
|---|---|---|---|
|**暴力枚举**|全排列|O(n!)|只适合 n≤10|
|**分支限界**|剪掉明显次优分支|仍指数级|实践中比纯暴力快很多|
|**动态规划（Held–Karp）**|状态=子集+终点|O(n²·2ⁿ)|n≤25 常用|
|**整型规划 + 割平面**|把 TSP 写成 ILP，逐步添加割|工程界求最优解的王牌||
|**启发式/近似**|Nearest-Neighbor, 2-Opt, 3-Opt|省时但可能较差|秒级给近似，常见于地理导航|
|**Christofides 算法**|生成 MST + 最小完美匹配|≤1.5×最优（度量空间）|有理论保证|
|**元启发式**|遗传算法、模拟退火、蚁群|经验效果好|无最坏界|
---
# 5. 真实场景
|应用|点是什么？|为什么像 TSP？|
|---|---|---|
|物流派送|货车要送货的门店|最短路线 = 省油、省时|
|芯片布线|触点 / 焊接点|路径越短越节省布线资源|
|3D 打印 / CNC|需加工的轮廓|减少无效移动、提高效率|
|观光旅游|旅游城市/景点|设计最省路费的环游线|
|DNA 测序装配|片段作为“城市”|变体：最短超级串问题|
---
# 6. 小结
- **“一条线连所有点”** 只是 TSP 的外表；
**真正挑战**在于让这条线**总长度最短且点不重复**。
- **Hamilton 路径/回路** 只关心“能不能连”；
**TSP** 关心“怎么连最短”。
- 从暴力枚举到各种近似与元启发式，**没有万能快解**，但有很多“够快又够好”的折中方案。
- 如果你有具体规模/需求（例如 50 个节点、允许 5% 误差、需要 1 秒以内返回），可以再告诉我，我会帮你挑选最合适的算法或库 🚀