哈密​​顿路径算法 [英] Hamiltonian path algorithm

问题描述

我有一个项目，我必须找到它，如果存在的话，一个哈密尔顿路径在一个无向图中使用两种不同的算法。我已经实现了使用回溯的启发式算法，但我一直在寻找另一个，我似乎无法找到它。

所以我的问题是，你知道要找到一个哈密尔顿路径，而不是使用回溯？

编辑：看了几个其他帖子后，我发现我们可以通过使用最长的路径找到哈密尔顿路径算法，并检查路径长度是否等于顶点数-1。我想知道这是否为真。

预先感谢。

因为哈密尔顿路径是NP完全的，你可能会以某种形式的回溯结束。无论您是使用堆栈还是穷尽枚举来实现指数性的爆炸，主要取决于您。

如果您查看公式，可以查看各种TSP算法（I并不知道哈密顿路径技术）。考虑到任何利用三角不等式的方法都不适用，因为你的权重都是有效的1和无穷大（边不存在）。

寻找分支和削减不需要三角不等式的TSP公式。分支和切割似乎是针对TSP的可证明最佳解决方案的最先进的技术。

使用最小生成树进行分支和绑定可能很好（这很容易以实现），并且可以以迭代的方式（分支之间）用节点权重来扩充最小生成树，作为将度数> 2的节点分解为度数为2的节点而不改变结果的正确性的一种方式。我不记得技术名称（我在工作，所以我不能查找它）。但是你的MST新距离度量是：

cost [i，j] =（exists（i，j）？1：infinity）+ node_augmentation [i] + node_augmentation [j]。

增加体面收敛的规则会更复杂一些（如果度数[i]> 2，则会增加），如果度数[i] < ; 2），但是我再也记不起这篇论文了（我认为它可能是Held-Karp，但我可能会离开）。

对不起一个蹩脚的答案，但我希望这可以帮助你寻找方法。由于我不太清楚TSP技术对哈密顿路径技术的适用程度如何，我可能没有帮助。

I have a project where I have to find, if it exists, an hamiltonian path in a undirected unweighted graph with two different algorithms. I already implemented an heuristic algorithm using backtracking but I've been looking for the other and I can't seem to find it.

So my question is, which algorithm do you know to find an hamiltonian path other than using backtracking?

EDIT : After looking at several other posts, I found that we could find an hamiltonian path by using the longest path algorithm and check if the length of the path equals number of vertex - 1. I'd like to know if this is true or not.

Thanks in advance.

解决方案

Since hamiltonian path is NP-complete, you'll probably end up with some form of backtracking. Whether you use the stack or exhaustive enumeration to achieve your exponential blow up is largely up to you.

If you look for formulations, you can look at various TSP algorithms (I don't really know hamiltonian path techniques). Take into account that any that exploit the triangle inequality won't apply, since your weights are all effectively 1 and infinity (edge does not exist).

Look for branch and cut formulations of TSP that don't require the triangle inequality. Branch and cut seems to be the state of the art technique for provably-optimal solutions to the TSP.

Branch and bound with a minimum spanning tree might be nice (it's easy to implement), and you can augment the minimum spanning tree with node-weights in an iterative fashion (between branching) as a way of breaking nodes of degree > 2 into nodes of degree 2 without changing the correctness of the result. I can't remember the technique name (and I'm at work, so I can't look it up). But your new distance metric for MST would be:

cost[i,j] = (exists(i,j) ? 1 : infinity) + node_augmentation[i] + node_augmentation[j].

The rules for changing augmentation for decent convergence are a little more complicated (increase if degree[i] > 2, decrease if degree[i] < 2), but again, I can't remember the paper (I think it might have been Held-Karp, but I may be way off).

Sorry for a crappy answer, I hope that helps you in your search for approaches, though. Since I don't really know how well TSP techniques apply to hamiltonian path techniques, I may be of no help.

这篇关于哈密​​顿路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！