Поиск оптимальной стоимости решения для коммивояжера - PullRequest
Новая
       26

Поиск оптимальной стоимости решения для коммивояжера

4 голосов
/ 08 декабря 2010

Я работаю над этой проблемой: 

TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b, 
if such a tour exists.

TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.

Показать, что если TSP может быть решен за полиномиальное время, то и TSP-OPT может.

Теперь первое, чтоВспоминается, что если бы я знал цену оптимального решения, я мог бы просто установить b на это и вуаля. И, разве вы не знаете, в другом месте моей книги это содержит подсказку для этого?Сама проблема:

Как найти оптимальную стоимость?Легко: с помощью бинарного поиска.

Я думаю, что я мог бы здесь что-то очень плохо понять.Бинарный поиск предназначен для поиска позиции данного элемента в отсортированном списке.Как именно это может помочь мне найти оптимальную стоимость?Я искренне запутался.К сожалению, авторы не уточняют дальше.

Единственное, о чем я мог бы подумать, чтобы решить эту проблему, - это доказать, что они обе сводятся к другой проблеме, являющейся NP-полной, которую я могу закончитьделаю, но все же ... это меня беспокоит.

1 Ответ

4 голосов
/ 08 декабря 2010

Предположим, что у вас есть некоторая нижняя граница l (например, 0) и верхняя граница u (например, сумма всех весов ребер).Во-первых, попытка найти решение общей стоимости <= (l + u) / 2.Если вам это удастся, попробуйте еще раз для более низкого значения: (3l + u) / 4;если нет, попробуйте более высокое значение: (l + 3u) /4.</p>

Я бы назвал это методом деления пополам (Wikipedia) , а не двоичным поиском, но идея та же,Мы хотим найти некоторый диапазон для оптимального значения, поэтому мы начинаем с середины и движемся вверх, если мы слишком низки, и вниз, если мы слишком высоки.

...