Задача немного отличается от "Задачи коммивояжера" в ее привычном понимании (где требуется обойти по кратчайшему пути все точки на графе и вернуться в исходную).
У меня есть граф (достаточно большой, есть вес каждого ребра). Некоторые ребра двунаправленные, некоторые – однонаправленные. Есть вершины с одним ребром (типа конечных ответвлений).
Задача: посетить указанный список вершин по минимальному пути. То есть заходить можно вообще в любые вершины графа, но в указанный список – посетить обязательно.
Намекните мне как это проще сделать. А то я затупил 
давно алгоритмами не занимался, все позабыл. Если есть примеры, то приму с радостью на Дельфях.
Спасибо.
3 сентября 2009 в 22:03
Я имею в виду, что оптимальное решение исходной задачи гарантированно будет получено с помощью алгоритма в #6, и что нет никакого смысла делать задачу без такого предварительного шага.
3 сентября 2009 в 22:02
минимальный путь между вершинами ищется методом дейкстры.
единственного пути в программировании не бывает. всегда остаётся старый добрый полный перебор. (поиск с возвращением), и обычно остаются всякие ноу хау как то для метода дейкстры хранить веса узлов в авл дереве…
3 сентября 2009 в 21:05
#6 +1
у меня возникла та же идея
3 сентября 2009 в 20:04
#6 +1
Более того, очевидно, что это по сути единственный способ.
3 сентября 2009 в 16:04
Можно для каждой пары нужных вершин посчитать минимальное расстояние и составить из них новый граф. А новый граф уже должен быть вполне пригоден для стандартного алгоритма.
3 сентября 2009 в 16:01
-травишь дейкстру на все узлы,
выбираешь подграф содержащий нужное множество узлов, и получаешь полный граф эквивалентный данному,
- на него уже поиск в глубину(метод ветвей и границ) O(m!).
можно конечно сразу тупо травить метод ветвей и границ, (отключив проверку в каких узлах уже был, а условие выхода это что множество нужных тебе узлов покрыто), но если граф действительно большой (узлов 15-18) это уже будет очень долго(месяцев несколько).
а чего за задача? может приближённый алгоритм нужен всё-таки?
3 сентября 2009 в 15:05
Можно построить вспомогательный граф, в котором нужно посетить все вершины по кратчайшему(но в исходную возвращаться не требуется).
Его вершины – это список заданных вершин. А дуги – кратчайшие расстояния между этими вершинами в исходном графе. Только придется искать кратчайшие пути от каждой до каждой и возможно в двух направлениях.
Если такой граф построить, то задача от коммивояжера будет отличаться только требованием "вернуться в исходную".
3 сентября 2009 в 15:00
я думал над этим, но волновой алгоритм годится для поиска минимального пути между двумя вершинами.
Но как обойти несколько заданных заранее вершин с минимальным путем – вот вопрос.
3 сентября 2009 в 14:01
волновой алгоритм тебе думаю поможет…