问题标签 [np-complete]

今天有一个关于 SO 的问题，作者在一次采访中被提出了一个 NP 完全问题，他显然没有被告知这是一个问题。

问这些问题的目的是什么？当问这样的问题时，面试官期望什么行为？证明？有用的启发式方法？问一个人是否不是每个人都应该知道的众所周知的 NP 完全问题是否合理？（有很多）

周围有很多国际象棋人工智能，显然有些足以击败一些世界上最伟大的棋手。

我听说已经为棋盘游戏Go编写了成功的 AI 进行了许多尝试，但到目前为止，还没有任何超出平均业余水平的构想。

在围棋中任何给定时间以数学方式计算最佳移动的任务是否是一个 NP 完全问题？

我正在寻找一种方法来证明 bicriteria 最短路径问题是 np 完备的。也就是说，给定一个具有长度和权重的图，我需要知道图中是否存在从 s 到 t 的总长度 <= L 且重量 <= W 的路径。

我知道我必须解决一个 NP 完全问题并将其简化为这个问题。我们有以下问题可供选择：3-SAT、独立集、顶点覆盖、汉密尔顿循环和 3 维匹配。

任何可能可行的想法？

谢谢

解决特定 NP 完全问题的最快算法是什么？例如，旅行推销员的简单实现是 O(n!)，但使用动态规划可以在 O(n^2 * 2^n) 中完成。是否有任何可能“更简单”的 NP-Complete 问题具有更好的运行时间？

我对确切的解决方案而不是近似值感到好奇。

NP、NP-Complete和NP-Hard之间有什么区别？

我知道网上有很多资源。我想阅读您的解释，原因是它们可能与外面的不同，或者有些我不知道。

我认为，当证明一个问题 P 是 NP-Complete 时，我们应该将一个已知的 NPC 问题简化为 P。但是，看看独立集问题的解决方案，它似乎不是这样。

为了证明独立集是 NP 完全的，你需要一个图 G，找到它的逆 G'，然后计算 CLIQUE(G')。但是，这是相反的：它处理一个问题 PI 不知道它是否是 NPC，然后将其简化为已知 NPC 问题。

这是解决方案的一个示例。

我在这里想念什么？这难道不是错的，因为它是反过来做的吗？

我知道那里有一些调度问题是 NP-hard/NP-complete ......但是，没有一个是这样说明的，以表明这种情况也是 NP。

如果您有一组任务受限于startAfter、startBy和duration都试图使用单个资源......您能否解决计划或确定如果不进行详尽搜索就无法解决？

如果答案是“对不起，朋友，但这是 NP-complete”，那么最好的启发式方法是什么？有没有办法减少 a) 解决计划和 b) 确定无法解决的时间日程。

我已经（在序言中）通过实现“最小窗口优先”启发式的递归实现了基本的冲突解决目标。这实际上很快就能找到解决方案，但在寻找无效时间表方面却异常缓慢。有没有办法克服这个问题？

耶复合问题！

抱歉，问题标题不是很清楚，这是一个具有挑战性的问题，无需提供更具体的示例。考虑以下场景：

我有一些朋友的生日即将到来（d1..dn），我设法想出了一些我想以成本购买他们的礼物（c1..cn）。不幸的是，我每天只能存下固定数量的钱（m）来购买这些礼物。我想问的问题是：

什么是每件礼物的理想储蓄分配（mi，其中 mi 从 1..n == m 的总和）以最小化我朋友的生日和我存够钱的日期之间的总偏差购买该礼物。

我正在寻找的不是这个问题的解决方案，就是我可以用来确定性地回答这个问题的已解决问题的映射。感谢您的思考，如果我能提供任何额外的说明，请告诉我！

这个问题出现在现实世界中，但我已将其翻译成更通用的“教科书式”表述。我怀疑它是 NP，但我特别想知道它是否有名字或众所周知，因为我认为我不能成为第一个遇到它的人。;-)

想象一下有 N 位客人的聚餐派对。每位客人可以将他/她的“招牌菜”带到聚会上，或者什么都不带。每个客人都喜欢或讨厌其他客人可能带来的每一种菜肴（这是提前知道的，因为他们都是老朋友！），但他们都喜欢自己的菜肴。

是否有一种确定性算法不需要指数时间来找到满足所有客人都会找到至少一种他们喜欢的菜肴的约束的最小菜肴集？我说“最小的”，但实际上可能有多种解决方案，如果可能的话，我想知道它们。

或者，以更抽象的方式，想象一个方阵，其中所有元素都是 0 或 1，所有对角线元素都是 1。 什么是最小的行集，使得每个行的总和（或二进制 OR）设置没有零？（行是菜，列是客人，1 表示客人喜欢一道菜，对角元素为 1，因为每个人都喜欢自己的菜。）

这可以推广到非方阵，或者通过删除对角线=1 规则（尽管后者保证总是至少有一个解决方案）。但我暂时不关心这些情况......

我已经有一个程序可以通过详尽的搜索来解决它，并且对于 20 左右的 N 来说足够快，但它需要指数级的时间。我在想我可能需要重新使用随机算法来为更大的 N 值找到足够好的解决方案。

添加

哇，谢谢你的快速回答！“设置封面”，这就是我要找的名字。:)

首先，让我说这不是家庭作业（我是一名 A-Level 学生，这与我们解决的问题没有什么关系（这更难）），而是我试图解决的更多问题改进我的编程逻辑。

我想到了一个场景，其中有一个随机整数数组，例如 10 个整数。用户将输入一个他想要计数的数字，算法将尝试计算出需要哪些数字来计算总和。例如，如果我想从这个整数数组中求和 44：

输出将是：

或类似的规定。我希望我说清楚。作为额外的奖励，我想让算法选择尽可能少的数字来获得所需的总和，或者如果无法使用提供的数字得出总和，则给出错误。

我考虑过使用递归并遍历数组，一遍又一遍地添加数字，直到总和达到或过去。但是我无法理解的是，如果算法超过了总和并且需要有选择地从数组中选择哪些数字，该怎么办。

我不是在寻找完整的代码或完整的算法，我只是希望您对我应该如何进行此操作提出意见，并可能分享一些提示或其他内容。我今晚可能会开始工作。:P

正如我所说，不是家庭作业。只是我想做一些更高级的事情。

感谢您提供的任何帮助。:)