改进Dominos算法

Question

我试图解决多米诺骨牌的一个细微的变化，在这种情况下，你会得到一组多米诺骨牌，并且必须对它们进行排序，使不匹配的次数(当两个相邻的瓷砖没有相同的触点数，例如[1 | 3] [4 | 1] =失配)最小化。此外，瓷砖不能旋转，只能转换(例如，不能将1\x 3旋转到3\\ 1)，以及

例如，假设给您的是tiles：[1 | 2]、[4 | 2]、[2 | 3]，您可以找到序列[1 | 2] [2 | 3] [4 | 2]，它在最后两个瓷砖之间只有一个不匹配。

我已经想出了几种算法。通过计算所有排列，计算它们的分数，并返回最佳的排列，就可以找到最优的(即最少的错配数)。这也可以通过DP或回溯来改进，例如避免那些已经比当前最好的解决方案得分更差的计算分支。这是可行的，但显然对于大型测试用例来说非常缓慢。我还找到了寻找次优解的方法，但在合理的时间内使用禁忌搜索和遗传算法。

这些工作，但我正在寻找的是一个最优解决方案，将解决它的速度比O(N!)需要我最初的蛮力解决方案。

不过，我怀疑这可能是不可能的。如果你把这个问题看作一个图问题，我们有一个图，其中的瓷砖是顶点，有向边(有向的，因为瓷砖不能旋转)。然后，它成为通过图求最短哈密顿路径的问题，该图是NP-完全的。

是否有另一种方法可以在合理的时间内最优地解决这一问题？

Answer 1

我认为像O(2^N * K)这样的东西是可行的，因为在一条链中，你并不真正关心里面是什么。

您可以使用DP超过2^N*K数组，其中N是瓷砖的数目( 2^N是包含的瓷砖的位掩码)，K是最后的接触数。

递归函数的原型如下所示：

int solve(Bit掩码mySet，int touchingNumber)；

在这里循环set (T)中的tiles，检查它们的上一个touchingNumber是否等于touchingNumber。循环上一次触摸数(L)。现在找出所有L和T的最小值：

• 给定T，L的候选解(mySet-T，L)，如果T.first==L
• 给定T，L的候选解(mySet-T，L)+1，如果T.first!=L

一旦计算完毕，求解参数的解决方案将存储在全局数组中，并用于以后的调用。

对于给定的参数，可能没有解决方案，应该跳过这样的结果。

最后的解决方案是最小的所有可能的最后触摸数字和全套瓷砖。