知识卡片

普通读书笔记卡 · 3591

NP完全先看判定版

理解等级:高级

严格说,NP 完全性作用于答案为“是/否”的判定问题。

旅行商的最短路线优化版与“是否存在总长不超过阈值的路线”判定版有关,但不能在论证中把两者直接当作同一种形式。

这张卡片看不懂?

已有反馈 · 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.