Путь без цикла ко всем узлам

Question

Существует ли алгоритм или набор алгоритмов, которые позволили бы вам найти кратчайшее расстояние ходьбы от произвольного начального узла, чтобы каждый узел посещался в весовом неориентированном графе?Это не совсем коммивояжер, потому что мне все равно, если узел посещают более одного раза.(Это даже не имеет значения, если вы вернетесь к началу - ходок может оказаться в каком-то удаленном узле, если он был последним, необходимым для посещения всех узлов.) Это не совсем минимальное связующее деревопотому что может случиться так, что движение A -> B -> C -> A -> D является (неуникальным) кратчайшим путем для посещения A, B, C и D. Моя интуиция говорит, чтоЭто проблема NP, потому что она не имеет ограничений, которые делают проблемы NP настолько сложными.Я, конечно, могу ошибаться.

Answer 1

Из статьи Википедии о Проблема коммивояжера :

Отмена условия посещения каждого города «только один раз» не снимает NP-твердость, так как легко видеть, что в плоском случае есть оптимальный тур, который посещает каждый город только один раз (в противном случае по неравенству треугольника ярлык, пропускающий повторное посещение, не увеличит продолжительность тура).

Answer 2

Не уверен, что такое этикет, чтобы добавить ответ на вопрос с уже принятым ответом.

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

Гамильтонову задачу можно свести к следующему:

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

Учитывая график, из которого нам нужно решить, существует ли гамильтонов путь или нет, мы просто передаем его в том виде, в каком он есть, для рассматриваемого алгоритма задачи, устанавливая веса ребер = 1. Если алгоритм возвращает значение> n-1 , тогда в исходном графе нет гамильтонова пути, иначе есть.

Так что эта проблема NP-Hard.