0

在最终幻想 XIII-3 游戏中，玩家会遇到几个谜题。引入的第一个谜题称为Tile Trial，它向玩家展示了一个瓷砖网格，其中一些上面有水晶。目标是取回所有水晶并到达出口，同时踩到每个瓷砖不超过一次。

http://arxiv.org/pdf/1203.1633v1.pdf的作者表示，这个问题是 NP-Hard，因为可以将特定情况简化为哈密顿循环。我发现这是一个幼稚的假设，因为他开发了一个特定的谜题，虽然符合游戏规则，但恰好涉及哈密顿循环。

看一般情况：我们可以将拼图的每个图块建模为图中的一个顶点。如果两个瓦片相邻，则一个顶点与另一个顶点有一条边。问题在于找到从起始图块到结束图块的路径，同时遍历所有具有晶体的顶点并且不多次访问任何顶点。

我相信这可以简化为 TSP（旅行商问题），我们只需要访问一部分城市。假设有n个城市的常规 TSP 问题。但是，在这个特定问题中，我们不必访问所有n个城市，只需访问其中的一个特定子集m，其中m<=n。不需要访问n中而不是m中的城市，但如果路径m1->m2大于m1->n1->m2则它们可能需要访问。

然而，这个“更简单”的 TSP 问题仍然是 NP-hard 吗？任何人都知道可以用作减少的更好的NP-hard问题吗？

4

1 回答 1

2

将这个问题简化为 TSP 不会证明任何有趣的事情。在这里，我会告诉你。

考虑这个问题SUMS-TO-TWELVE，即确定一组特定数字相加后是否为 12 的问题。我决定将其简化为 TSP，如下所示：创建一个由节点链组成的图，边的数量与输入集中的数字一样多，并且每条边的成本等于输入集中的相应数字。最后，从第一个节点到最后一个节点添加一条额外的边，成本为零。如果 TSP 的解的成本为 12，则序列通过SUMS-TO-TWELVE。

这是一个非常愚蠢的方法来查看数字是否加到十二。我还没有证明这SUMS-TO-TWELVE很困难，我已经证明它很容易，或者至少和 NP 问题一样简单——也就是说，它是“在 NP 中”。但是我们不倾向于使用归约来证明问题存在于 NP 中，因为只给出一个在非确定性图灵机上解决问题的算法会更容易。

因此，您经常会看到一些论文采用了一些奇异的问题并降低了 3SAT 或 TSP 或其他任何内容。您很少看到将奇异问题简化为其他问题的论文。这不是一件有用的事情。

于 2015-11-10T17:42:59.493 回答