多米诺骨牌匹配算法

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)

Answer 1

现在的问题并没有得到尽可能明确的表述——解决方案的评级到底如何？最重要的标准是什么？是最长链的长度吗？创建长度为 1 的链是否会受到惩罚？

在此类问题中，将结构可​​视化为图形通常很有帮助 - 例如，为每个图块分配一个顶点 (V[i])。然后，对于每个 i、j，如果您可以将 V[i] 放置在链中 V[j] 的左侧，则在顶点 V[i]、V[j] 之间创建一条边（因此，如果 V[i] 对应于 (X , A) 那么 V[j] 对应于某些 X, Y, A) 的 (A, Y)。

在这样的图中，链是路径，循环是闭合（“循环”）链，并且问题已简化为找到图的某些循环和/或路径覆盖。此类问题通常可以简化为匹配或 * 流问题（最大流、最大成本最大流、最小成本最大流或其他问题）。

但在进一步减少之前，您必须建立精确的规则，根据该规则确定一种解决方案比另一种解决方案“更好”。