哈密顿路径在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难度问题是可以预料的。无论如何，在实施更好的算法之前，这可能是一个好的开始。