知识卡片
NP完全先看判定版
严格说,NP 完全性作用于答案为“是/否”的判定问题。
旅行商的最短路线优化版与“是否存在总长不超过阈值的路线”判定版有关,但不能在论证中把两者直接当作同一种形式。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第1章 算法在计算中的作用 · 查看原书依据
To be precise, only decision problems—those with a “yes/no” answer—can be NP-complete. The decision version of the traveling salesperson problem asks whether there exists an order of stops whose distance totals at most a given amount.
参考来源
- 位置:《算法导论(第4版)》第 1 章《算法在计算中的作用》(源文件:`OEBPS/chapter001.xhtml`)
- 结论依据:第1章限定NP完全性用于是/否判定问题,并以旅行商是否存在阈值内路线说明优化版与判定版的形式区别。
- 原始内容:To be precise, only decision problems—those with a “yes/no” answer—can be NP-complete. The decision version of the traveling salesperson problem asks whether there exists an order of stops whose distance totals at most a given amount.