知识卡片
TSP:组合爆炸的排列寻优
TSP(旅行商问题)要求商人从出发城市拜访 N 个城市、每城只访问一次最后回到起点,目标是让总路程最短;它在运输线路、电路板布线、基因测序、机器人控制等场景都有应用。从 A 点出发遍历其余 24 个点,路径数是 24!,即其余节点的全排列,因此 TSP 可转化为排列问题。精确求解中,枚举 (n−1)! 条路线的复杂度是 O(n!),动态规划虽能降低但仍需 O(n²2ⁿ)。随着规模扩大,这类精确算法因组合爆炸失去实际意义。要点:正因精确解不可行,人们转向模拟退火这类启发式算法,接受误差可控、时间可接受的近似解——这是 TSP 与模拟退火相连的根本原因。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第6章 神经网络初步 · 查看原书依据
通过枚举(n-1)!条遍历路线,从中找出具有最短路径(最小成本)的算法,其时间复杂度显然为O(n!)。排列方法的求解通常比子集选择要难得多,如果我们使用动态规划法求解,时间复杂度会有很大下降,但这类精确解法最低也要在O(n22n)时间内解决。
参考来源
- 位置:《机器学习算法原理与编程实践》第6章 神经网络初步(源文件:extracted/机器学习算法原理与编程实践/_epub-src/OEBPS/text00022.html)
- 结论依据:原文给出 TSP 的定义与路径目标,并用 24! 示例说明枚举复杂度 O(n!) 与组合爆炸,引出近似求解思路。
- 原始内容:通过枚举(n-1)!条遍历路线,从中找出具有最短路径(最小成本)的算法,其时间复杂度显然为O(n!)。排列方法的求解通常比子集选择要难得多,如果我们使用动态规划法求解,时间复杂度会有很大下降,但这类精确解法最低也要在O(n22n)时间内解决。