旅行商问题

简介

我将讨论 P 与 NP、NP 完全问题以及 NP 难问题，定义计算机科学中的启发式方法、哈密顿回路、旅行商问题（TSP）和度量旅行商问题、近似算法，以及最优解与次优解。我还将提及局部极小值、组合爆炸，以及为何精确解变得不可行。最后，我们将看到一个最优解以及一个近似算法。
我还将讨论所选近似算法的局限性、可以改进之处，并提及其他选项，如基于最小生成树（MST）的解决方案、k-优化方法，以及遗传算法等元启发式算法，并分析它们的权衡取舍。
项目代码和分析是与马特乌斯·佩尔施合作开发的，作为巴西 佩洛塔斯联邦大学（UFPel） DSA III 课程的一部分。

判定问题：你希望回答 是或否。
- 例如：“图 G 中是否存在任何哈密顿回路？”（是/否）
搜索问题：你希望找到一个有效解（如果存在）。
- 例如：“在图 G 中找到一个哈密顿回路。”
优化问题：你希望根据某些目标（最小化/最大化）找到 最佳解。
1. “在图 G 中找到最短的哈密顿回路。”（旅行商问题）- 最小化问题
2. “在图 G 中找到 最大团。” - 最大化
3. 团 = 图中形成 完全子图 的 顶点子集

非正式定义：可在 O(TIME(n)) 时间内解决的问题集合。
- 示例：排序属于 P 类，因为它有多项式时间算法。
形式化定义：TIME(t(n)) 是确定性图灵机在 O(t(n)) 时间内可判定的语言集合。
- 注意：“可判定”是针对语言的形式化术语；对于排序等问题，这听起来不太自然，因此目前请重点关注非正式版本。

多项式时间（P）：那些使用确定性图灵机可在多项式时间内判定的问题。
- TIME(O(n^k)) → k 为常数
非确定性多项式时间（NP）：那些其解可由确定性图灵机在多项式时间内验证的判定问题。
- 验证：给定一个候选解（证书），我们 检查其是否有效。
- 例如：“给定一个图和一张证书，检查它是否是一个有效的哈密顿回路。”
NP 完全（NPC）：
1. 属于 NP
2. NP 中的每个问题都可以在多项式时间内归约到它
  - 一个例子是布尔可满足性问题（SAT）
NP 难：至少与 NP 中最难的问题一样难的问题。
1. NP 中的每个问题都可以在多项式时间内归约到它们
2. 不要求属于 NP
  1. 所有 NP 完全问题都是 NP 难的
  2. 但并非所有 NP 难问题都是 NP 完全的
3. NP 难问题不限于
  免责声明：本文内容来自互联网，该文观点不代表本站观点。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，请到页面底部单击反馈，一经查实，本站将立刻删除。