А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.

Можно ли сделать это неэвристически и чтоб не за O(N!) по времени было?

Кстати, граф можно считать неизменным, потому если можно уменьшить время выполнения за счёт каких-то предварительных подсчётов — это тоже вариант.

Здравствуйте, Firstborn, Вы писали:

F>А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.

F>Можно ли сделать это неэвристически и чтоб не за O(N!) по времени было?

Частный случай задачи коммивояжера. Также является NP-полной.
Т.е. эффективного неэвристического решения нет (не известно).

Основные алгоритмы описаны в вики

F>Кстати, граф можно считать неизменным, потому если можно уменьшить время выполнения за счёт каких-то предварительных подсчётов — это тоже вариант.

Зависит от эвристического алгоритма

Здравствуйте, Firstborn, Вы писали:

F>А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.

Задача коммивояжёра?

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, Firstborn, Вы писали:

F>>А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.

Pzz>Задача коммивояжёра?
Ну почти, только (а) нет требования закончить обход там же, где и начал (т.е. это, видимо, "незамкнутый варианты задачи"), (б) обойти нужно не весь граф, а только очень небольшое подмножество вершин и (в) нет требования заходить в каждую вершину из целевого подмножества только единожды. Была надежда, что вдруг есть какое-то решение для такого частного случая, но выглядит так, что не особо...

Здравствуйте, Firstborn, Вы писали:

Я генетическим алгоритмом похожую штуку реализовывал

Здравствуйте, Буравчик, Вы писали:

F>>Кстати, граф можно считать неизменным, потому если можно уменьшить время выполнения за счёт каких-то предварительных подсчётов — это тоже вариант.
Б>Зависит от эвристического алгоритма

Вот подумываю сделать так:

1. Просчитать заранее матрицу расстояний от каждой вершины к каждой
   
2. Перебирать как-нибудь эвристически перестановки из подмножества "посещаемых" вершин, минимизируя длинну суммарного пути (который будет добываться из матрицы расстояний за O(1))

Здравствуйте, Firstborn, Вы писали:

F>А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.
F>Можно ли сделать это неэвристически и чтоб не за O(N!) по времени было?
Нет.

F>Кстати, граф можно считать неизменным, потому если можно уменьшить время выполнения за счёт каких-то предварительных подсчётов — это тоже вариант.

https://youtu.be/GiDsjIBOVoA
Тут достаточно полная инфа по возможным алгоритмам, но они все неточные.

Здравствуйте, Нomunculus, Вы писали:

Н>Здравствуйте, Firstborn, Вы писали:

Н>Я генетическим алгоритмом похожую штуку реализовывал
Была именно такая мысль. Вот только мне не удалось придумать как осмысленно реализовать половое размножение среди перестановок "обходимых" вершин (которые по сути и являются возможными решениями)... а если оставить одну лишь мутацию (случайную перемену местами двух элементов в перестановке), то это уже и не генетический алгоритм толком, а просто перебор с элементами случайности получается. Или я что-то тут упускаю?

Здравствуйте, Firstborn, Вы писали:

Ген — это не «путь», а «повороты». Тогда скрестить два гена не проблема

Здравствуйте, Firstborn, Вы писали:

F>А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.

Посмотрите тексты программ на 60-ти языках программирования на сайте Rossetta
10 000 эта не то количество, которое может смущать. Пробуйте реальную задачу, любой из алгоритмов должен справиться
Хороший обзор методов на страничке здесь
Konstantin