哈密頓路徑在Haskell

Question

我不知道如何使定列表列表的功能，例如：

[0,0,1,1]，[0,0,1 ，0]，[1,1,0,1]，[0,0,0,0]]

這意味着第一個可以去第二個和第三個節點2可以去到第三，第三個節點可以去第一，第二和第四，第四個節點不能去任何一個，所以，我想在haskell中做一個函數，給出那種列表的列表（只有0和1）返回一個Bool，如果我找到一條哈密爾頓路徑，這意味着如果你可以訪問所有的節點

Answer 1

哈密頓路徑是通過圖形訪問每個節點一次的路徑。找到一個最簡單最天真的方法是實際嘗試節點的所有可能的排列，並且對於每個這樣的路徑檢查它是否是哈密爾頓算子。

爲了編寫這樣的功能，請嘗試分解問題。

首先編寫一個函數來檢查兩個節點之間是否有邊：hasEdge :: [[Int]] -> Int -> Int -> Bool。

另一個有用的函數將檢查一個路徑是哈密頓量：isHamiltonian :: [[Int]] -> [Int] -> Bool。假設第二個參數是每個節點只有一次的節點號的列表，因此您只需驗證列表中的每個後續對都表示圖中的一條邊。

現在剩下的就是生成列表[0..(length ps - 1)]的所有排列並檢查是否有滿足isHamiltonian謂詞。你migth找到功能permutations從Data.List在這裏非常有用。

這種方法顯然會很慢，但這對於一個NP難度問題是可以預料的。無論如何，在實施更好的算法之前，這可能是一個好的開始。