Невелосипедная дорожка ко всем узлам
Существует ли алгоритм или набор алгоритмов, которые позволили бы Вам найти самое короткое недалеко от произвольного узла запуска так, чтобы каждый узел посетили в весе, неориентированном графе? Это - не совсем Коммивояжер, потому что я не забочусь, посещают ли узел несколько раз. (Даже не имеет значения, если Вы возвращаетесь к запуску - Уокер может закончить в некотором отдаленном узле, пока это было последнее, должен был посетить все узлы.) Это - не совсем минимальное связующее дерево, потому что может случиться так, что, идя-> B-> C->-> D является (групповым) кратчайшим путем для посещения A, B, C, и D. Моя интуиция говорит, что это не настоящая проблема NP, потому что она не имеет ограничений, которые делают проблемы NP настолько хитрыми. Я мог, конечно, быть абсолютно неправым.
2 ответа
Из статьи Википедии о Задача коммивояжера :
Удаление условия посещения каждого города «только один раз» не снижает NP-жесткость, поскольку легко видеть, что в плоском случае существует оптимальный тур, который посещает каждый город только один раз (иначе, согласно неравенству треугольника, ярлык, пропускающий повторное посещение, не увеличил бы продолжительность тура).
Не знаю, каков этикет, когда нужно добавлять ответ на вопрос с уже принятым ответом.
Я добавляю этот ответ только для того, чтобы не переходить на другую страницу, чтобы не иметь дела с плоскими графами и неравенством треугольников, а также с тем фактом, что это просто и, вероятно, легче понять.
Проблема гамильтонова пути может быть сведена к следующему:
Предположим, у нас есть алгоритм с полиномиальным временем для решения нашей проблемы поиска обхода наименьшего веса, который посещает все вершины.
Учитывая граф, для которого нам нужно решить, существует ли гамильтонов путь, мы просто передаем его как есть в рассматриваемый алгоритм задачи, устанавливая веса ребер = 1. Если алгоритм возвращает значение> n-1 , то в исходном графе нет гамильтонова пути, иначе он есть.
Итак, эта задача NP-Hard.