Tile Trial NP-hard复杂性 [英] Tile Trial NP-hard complexity

问题描述

在《最终幻想XIII-3》游戏中，玩家遇到了几个难题.引入的第一个难题叫做 Tile Trial ，它为玩家提供了一个网格砖，其中一些砖块上有水晶.目标是取回所有晶体并到达出口，同时在每个瓷砖上踩不超过一次.

In the game Final Fantasy XIII-3, the player is presented with a couple puzzles. The first puzzle introduced is called Tile Trial, which presents the player with a grid of tiles, some of which have crystals on them. The goal is to retrieve all of the crystals and reach the exit, while stepping on each tile no more than once.

http://arxiv.org/pdf/1203.1633v1.pdf 的作者指出这个问题是NP-Hard问题，因为可以将特定情况简化为哈密顿循环.我发现这是一个幼稚的假设，因为他开发了一个特定的难题，尽管适合游戏规则，但恰好涉及汉密尔顿循环.

The author of http://arxiv.org/pdf/1203.1633v1.pdf stated that this problem is NP-Hard because a specific case can be reduced to Hamiltonian-cycle. I find that this is a naive assumption, because he developed a specific puzzle that, although suits the rules of the game, just happens to involve Hamiltonian-cycles.

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

Looking at the general case: We can model each tile of the puzzle as a vertex in a graph. A vertex has an edge to another vertex if two tiles are adjacent. The problem consists in finding a path from the starting tile to the ending tile while transversing all vertex that have crystals and not visiting any vertex more than once.

我相信可以将其简化为TSP(旅行推销员问题)，我们只需要访问一部分城市即可.假设 n 个城市经常出现TSP问题.但是，在这个特定问题中，我们不必访问所有 n 个城市，只需访问其中的特定子集 m ，其中 m <= n .不需要访问 n 中的城市，但不需要访问 m 中的城市，但是如果路径 m1-> m2 大于例如 m1-> n1-> m2 .

I believe that this could be reduced to the TSP (Traveling Salesman Problem) where we only need to visit a subset of cities. Assume a regular TSP problem with n cities. However, in this particular problem, we do not have to visit all the n cities, only a specific subset of them, m, where m<=n. The cities in n but not in m don't need to be visited, but they might if the path m1->m2 is larger than m1->n1->m2 for example.

但是，这个更简单的" TSP问题仍然是NP难题吗?任何人都知道有更好的NP-hard问题可以用来减少费用吗?

However is this "simpler" TSP problem still NP-hard? Anyone know of a better NP-hard problem that could be used as a reduction?

推荐答案

将这个问题简化为TSP不会带来任何有趣的结果.在这里，我告诉你.

Reducing this problem to TSP wouldn't prove anything interesting. Here, I'll show you.

请考虑问题SUMS-TO-TWELVE，该问题是确定特定的一组数字求和时是否得出十二的问题.我决定将其简化为TSP，如下所示:创建一个由节点链组成的图，其边数与输入集中的数字一样多，并且每个边的成本等于输入集中相应的数字.最后，从第一个节点到最后一个节点再增加一条边，成本为零.如果解决TSP的成本为12，则序列通过SUMS-TO-TWELVE.

Consider the problem SUMS-TO-TWELVE, which is the problem of determining whether a particular set of numbers, when summed up, results in twelve. I've decided to reduce this to TSP as follows: Create a graph consisting of a chain of nodes, with as many edges as there are numbers in the input set, and with each edge's cost equal to the corresponding number in the input set. Finally, put an additional edge from the first to the last node, with a cost of zero. If the solution to TSP has cost 12, then the sequence passes SUMS-TO-TWELVE.

查看数字是否加到12是一种非常愚蠢的方法.我还没有证明SUMS-TO-TWELVE是困难，我已经证明它很容易，或者至少和NP问题一样容易-也就是说， 在NP中".但是我们不倾向于使用归约法来证明问题出在NP上，因为在非确定性Turing机器上给出解决问题的算法比较容易.

Which is a very silly way to see if numbers add to twelve. I haven't proven that SUMS-TO-TWELVE is hard, I've proven that it's easy, or at least, as easy as NP problems -- that is, that it's "in NP". But we don't tend to use reductions to prove that a problem is in NP, because it's easier to just give an algorithm which solves the problem on a nondeterministic Turing machine.

因此，您经常看到带有一些特殊问题并减少3SAT或TSP或其他结果的论文.您很少看到将异国情调减少到其他问题的论文.这不是一件有用的事情.

So you often see papers which take some exotic problem and reduce 3SAT or TSP or whatever to it. You rarely see papers which reduce the exotic problem to something else. It's not a useful thing to do.

这篇关于Tile Trial NP-hard复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！