Numberlink /流游戏：如何识别NP完全问题？ [英] Numberlink/Flow Game: How to spot NP-Complete problems?

问题描述

我试图找到一种方法来解决这个问题，在著名的游戏流程。 http://moh97.us/flow/

I was trying to find a way to solve the problem in the famous game Flow. http://moh97.us/flow/

谷歌搜索我发现这是一个NP完全问题后。一个好的解决方案将利用启发式和削减。我怎样才能发现一个NP完全问题容易吗？有时，当我挡，我看不到明显的解决方案。当发生这种情况与NP完全性，最好是快速识别并移动到下一个问题。

After googling I find out that this is a NP-complete problem. A good solution would make use of heuristics and cuts. How can I spot a NP-complete problem easily? Sometimes when I block, I can't see the obvious solution. When this happens with an NP-complete, it's better to recognise it quickly and move on to the next problem.

推荐答案

当你有对象的爆炸（说的对象，它们的数量增长 指数基于某些参数或参数），这应该指向 你的方向，这是一个NP完全问题。当你 有权检查，检查对象太多（组合或其他）。 通常，这些对象的子集或一些初步的子空间 对象空间。你应该建立一些直觉这一点。但是，像往常一样， 直觉有时谎言（我一直在骗就这样被我的直觉 在2-3次）。

When you have an explosion of objects (say objects whose count grows exponentially based on some parameter or parameters), this should point you in the direction that it's an NP-complete problem. When you have to inspect, check too many objects (combinatorial or others). Usually these objects are subsets or sub-spaces of some initial object space. You should build some intuition for this. But as usual, the intuition lies sometimes (I've been lied like this by my intuition on 2-3 occasions).

然后，一旦你怀疑一些问题是NP完全问题，只是 谷歌为它，并尝试寻找的更多信息 相同或有关类似问题。

Then once you suspect some problem is NP-complete, just Google for it and try finding more information about the same or about a similar problem.

这是我做的，至少，我已经 解决了不少算法问题 前一段时间。

This is what I do at least and I've been solving quite a few algorithmic problems some time ago.

下面是我pretty的肯定有不错的问题 是NP完全但它可以通过解决 遗传算法的例子。

Here is a nice problem which I am pretty sure is NP-complete but which can be solved through a genetic algorithm for example.

<一个href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973" rel="nofollow">http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973

和作为Dukeling说，有这样做的没有通用的方法。

And as Dukeling said, there's no generic way of doing this.

这篇关于Numberlink /流游戏：如何识别NP完全问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！