完整权图和哈密顿游 [英] Complete Weighted Graph and Hamiltonian Tour

问题描述

我遇到了一个期中考试的问题。任何人都可以明确的答案？

I ran into a question on a midterm exam. Can anyone clarify the answer?

问题答：给定一个完整的加权图G，找到一个汉密尔顿之旅以最小的重量

Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight.

B题：给定一个完整权图G和实数R，并摹有一个汉密尔顿的游览与重量至多r

Problem B: Given a Complete Weighted Graph G and Real Number R, does G have a Hamiltonian Tour with weight at most R?

假设有一台机器，解决了B.多少次我们可以调用B（每次G和实数R给出），解决问题的一个与该机器？假设G中边的总结为M。

Suppose there is a machine that solves B. How many times can we call B (each time G and Real number R are given),to solve problem A with that machine? Suppose the sum of Edges in G up to M.

1），我们不能做到这一点，因为有无数的状态。

1) We cannot do this, because there is uncountable state.

2）O（| E |）时间

2) O(|E|) times

3）O（LG米）时间

3) O(lg m) times

4），因为A是NP难的，这是无法做到的。

4) because A is NP-Hard, This is cannot be done.

推荐答案

第一算法的

答案是：（3）O（LG米）次。你只需要执行二进制搜索的最小哈密尔顿游的加权图。请注意，如果有长度的哈密尔顿旅游→图中，有在检查没有任何意义，如果一个汉密尔顿游览长度 L'的，其中 L'＆GT; →，存在，因为你所感兴趣的最小重量哈密尔顿之旅。所以，在你的算法的每一步可以消除一半，剩下的可能巡回权重。因此，你将不得不调用 B 在你的机器 O（LG M）时间，其中<​​code >米表示在完全图的所有边的总重量

The answer is (3) O(lg m) times. You just have to perform a binary search for the minimum hamiltonian tour in the weighted graph. Notice that if there is a hamiltonian tour of length L in the graph, there is no point in checking if a hamiltonian tour of length L', where L' > L, exists, since you are interested in the minimum-weight hamiltonian tour. So, in each step of your algorithm you can eliminate half of the remaining possible tour-weights. Consequently, you will have to call B in your machine O(lg m) times, where m stands for the total weight of all edges in the complete graph.

编辑：

第二种算法的

我有一个小的上述算法，它使用机器的修改 O（| E |）倍，因为有些人说，我们不能应用在二进制搜索不可数可能值的集合（和它们可能右）：以从图中边的每个可能子集，并且对于每个子集存储一个值，该值是从所述子集的所有边的权重的总和。让我们存储在名为瓦尔阵列的所有子集的值。该数组的大小是 2 ^ | E | 。排序瓦尔以递增的顺序，然后应用二进制搜索的最小哈密尔顿路径，但这个时候打电话，解决问题仅B从瓦尔阵列。因为边缘的每一个子集被包括在排序后的数组中，这是保证该溶液会被发现。本机的电话总数为 O（LG电子（2 ^ | E |）），这是 O（| E |）。因此，正确的选择是（2）O（| E |）时间。

I have a slight modification of the above algorithm, which uses the machine O(|E|) times, since some people said that we cannot apply binary search in an uncountable set of possible values (and they are possibly right): Take every possible subset of edges from the graph, and for each subset store a value that is the sum of weights of all edges from the subset. Lets store the values for all the subsets in an array called Val. The size of this array is 2^|E|. Sort Val in increasing order, and then apply binary search for the minimum hamiltonian path, but this time call the machine that solves problem B only with values from the Val array. Since every subset of edges is included in the sorted array, it is guaranteed that the solution will be found. The total number of calls of the machine is O(lg(2^|E|)), which is O(|E|). So, the correct choice is (2) O(|E|) times.

注意：

第一种算法我建议可能不正确，因为有人指出，你不能在不可数集应用二进制搜索。由于我们正在谈论的实数，我们不能在适用范围内的二进制搜索 [0-M]

The first algorithm I proposed is probably incorrect, as some people noted that you cannot apply binary search in an uncountable set. Since we are talking about real numbers, we cannot apply binary search in the range [0-M]

这篇关于完整权图和哈密顿游的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！