Что-то я запутался, вот подскажите, пожалуйста — если кто-то университетскую программу ещё помнит )) Имеется ненаправленный, невзвешенный граф, в котором около 8,500 вершин и 14,000 рёбер. Как называется алгоритм нахождения кратчайшего пути, проходящего через заданное подмножество вершин (порядок которых не важен) и начинающийся в одной заданной вершине? Требования замкнутости пути (то есть возвращения в начало) НЕ имеется.
Здравствуйте, Firstborn, Вы писали:
F>Что-то я запутался, вот подскажите, пожалуйста — если кто-то университетскую программу ещё помнит )) Имеется ненаправленный, невзвешенный граф, в котором около 8,500 вершин и 14,000 рёбер. Как называется алгоритм нахождения кратчайшего пути, проходящего через заданное подмножество вершин (порядок которых не важен) и начинающийся в одной заданной вершине? Требования замкнутости пути (то есть возвращения в начало) НЕ имеется.
Задача коммивояжера что ли (незамкнутая)? Это разве не классическая NP-полная задача, где нормального решения не существует, только эвристики?
Здравствуйте, bnk, Вы писали:
bnk>Здравствуйте, Firstborn, Вы писали:
F>>Что-то я запутался, вот подскажите, пожалуйста — если кто-то университетскую программу ещё помнит )) Имеется ненаправленный, невзвешенный граф, в котором около 8,500 вершин и 14,000 рёбер. Как называется алгоритм нахождения кратчайшего пути, проходящего через заданное подмножество вершин (порядок которых не важен) и начинающийся в одной заданной вершине? Требования замкнутости пути (то есть возвращения в начало) НЕ имеется.
bnk>Задача коммивояжера что ли (незамкнутая)? Это разве не классическая NP-полная задача, где нормального решения не существует, только эвристики?
Так вот вроде не то. Задача коммивояжёра обходит все вершины графа, а мне нужно обойти только небольшое подмножество
Здравствуйте, Firstborn, Вы писали:
bnk>>Задача коммивояжера что ли (незамкнутая)? Это разве не классическая NP-полная задача, где нормального решения не существует, только эвристики?
F>Так вот вроде не то. Задача коммивояжёра обходит все вершины графа, а мне нужно обойти только небольшое подмножество
А не сводится ли эта задача к задаче коммивояжера? Создадим новый граф из этого небольшого подмножества
и ребер которые соединяют только это вершины этого подмножества.
Плюс добавим все кратчайшие пути для каждой пары из подмножества,
такие что не проходят через вершины подмножества. Эти пути будут
дополнительными ребрами в новом графе.
После этого останется решить задачу коммивояжера для нового графа,
чтобы решить исходную?
Здравствуйте, Zhendos, Вы писали:
Z>После этого останется решить задачу коммивояжера для нового графа,
Чтобы показать NP-полноту обсуждаемой задачи, нужно делать ровно наоборот — нужно сводить задачу коммивояжера к обсуждаемой задаче (а не обсуждаемую задачу к задаче коммивояжера).
1. Возьмем какую-нибудь задачу коммивояжера. Добавим любое количество вершин, и любые смежные им ребра.
2. Решаем для получившегося графа обсуждаемую задачу. При этом в качестве вершин которые нужно посетить выберем вершины из задачи коммивояжера.
3. Если существует решения обсуждаемой задачи за P, то существует и решение коммивояжера за P.
В общем, обсуждаемая задача и задача коммивояжера лежит в одном классе — NP.
Здравствуйте, Firstborn, Вы писали:
F>Что-то я запутался, вот подскажите, пожалуйста — если кто-то университетскую программу ещё помнит )) Имеется ненаправленный, невзвешенный граф, в котором около 8,500 вершин и 14,000 рёбер. Как называется алгоритм нахождения кратчайшего пути, проходящего через заданное подмножество вершин (порядок которых не важен) и начинающийся в одной заданной вершине? Требования замкнутости пути (то есть возвращения в начало) НЕ имеется.
Ну, казалось бы, Волновой алгоритм Ли должен легко обобщаться для решения этой задачи...
Здравствуйте, Firstborn, Вы писали:
F>Что-то я запутался, вот подскажите, пожалуйста — если кто-то университетскую программу ещё помнит )) Имеется ненаправленный, невзвешенный граф, в котором около 8,500 вершин и 14,000 рёбер. Как называется алгоритм нахождения кратчайшего пути, проходящего через заданное подмножество вершин (порядок которых не важен) и начинающийся в одной заданной вершине? Требования замкнутости пути (то есть возвращения в начало) НЕ имеется.
1. строишь новый граф из подмножества вершин с имеющимися ребрами
2. раз граф не взвешенный, то ставим вес 1 там где есть ребро, и бесконечность там где нет, получаешь матрицу весов
3. решаешь задачу коммивояжера. Для того чтобы учесть условие, что возвращаться не надо, добавляешь вершину, которая имеет связь со всеми, а вес ребра с нужной начальной ставишь 0.
Здравствуйте, Firstborn, Вы писали:
F>Что-то я запутался, вот подскажите, пожалуйста — если кто-то университетскую программу ещё помнит )) Имеется ненаправленный, невзвешенный граф, в котором около 8,500 вершин и 14,000 рёбер. Как называется алгоритм нахождения кратчайшего пути, проходящего через заданное подмножество вершин (порядок которых не важен) и начинающийся в одной заданной вершине? Требования замкнутости пути (то есть возвращения в начало) НЕ имеется.
Не понимаю, почему большинство так топит за коммивояжёра, у которого постановка задачи, мягко говоря, немножко не такая.
У меня подозрение, что либо подойдёт итеративный поиск пути от начала до всех промежуточных, выбор наилучшего, далее повторять от найденной наилучшей промежуточной цели пока есть другие промежуточные (но может быть вариант когда найденный порядок всё равно не оптимальный), либо же какой-то итеративный перебор на основе симплекс-метода:
Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи[1]. Примеры таких задач:
Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теории исследования операций[2].
