На графе дано: старт, финиш, промежуточные точки.
Нужно: найти кратчайший маршрут из старта в финиш, включающий в себя (в любом порядке) каждую из промежуточных точек.

Есть ли хороший алгоритм для решения такой задачки?
Парочка хороших кейвордов по теме тоже устроит

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

BQS>На графе дано: старт, финиш, промежуточные точки.
BQS>Нужно: найти кратчайший маршрут из старта в финиш, включающий в себя (в любом порядке) каждую из промежуточных точек.

BQS>Есть ли хороший алгоритм для решения такой задачки?
Думаю, что полиномиального алгоритма от количества промежуточных точек нет.
Запускаем алгоритм Флойда и находим кратчайшие пути между всеми парами точек. Дальше строим граф, состоящий из точки старта, финиша и промежуточных точек. Длина ребра в новом графе — кратчайшее расстояние между соответсвующими точками. Получили задачу коммивояжёра.

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

BQS>На графе дано: старт, финиш, промежуточные точки.
BQS>Нужно: найти кратчайший маршрут из старта в финиш, включающий в себя (в любом порядке) каждую из промежуточных точек.

Включающий только один раз? Это задача коммивояжера.

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

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

BQS>>На графе дано: старт, финиш, промежуточные точки.
BQS>>Нужно: найти кратчайший маршрут из старта в финиш, включающий в себя (в любом порядке) каждую из промежуточных точек.

V_>Включающий только один раз? Это задача коммивояжера.

Упс, не заметил слово "кратчайший"

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

BQS>На графе дано: старт, финиш, промежуточные точки.
BQS>Нужно: найти кратчайший маршрут из старта в финиш, включающий в себя (в любом порядке) каждую из промежуточных точек.

BQS>Есть ли хороший алгоритм для решения такой задачки?
BQS>Парочка хороших кейвордов по теме тоже устроит

Ключевые слова:
Hamiltonian path
Traveling salesman problem

Это задача нахождения гамильтоновой цепи во взвешенном графе с минимальной стоимостью. Задача является NP-трудной. Полиномиального алгоритма решения не существует.

The problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases.

Если интересует точные методы, то
— если количество вершин небольшое и есть возможность использовать O(2^n) памяти, то решается с помощью динамического программирования.
— если чуть побольше, то методом ветвей и границ
— если порядка сотен вершин, то надо использовать cutting-plane method

Если интересуют эвристические методы, то ищи эвристику Кернигана-Лина и ее многочисленные модификации.

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

_DA>- если порядка сотен вершин, то надо использовать cutting-plane method

Можно чуть поподробнее про cutting-plane method для данной задачи?
Я эту задачу на сильно разреженном графе решал методом ветвей и границ.

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

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

_DA>>- если порядка сотен вершин, то надо использовать cutting-plane method

H>Можно чуть поподробнее про cutting-plane method для данной задачи?
H>Я эту задачу на сильно разреженном графе решал методом ветвей и границ.

Вот примерное описание
http://www.tsp.gatech.edu/methods/dfj/index.html
В 2001 году с помощью этого метода был найден кратчайший гамильтонов цикл для 15112 немецких городов. На тот момент это был рекордный результат.

P.S. Сорри за долгий ответ, был небольшой отпуск