← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 9843.m · 生成模型:Hunyuan

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)时间内解决。