多米诺骨牌匹配算法

Question

给定一些由左右符号组成的输入，输出将这些输入链接在一起的链。

可以将输入想象成多米诺骨牌，不能水平翻转，并需要将它们链接在一起。创建大的循环链（如果您无法在现实中使用真正的多米诺骨牌，则忽略此步骤）优于小的循环链，而小的循环链优于起点和终点不匹配的链。

我们要寻找具有更多循环链（不管有多少个或长度如何）的输出。例如，3个循环链的输出比1个大链和一个剩余的单个多米诺骨牌更好。

有人能指点我正确的方向吗？这属于哪一类问题，是否有现有算法可用于解决？

示例（输出可能不正确！）：

in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,A)
out[0]=(0,1,2)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,C)
out[0]=(0,1)
out[1]=(2,3)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(E,F)
out[0]=(0,1)
out[1]=(2)
out[2]=(3)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,E)
out[0]=(0,1)
out[1]=(2,3)

in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,D)
out[0]=(0,1,2)

- zaf

---

不要提及，但我宁愿知道答案。我自己也在考虑图形方面，但这是我技能严重缺乏的领域。我正在努力通过阅读http://www.amazon.co.uk/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref=sr_1_1?s=books&ie=UTF8&qid=1301312087&sr=1-1来提高自己。如果你和我一样数学基础不够强，我强烈推荐这本书。 - Lieven Keersmaekers

@Lieven 嘿！我有很强的数学背景，只是没玩过多米诺 :) - zaf

Answer 1

无法水平翻转的多米诺骨牌 == 有向图。

将多米诺骨牌一个接一个地放置称为“路径”，如果是封闭路径，则为电路。

包括图中所有顶点的电路称为哈密顿电路。

在图论术语中，您的问题是：如何将图分解为具有哈密顿电路（又称哈密顿图）的最少子图数量。

- biziclop

---

谢谢你的提示。我会去查看哈密顿量相关的内容。 - zaf

Answer 2

问题现在没有表述得非常清楚 - 解决方案如何评估？最重要的标准是什么？最长链的长度吗？创建长度为一的链是否会受到惩罚？

在这种问题中将结构可视化为图通常是有帮助的 - 每个瓷砖分配一个顶点（V [i]）。然后为每个i，j在顶点V [i]，V [j]之间创建一条边，如果您可以将V [i]放置在链中的V [j]左侧（因此如果V [i]对应于（X，A），则V [j]对应于（A，Y）用于某些X，Y，A）。

在这样的图中，链是路径，循环是封闭的（“循环”的）链，问题已经被简化为查找图的某些循环和/或路径覆盖。这种类型的问题通常可以进一步简化为匹配或 *-flow 问题（max-flow、max-cost-max-flow、min-cost-max-flow 或其他）。

但是，在您进一步简化之前，必须确定确定一个解决方案比另一个解决方案更好的精确规则。

- t.dubrownik

---

我添加了一些更多的信息。最重要的标准是尽量减少单个多米诺骨牌的剩余。你的建议并不完全清楚，但我会查找流问题，看看是否有任何线索。谢谢。 - zaf

Answer 3

检查是否存在由所有多米诺骨牌组成的循环链非常容易。首先，您需要创建以下有向图G：

• G的节点是多米诺骨牌上的符号（例如A、B、C等）。
• 对于每个多米诺骨牌（A，B），您将从A到B放置一个有向边。

如果G中存在一个欧拉回路，则存在由所有多米诺骨牌组成的循环链。要检查G中是否存在欧拉回路，只需检查每个节点的度数是否为偶数即可。

- Paperback Writer

Answer 4

我不确定这是否是真的，但根据你的例子判断，你的问题看起来类似于将排列分解为不相交循环的问题。每个图块 (X,Y) 可以被视为一个排列 P 的 P(X) = Y 。如果这符合您的假设，好消息（或坏消息）是这样的分解是唯一的（循环顺序除外），而且非常容易找到。基本上，你从任何一个图块开始，找到另一侧匹配的图块，并一直跟随下去，直到无法找到匹配。然后你移动到下一个未触及的点。如果这不是你要找的，那么更通用的基于图形的解决方案由 t.dubrownik 提供。

- Kris

---

感谢您提供的简单想法和排列引导。 - zaf