查找立方平面圖中的哈密爾頓週期

Question

我有相當小的（40-80節點）立方（3-規則）平面圖，我必須決定他們的哈密爾頓性。我知道的事實，這任務是NP完全，但我希望漸近指數時間的算法是仍然是在圖形大小我很感興趣，非常快

Answer 1

40個節點似乎是可行的。您正在選擇包含60個邊的40個。

讓我們嘗試一個深度優先搜索。

要開始，選擇一個頂點V.您將需要排除其3個入射邊緣中的一個。一次嘗試這三種可能性。當您選擇要排除的邊時，您將強制包含4條邊。在此之後，我們將調用被排除的邊的頂點「used」。

如果你可以重複這個過程10次，你會選擇所有40條邊，只搜索3^10（59049）個可能性。當然，在足夠的邊界被確定之後，你會用完「孤立」的頂點。

但是，我們現在有一個算法的想法。在每一步中，嘗試用最少的「已使用」鄰居來挑選一個頂點。實際上，挑選2個使用鄰居的頂點是最好的，因爲使用的邊是強制的。我不確定選擇1或0使用鄰居的頂點是次好的。嘗試兩種方式！ （和3個使用的鄰居表示搜索失敗）

當我們完成拾取邊緣時，檢查它們是否形成單個週期。

你有幾個樣本圖嗎？我可能會嘗試一個簡單的實現。

Answer 2

從http://mathworld.wolfram.com/HamiltonianCycle.html： 「魯賓（1974）介紹一個高效的搜索程序，可以使用減少回溯和臆測的減法來找到圖中的一些或全部Hamilton路徑和電路。「

紙轉讓在這裏：http://portal.acm.org/citation.cfm?id=321850.321854