多米諾骨牌匹配算法

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

，因爲它現在是沒有明確規定，因爲它可能是問題 - 究竟如何解決被評爲？最重要的標準是什麼？它是最長鏈條的長度嗎？是否有創造長度鏈的懲罰？

這樣的問題往往有助於將結構可視化爲一個圖形 - 比如說爲每個圖塊分配一個頂點（V [i]）。那麼對於每個i，如果可以將V [i]放置在鏈中的V [j]的左邊（如果V [i]對應於（X），則在頂點V [i]，V [j] ，A），那麼對於某些X，Y，A，V [j]對應於（A，Y）。

在這樣的圖中，鏈是路徑，週期是閉合的（「循環」）鏈，並且問題已經減少到尋找圖的一些循環和/或路徑覆蓋。這種類型的問題反過來通常可以減少爲匹配或*流問題（最大流量，最大成本最大流量，最小成本最大流量或你有什麼）。

但是，在你可以進一步減少之前，你必須建立精確的規則，根據哪一個解決方案被確定爲比另一個「更好」。

Answer 2

很容易檢查是否存在由所有多米諾骨牌組成的環鏈。首先，需要進行以下向圖G：

的G

• 節點是在你的示例骨牌（A，B，C ...）的符號，
• 對於每個多米諾（A，B）你放有向邊從A到B

存在着由所有的多米諾骨牌當且僅當存在於G的Eulerian cycle要檢查是否存在歐拉週期G中就足夠，以檢查天氣每個節點都有一個循環鏈甚至程度。

Answer 3

我不確定這是否真的如此，但通過您的示例來判斷，您的問題看起來與將排列分解爲不相交循環乘積的問題類似。每個瓦片（X，Y）可以被看作P（X）= Y，對於排列P.如果這符合你的假設，好的（或壞的）消息是這種分解是獨特的（直到循環次序）和很容易找到。基本上，你從任何瓷磚開始，另一方面找到一個匹配的瓷磚，並按照此直到找不到匹配。然後你轉向下一個未觸及的點。如果這不是你正在尋找的，那麼t.dubrownik更通用的基於圖形的解決方案看起來就像是要走的路。

Answer 4

無法水平翻轉的多米諾骨牌==有向圖。

將多米諾骨牌一個接一個地稱爲「路徑」，如果它是封閉路徑，則是電路。

包含圖的所有頂點的電路是哈密爾頓電路。

您在圖論中的問題是：如何將您的圖分解（分解）爲具有哈密爾頓電路的最小數量的子圖。 （又名漢密爾頓圖）