Полный взвешенный график G, нахождение весов и одна машина

Question

Я много читал о темах Complete Weighted Graph и Hamiltonian Tour на этом сайте, которые задавал один из пользователей, спрашивал много сотрудников в моем университете, но не мог найти хороший ответ, я изменяю важную часть этого вопроса как следующим образом:

Задача A: учитывая полный взвешенный граф G, найдите weights гамильтониана тур с минимальным весом.

Задача B: Учитывая полный взвешенный граф G и действительное число R, имеет ли G гамильтоново тур с весом не более R?

Предположим, есть машина, которая решает B. Сколько раз мы можем позвонить B (каждый раз, когда задаются G и действительное число R), чтобы решить проблему A с этой машиной? Пусть сумма ребер в G с точностью до M.

1. Мы не можем этого сделать, потому что существует неисчислимое состояние.

2. O(| E |) раз

3. O(LG м) раз

4. потому что A NP-Hard, это не может быть сделано.

Я прочитал этот файл, на странице 2 он написал:

а) задача оптимизации (в строгом смысле): найти оптимальное решение

б) оценка проблемы: определить значение оптимального решения

c) связанная задача: с учетом границы B определить, является ли значение оптимального решения выше или ниже B.

в следующих двух абзацах

Чтобы использовать в) при решении б), мы используем тот факт, что возможные значения комбинаторной задачи обычно являются дискретными и могут быть приняты за целые числа. Предположим, что мы можем решить связанную задачу c) в течение времени T. Для соответствующей задачи оценки b) обычно априори известно, что значение лежит в некотором диапазоне [L, U] целых чисел. Используя бинарный поиск, мы решаем задачу оценки с помощью log | U - L | обращается к связанной задаче в) и, следовательно, во времени T log | U - L |.

и в следующем он написал:

Пример: TSP на весовом графе Kn = (V, E, w: E -> Reals), |V| = n, |E| = n-выбирать-2. Используйте с), чтобы решить б). Тур или гамильтонов цикл в графе из n вершин имеет ровно n ребер. Таким образом, сумма S самых длинных ребер является верхней границей длины оптимального тура. С другой стороны, суммы всех m выберите-n подмножеств n ребер - это конечный набор чисел, а минимальная ненулевая разница d между двумя из этих чисел определяет гранулярность длин обхода. Два разных тура либо имеют одинаковое значение, либо их длина различается как минимум на d. Таким образом, бинарный поиск, который вычисляет связанные с журналом ( S / d) задачи, определяет длину (значение) оптимального тура.

Мой вопрос: можем ли мы адаптировать это решение, чтобы выбрать (3) таким образом?

Answer 1

Предположим, есть машина, которая решает B. Сколько раз мы можем позвонить B (каждый раз, когда задаются G и действительное число R), чтобы решить проблему A с этой машиной? Пусть сумма ребер в G с точностью до M.

O(log M),

Выбирать a = 0, b = M,

1. задавать R = (a + b) / 2, Решите Б с этим R,

2. Результат True

   Тогда есть Гамильтониан Тур с весом не более R, Есть ли один для более жесткой верхней границы? Задавать b = R и повторите, чтобы узнать (перейдите к 1).

3. Результат False

   Тогда нет гамильтонова тура с весом не более R: минимальный вес больше. Задавать a = R и повторите (перейдите к 1).

Это алгоритм двоичного поиска.

Хотя теоретически верно, что этот алгоритм не будет работать со всеми действительными числами (особенно иррациональными), на практике вы не можете иметь иррациональные числа. В любом случае компьютер может представлять только приближения иррациональных чисел, поэтому вы можете использовать бинарный поиск, чтобы получить приближение, которое подходит для такого количества знаков после запятой, для которого вы хотите запустить алгоритм.

Например, если один из ваших ребер имел значение pi, вы должны согласиться с приближением этого, так как математическая константа pi имеет бесконечное количество цифр. Поэтому, независимо от того, какой алгоритм вы использовали, у вас будут проблемы с точностью.