algorithm - 多米诺骨牌匹配算法

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

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

一张接一张的多米诺骨牌称为“路径”，如果是闭合路径，则为回路。

包含图的所有顶点的回路是哈密顿回路。

用图论术语来说，您的问题是:如何将您的图拆分(分解)为最少数量的具有哈密顿回路的子图。 (又名哈密顿图)