Нециклический путь ко всем узлам

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


graph algorithm shortest-path graph-theory traveling-salesman
person Jon    schedule 01.03.2010    source источник
comment
График взвешенный или нет? Как A - ›B -› C - ›A может быть кратчайшим путем? Если только у вас не будет отрицательных затрат A - ›B -› C всегда будет короче ...   -  person IVlad    schedule 02.03.2010
comment
Извините - да, график взвешенный и ненаправленный. Причина, по которой он может быть короче, заключается в том, что у вас могут быть A, B, C и D такие, что есть ребра: A ‹- [3] -› B [3], B ‹- [5] -› C, A ‹- [3] - ›C, B‹ - [15] - ›D и A‹ - [5] - ›D. В этом случае (неуникальный) оптимальный путь будет A - ›B -› C - ›A -› D.   -  person Jon    schedule 02.03.2010

Ответы (2)


arrow_upward
9
arrow_downward

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

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

person Larry    schedule 01.03.2010
comment
Вики на этот раз ошибается как минимум наполовину. Рассмотрим взвешенный граф 1 - ›2 (1), 1 -› 3 (1), 1 - ›4 (1), 2 -› 3 (1000). Если мы можем посетить город более одного раза, оптимальный инструмент позволит избежать края 2 - ›3 стоимости 1000, поэтому мы можем сделать, например, 2 -› 1 - ›3 -› 1 - ›4. Или я что-то упустил? - person IVlad; 02.03.2010
comment
Что ж, тогда это ответ на этот вопрос. - person Jon; 02.03.2010
comment
Ваш пример не удовлетворяет неравенству треугольника, которое подразумевается различием плоского случая. - person Larry; 02.03.2010
comment
Кроме того, я думаю, что это просто более узкий случай, когда оптимальное легко визуализировать, а не то, что это доказательство правильности утверждения (поскольку он не работает для планарного TSP, это не означает, что он не работает для всех TSP). - person Larry; 02.03.2010

arrow_upward
3
arrow_downward

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

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

Проблема гамильтонова пути сводится к следующему:

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

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

Итак, это проблема NP-Hard.

person Community    schedule 02.03.2010
comment
Спасибо - это поможет объяснить проблему дальше. - person Jon; 02.03.2010