algorithm - Numberlink/Flow Game：如何发现 NP 完全问题？

Question

我试图在著名的游戏 Flow 中找到解决问题的方法。http://moh97.us/flow/

谷歌搜索后，我发现这是一个 NP 完全问题。一个好的解决方案是利用启发式和削减。如何轻松发现 NP 完全问题？有时当我阻止时，我看不到明显的解决方案。当NP完全发生这种情况时，最好快速识别它并继续处理下一个问题。

Answer 1

当您有对象爆炸时（例如，其计数基于某个或多个参数呈指数增长的对象），这应该指向您这是一个 NP 完全问题的方向。当您必须检查时，检查太多对象（组合或其他）。通常这些对象是一些初始对象空间的子集或子空间。你应该为此建立一些直觉。但像往常一样，直觉有时会撒谎（我的直觉被这样骗了2-3次）。

然后，一旦您怀疑某个问题是 NP 完全问题，只需谷歌搜索并尝试查找有关相同或类似问题的更多信息。

这至少是我所做的，而且前段时间我一直在解决很多算法问题。

这是一个很好的问题，我很确定它是 NP 完全的，但可以通过例如遗传算法来解决。

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973

正如杜克林所说，没有通用的方法可以做到这一点。

Answer 2

没有简单的通用方法可以做到这一点。它基本上归结为减少一些已知的 NP 完全问题来解决这个问题，或者表明它们是等价的。

因此，了解更多关于著名的 NP 完全问题的信息，并获得更多将问题简化为解决另一个问题和识别等价问题的经验。

免责声明：您只需要注意 NP 完全问题的特殊情况 - 虽然问题的一般情况可能需要指数时间才能解决，但这些特殊情况实际上可能在多项式时间内可解决。