Complete weighted G chart, search for weights and one machine

Question

I read a lot about the full weighted schedule and the Hamilton tour on this site, which was asked by one of the users, asked a lot of staff at my university, but I couldn’t get a good answer, I change the important part of this question as follows:

Task A: Given the full weighted schedule of G, find the weights of the Hamilton tour with the minimum weight.

Problem B: taking into account the full weighted graph G and the real number R, then G have a Hamilton tour with a mass of at most R?

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

• We cannot do this because there is an uncountable state.

• O (| E |) times

• O (log m) times

• because A is NP-Hard, this is not possible.

I read this file , on page 2 he wrote:

a) optimization problem (in the strict sense): find the optimal solution

b) assessment problem: determine the value of the optimal solution

c) related problem: for a given boundary B, determine whether the value of the optimal solution is above or below B.

in the next two paragraphs

To use c) in solution b) we use the fact that the possible values ​​of the combinatorial problem are usually discrete and integers can be accepted. Suppose we can solve the associated problem c) over time T. For the corresponding problem of estimating b) it is usually a priori known that the value lies in a certain range of [L, U] integers. Using binary search, we solve the evaluation problem with log | U - L | causes the associated problem c) and, therefore, in time T log | U - L |.

and in the following he wrote:

Example: TSP on a weighted graph Kn = (V, E, w: E → Reals), | V | = n, | E | equals n-choose-2. Use c) for solution b). A tour or a Hamiltonian cycle in a graph of n vertices has exactly n edges. Thus, the sum S of the largest n edges is the upper bound on the length of the optimal tour. On the other hand, the sums of all m choose -n subsets of n edges, the set of numbers is finite and the minimum nonzero difference d among these two numbers determines the granularity of the lengths of the tour. Two different tours have the same meaning or their length differs by at least d. Thus, a binary search that calculates log (S / d) related problems determines the length (value) of the optimal tour.

My question is: can we adapt this solution to select (3) in this way?

Answer 1

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

O(log M) .

Choose a = 0, b = M

• set R = (a + b) / 2 . Solve B with this R

• Result True

  Then there is a Hamiltonian tour with a mass of at most R Does it have a tougher upper bound? Set b = R and repeat to find out (go to 1).

• Result is False

  Then there is no Hamilton tour with a weight of at most R : the minimum weight is greater. Set a = R and repeat (go to 1).

This is a binary search algorithm .

Although it is theoretically that this algorithm will not work on all real numbers (especially irrational ones), in practice you cannot have irrational numbers. In any case, the computer can only represent approximations of irrational numbers, so you can use binary search to get an approximation that is suitable for many decimal places, since you are ready to run the algorithm for.

For example, if one of your edges has a value of pi , you will need to come to terms with its approximation, since the mathematical constant pi has an infinite number of digits. Therefore, no matter what algorithm you use, you will have a certain level of accuracy.