旅行商问题中的NP-难与NP-完全混淆 [英] Confusion about NP-hard and NP-Complete in Traveling Salesman problems
问题描述
参考文献：(1)算法、Dasgupta、Papadimitriou、Vazirani练习8.1http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdfhttps://cseweb.ucsd.edu/classes/sp08/cse101/hw/hw6soln.pdf
http://cs170.org/assets/disc/dis10-sol.pdf
推荐答案
我快速浏览了一下您提供的参考资料，我必须承认，在您的教科书(第1版)中有一件事我非常不喜欢：它们解决了NP-完备性，但几乎没有提到决策问题。所提供的NP-Complete问题的定义也与我从教科书中期望的有所偏离。我认为这是一个有意识的决定，目的是让介绍更有吸引力……
我将提供简短的回答，然后对相关概念进行更详细的解释。
简短版本
直观地(和非正式地)，NP如果验证其解决方案很容易，问题就出在NP中。
另一方面，如果问题难以解决，则NP-Hard，或者找到解决方案。
现在，如果一个问题既在NP中，又在NP-Hard中，那么它是NP-完全的。因此，对于NP-完备性，您有两个关键的、直观的性质。易于验证，但很难找到解决方案。尽管它们看起来很相似，但验证和寻找解决方案是两码事。当你使用约化论点时，你是在看你是否能找到解决方案。在这方面，TSP和TSP-OPT都是NP难的，很难找到它们的解决方案。事实上，第三个pdf提供了一个解决方案来练习你的教科书8.1，这直接说明了TSP和TSP-OPT同样很难解。
现在，TSP和TSP-OPT之间的一个主要区别是，前者是(您的教科书中所说的)搜索问题，而后者是优化问题。验证搜索问题的解的概念是有意义的，对于TSP来说，它很容易做到，因此它是NP-完全的。对于优化问题，验证解决方案的概念变得很奇怪，因为我想不出任何方法来验证，除非首先计算最优解决方案的大小，这大致相当于解决问题本身。由于我们不知道一种有效的方法来验证TSP-OPT的解，所以我们不能说它在NP中，因此我们不能说它是NP-完全的。(有关此主题的更多信息，请参阅详细说明。)Tl；dr是指对于TSP-OPT，既难验证又难找到解，而对于TSP来说，它容易验证且难找到解。 减少参数仅在查找解决方案时有用，因此在验证解决方案时需要其他参数来区分它们。
详细信息
您的教科书非常简短的一件事是决策问题是什么。 形式上，NP-完备性、NP-硬度、NP、P等概念是在决策问题而不是优化或搜索问题的背景下发展起来的。
以下是这些不同类型问题之间的差异的快速示例。
决策问题是指其答案为是或否的问题。
TSP决策问题
输入：一个图表G，一个预算b
输出：G最多允许参观体重b吗？(是/否)
这是搜索版本
TSP搜索问题
输入：一个图表G，一个预算b
输出：查找权重最多为b的G的巡视图(如果存在)。
现在是优化版本
断章取义地说，TSP问题可能指的是其中的任何一个。我个人所说的TSP是决策版本。在这里，您的教科书使用TSP作为搜索版本，使用TSP-OPT作为优化版本。 这里的问题是，这些不同的问题严格来说是截然不同的。决策版本只要求存在，而搜索版本要求更多，它需要这样一个解决方案的例子。在实践中，我们往往希望得到实际的解决方案，因此更实用的方法可能会省略提及决策问题。TSP优化问题
输入：图形G
输出：查找权重最小的G的巡视。
现在怎么办？NP-完全问题的定义是用于决策问题，因此从技术上讲，它不直接适用于搜索或优化问题。但因为它背后的理论定义良好且有用，所以仍然使用术语NP-Complete/NP-Hard来搜索/优化问题是很方便的，这样您就可以了解这些问题有多难解决。因此，当有人说旅行商问题是NP完全问题时，形式上它应该是这个问题的决策问题版本。
显然，许多概念可以扩展，使它们也包括搜索问题，这就是您的教科书中所呈现的方式。决策、搜索和优化之间的区别，正是练习8.1和8.2试图在教科书中涵盖的内容。这些练习可能是为了让你对这些不同类型的问题之间的关系感兴趣，以及它们是如何相互关联的。这篇关于旅行商问题中的NP-难与NP-完全混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
