算法来找到以图形的哈密顿路径的数量 [英] Algorithms to find the number of Hamiltonian paths in a graph
问题描述
我要解决的哈密尔顿路径的问题略加修改。它被修改，所述起始和结束点被给予，而不是确定溶液是否存在我们和，我们希望找到解决方案的的号的（可能为0）。
I'm trying to solve a slightly modified version of the Hamiltonian Path problem. It is modified in that the start and end points are given to us and instead of determining whether a solution exists, we want to find the number of solutions (which could be 0).
该图是给我们作为一个二维数组，与节点是数组的元素。此外，我们只能水平移动或垂直，不斜。不用说，我们不能从一个城市到二级城市，因为要做到这一点，我们需要去一个城市的两倍。
The graph is given to us as a 2D array, with the nodes being the elements of the array. Also, we can only move horizontally or vertically, not diagonally. Needless to say, we can't go from one city to two cities because to do that we would need to visit a city twice.
我写蛮力溶液试图所有4（3或2上的边缘节点）在每个节点处可能的行动，然后计数解的数目（这是当它到达目标，并已看到所有其他节点太），但它运行的时间对中等规模的投入荒谬的金额（如，说的7x7阵列）。
I wrote a brute force solution that tries all 4 (3 or 2 for nodes on the edges) possible moves at each node and then counts the number of solutions (which is when it reaches goal and has seen all the other nodes too), but it ran for ridiculous amounts of time on inputs of modest size (like, say a 7x7 array).
我也想过用双向搜索既然知道了目标，但这并没有真正的帮助，因为我们不只是想边缘见面，我们也想确保所有的节点都被访问。此外，这可能是因为当所有节点已经用尽两个条纹之间，它们的方式，使得它们不能被接合结束。
I also thought of using bidirectional search since we know the goal, but this didn't really help, since we don't just want the fringes to meet, we want to also ensure that all the nodes have been visited. Moreover, it could be that when all nodes have been exhausted between the two fringes, they end in a way such that they can't be joined.
我觉得有一些我不知道这是留给我只用蛮力解决方案。我知道，这个问题本身是NP完全问题，但我不知道是否有任何的改善了蛮力。有人建议别的东西？
I feel like there is something I don't know that's leaving me with only a brute force solution. I know that the problem itself is NP-complete, but I'm wondering if there are any improvements over brute force. Can someone suggest something else?
- 编辑 -
我提到，使用双向搜索并没有真正帮助，我想澄清，为什么我是这么认为的。考虑一个2×3图，左上角和右下角的节点分别为起始和目标。让条纹的右侧，从开始的双向搜索和移动距离球门左侧。经过2移动，所有的节点都被访问过，但也没有办法加入条纹，因为我们只能从一个节点在一个方向。然而，有可能使算法工作的一些修改，如大卫指出在低于他的答案。
I mentioned that using bidirectional search doesn't really help and I'd like to clarify why I thought so. Consider a 2x3 graph with the top left and bottom right nodes being the start and goal respectively. Let the fringes for bidirectional search move right from start and left from goal. After 2 moves, all the nodes would have been visited but there is no way to join the fringes, since we can only go in one direction from one node. However, it might be possible to make the algorithm work with some modifications, as David pointed out in his answer below.
推荐答案
...唯一已知的方法来确定 一个给定的一般图形是否有 汉弥尔顿路径是承担一个 穷举搜索
... the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search
我相信你会希望先找到一个单一的哈密尔顿路径，然后将其分成两条路径，使得分割点一个清楚分隔两个路径尽可能。然后，你可以发现，在子图的排列（和递归当然！）
I believe you would want to start by finding a single hamiltonian path, and then splitting it into two paths, making the split point one that clearly separates the two paths as much as possible. Then you can find the permutations in the subgraphs (and recurse, of course!)
我不知道确切的算法，但那种鸿沟而治之的方法是在那里我会开始。
I don't know the exact algorithm, but that sort of divide and conquer method is where I would start.
这篇关于算法来找到以图形的哈密顿路径的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
