Я много читал о темах Complete Weighted Graph и Hamiltonian Tour на этом сайте, которые спросил один из пользователей, я спросил много сотрудников в моем университете, но не смог получить хороший ответ, я изменил важную часть этого вопроса следующим образом:
Задача A: Имея полный взвешенный граф G, найти
weightsгамильтонова тура с минимальным весом.Задача B: Имея полный взвешенный граф G и действительное число R, имеет ли граф G гамильтонов тур с весом не более R?
Предположим, что есть машина, которая решает B. Сколько раз мы можем вызывать B (каждый раз, когда заданы G и действительное число R), чтобы решить задачу A с помощью этой машины? Предположим, что сумма ребер в G до M.
Мы не можем этого сделать, потому что существует неисчисляемое состояние.
О(|Е|) раз
O(lg м) раз
поскольку A является NP-сложным, это невозможно сделать.
Я прочитал этот файл, на странице 2 он написал:
а) оптимизационная задача (в строгом смысле): найти оптимальное решение
б) задача оценки: определить значение оптимального решения
c) связанная задача: при заданной границе B определить, является ли значение оптимального решения выше или ниже B.
в следующих двух абзацах
Чтобы использовать c) при решении b), мы используем тот факт, что возможные значения комбинаторной задачи обычно дискретны и могут быть приняты целыми. Предположим, что мы можем решить связанную задачу c) за время T. Для соответствующей задачи вычисления b) обычно априори известно, что значение находится в пределах определенного диапазона [L, U] целых чисел. Используя бинарный поиск, мы решаем задачу оценки с помощью log | У - Л | обращений к связанной задаче c), и, следовательно, за время T log | У - Л |.
а в следующем он написал:
Пример: TSP на взвешенном графе Kn = (V, E, w: E -> Reals), |V| = п, |Е| = n-выбрать-2. Используйте в) для решения б). Тур или гамильтонов цикл в графе из n вершин имеет ровно n ребер. Таким образом, сумма S n самых длинных ребер является верхней границей длины оптимального тура. С другой стороны, сумма всех m выбранных n подмножеств n ребер представляет собой конечный набор чисел, и минимальная ненулевая разность d между двумя из этих чисел определяет степень детализации длин тура. Два разных тура либо имеют одинаковую стоимость, либо их длины отличаются не менее чем на d. Таким образом, бинарный поиск, вычисляющий log(S/d) связанных задач, определяет длину (значение) оптимального тура.
Мой вопрос: можем ли мы адаптировать это решение для выбора (3) таким образом?
