Есть ли алгоритм или набор алгоритмов, которые позволят вам найти кратчайшее расстояние ходьбы от произвольного начального узла, чтобы каждый узел посещался в весовом неориентированном графе? Это не совсем Traveling Salesman, потому что меня не волнует, посетил ли узел несколько раз. (Не имеет значения, верните ли вы его к началу - ходок может оказаться в каком-то отдаленном узле, пока он был последним, нужно было посетить все узлы.) Это не совсем минимальное остовное дерево, потому что может быть, что переход A -> B -> C -> A -> D является (неповторимым) кратчайшим путем для посещения A, B, C и D. Моя интуиция говорит, что это не " t довольно NP проблема, потому что у нее нет ограничений, которые делают проблемы NP настолько сложными. Я мог бы, конечно, быть совершенно неправым.Непериодический путь ко всем узлам
ответ
Из статьи Википедии на Travelling Salesman Problem:
Удаление условия посещения каждого города «только один раз» не удаляет NP-твердость, так как легко видеть, что в плоском случае существует оптимальный тур который посещает каждый город только один раз (иначе, по неравенству треугольника, ярлык, который пропускает повторный визит, не увеличивал длину тура).
На этот раз Wiki по крайней мере наполовину ошибается. Рассмотрим взвешенный граф 1 -> 2 (1), 1 -> 3 (1), 1 -> 4 (1), 2 -> 3 (1000). Если мы сможем посетить город более одного раза, оптимальный инструмент позволит избежать края 2 -> 3 стоимостью 1000, поэтому мы можем сделать, например, 2 -> 1 -> 3 -> 1 -> 4. Или я чего-то не хватает? – IVlad
Ну, тогда это отвечает. – Jon
Ваш пример не удовлетворяет «неравенству треугольника», что подразумевается разграничением «планарного случая». – Larry
Не уверен, что этикет должен добавить ответ на вопрос с уже принятым ответом.
Я добавляю этот ответ только ради того, чтобы не переходить на другую страницу, чтобы не иметь дело с планарными графами и неравенством треугольника и тем, что это просто и, вероятно, легче понять.
гамильтонова проблема Путь может быть сведена к следующему:
Предположим, что мы имели полиномиальный алгоритм времени, чтобы решить нашу задачу о нахождении наименьшего веса ходить, который посещает все вершины.
Для определения графа, которому мы должны решить путь гамильтониана, существует или нет, мы просто передаем его, как есть, к алгоритму задачи под рукой, задав вес по краям = 1. Если алгоритм возвращает значение> n- 1, то в исходном графе нет гамильтонова траектории, иначе существует.
Так что эта проблема NP-Hard.
Спасибо - это помогает объяснить проблему дальше. – Jon
- 1. C# доступ ко всем узлам html
- 2. Найти узел по отношению ко всем узлам в коллекции
- 3. Доступ ко всем узлам в элементе управления TreeView
- 4. шаблон XSL матч шаблон применяется ко всем дочерним узлам
- 5. Валидатор Deform/Colander, который имеет доступ ко всем узлам?
- 6. Как выбрать узел, ближайший ко всем другим узлам в графе?
- 7. Drupal 6 - Как отключить комментарии ко всем узлам/content_types?
- 8. Я хочу иметь действие ко всем узлам treeview
- 9. Найти узел, который подключен ко всем узлам запуска
- 10. Как добавить данные ко всем листовым узлам карты clojure?
- 11. Поиск совпадений со всех узлов ко всем узлам в Neo4j
- 12. Алгоритм, чтобы найти путь ко всем городам
- 13. Самый быстрый путь для прохождения по всем заданным узлам
- 14. Предоставление уникальных идентификаторов всем узлам?
- 15. xslt соответствует всем узлам, кроме определенного
- 16. Поиск минимального количества туров по всем узлам
- 17. итерация по всем узлам файла xml
- 18. Neo4J: Cypher для поиска по всем узлам и всем свойствам
- 19. Правило Dom4j не соответствует всем ожидаемым узлам
- 20. javascript динамически добавлять относительный путь ко всем ссылкам
- 21. Алгоритмы находят самый короткий путь ко всем ячейкам на сетке
- 22. Использование Linq To XML, способ получить путь ко всем листьям?
- 23. Подключение ко многим узлам выхода TOR
- 24. Зачем добавлять кластерные ключи указателя ко всем (промежуточным) узлам в NCI?
- 25. Алгоритм для генерации неориентированного графа с путями ко всем узлам с максимальной степенью?
- 26. Добавление атрибута ко всем узлам, соответствующим выражению XPATH, с использованием Oracle XML DB
- 27. Как добавить дочерний элемент ко всем узлам с указанным именем класса, используя чистый javascript
- 28. MySQL - Как получить доступ ко всем узлам уровня 2 в таблице
- 29. Как предоставить доступ для чтения/записи ко всем узлам с правилами Firebase?
- 30. Узлы соответствия Cypher, которые имеют отношения ко всем узлам, соответствующим некоторым критериям
Граф взвешен или нет? Как А -> В -> С -> А - кратчайший путь? Если у вас не может быть отрицательных издержек, A -> B -> C всегда будет короче ... – IVlad
Извините - да, график взвешен и неориентирован. Причина, по которой это может быть короче, состоит в том, что у вас могут быть 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. – Jon