哈密顿循环的归约算法
我认为哈密顿循环问题可以概括为：
给定一个无向图
G = (V, E)，a 哈密顿回路是在G中经过的一次旅行G的每个顶点一次且仅一次。
现在，我想做的就是将我的问题简化为这样。我的问题是：
给定一个加权无向图
G、整数k和顶点u, v两者都在G中，G中是否存在从u到v的简单路径 总重量至少为k？
所以知道哈密顿循环问题是NP完全的，通过将这个问题简化为哈密顿量，这个问题也被证明是NP完全的。我的问题是将其简化为哈密顿量的函数。
- 最大的问题是哈密顿量问题不处理边权重，所以我必须将我的图转换为没有任何权重的图。
- 最重要的是，这个问题有指定的开始和结束（u 和 v），而哈密顿量找到一个循环，因此任何开始都与结束相同。
对于（1），我正在考虑传递一个图，其中取出总权重小于 k 的所有简单路径。 对于（2），我认为这并不是一个真正的问题，因为如果存在哈密顿循环，那么从 u 到 v 的简单路径可以从中分割出来。
所以，我真正的问题是：
- 我的解决方案能给我正确的答案吗？
- 如果是，那么我如何取出将产生总权重小于 k 的简单路径的边，而不影响实际解决方案可能需要这些边之一的可能性？因为如果一条边e被取出来，因为它产生了一条简单的权重<1的路径。 k 对于 E 的子集，它仍然可以用在具有不同边组合的简单路径中，以产生权重 >= k 的路径。
谢谢！
I believe that the Hamiltonian cycle problem can be summed up as the following:
Given an undirected graph
G = (V, E), a
Hamiltonian circuit is a tour inGpassing through
every vertex ofGonce and only once.
Now, what I would like to do is reduce my problem to this. My problem is:
Given a weighted undirected graph
G, integerk, and verticesu, v
both inG, is there a simple path inGfromutov
with total weight of AT LEASTk?
So knowing that the Hamiltonian cycle problem is NP-complete, by reducing this problem to the Hamiltonian, this problem is also proved NP-complete. My issue is the function reducing it to Hamiltonian.
- The big issue is that the Hamiltonian problem does not deal with edge weights, so I must convert my graph to one that doesn't have any weights.
- On top of that, this problem has a designated start and finish (u and v), whereas the Hamiltonian finds a cycle, so any start is the same as the finish.
For (1), I am thinking along the lines of passing a graph with all simple paths of total weight LESS THAN k taken out.
For (2), I am thinking that this is not really an issue, because if there is a Hamiltonian cycle, then the simple path from u to v can be sliced out of it.
So, my real questions are:
- Is my solution going to give me the right answer?
- If yes, then how can I take out the edges that will produce simple paths of total weight less than k WITHOUT affecting the possibility that one of those edges may be required for the actual solution? Because if an edge e is taken out because it produces a simple path of weight < k for a subset of E, it can still be used in a simple path with a different combination of edges to produce a path of weight >= k.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你的减少方向是错误的。为了证明你的问题是 NP 完全问题，你需要将哈密尔顿电路简化为它，这非常简单。即表明每个汉密尔顿电路问题都可以用您的问题变体来表达。
Your reduction is in the wrong direction. To show that your problem is NP-complete, you need to reduce Hamilton Circuit to it, and that is very easy. I.e. show that every Hamilton Circuit problem can be expressed in terms of your problem variant.
更多的是提示而不是答案：
未加权图可以解释为加权图，其中每条边的权重为
1。在这样的图中，哈密顿循环的成本是多少？More of a hint than an answer:
A unweighted graph can be interpreted as a weighted graph where each edge has weight
1. What would the cost of a Hamiltonian cycle be in a graph like that?关于周期和路径不匹配的部分是正确的，是您需要解决的问题。基本上，您需要证明哈密顿路径问题也是 NP 完全问题（相对直接地简化为循环问题）
至于其他部分，您正在以错误的方向做事。您需要证明您的更复杂的问题可以解决哈密顿路径问题（因此是 NP 难问题）。为此，您基本上只需要使用单位成本边的特殊情况。
The part about the mismatch between cycles and paths is correct and is a problem you need to solve. Basically you need to prove that the Hamiltonian Path problem is also NP complete (a relatively straightfoward reduction to the Cycle problem)
As for the other part, you are doing things in the wrong direction. You need to show that your more complicated problem can solve the Hamiltonian Path problem (and is thus NP-hard). To do this you just basically have to use the special case of unit-cost edges.