B>имхо — только реализовать несколько алгоритмов и сравнивать. сам я давно хочу написать развернутую статью по сравнению алгоритмов для решения задачи коммивояжера, причем я очень надеюсь, что ГА там будет одним из лучщих
Это будет недостаток твоей статьи Ибо я тут приводил ссылку на замечательный сайт Keld Helsgaun на котором есть замечательный исходник, кооторый зашибительно точно решал у меня на машине TSP на 2000 вершин за примерно минуту. Ибо не может универсальный по своей сути ГА хорошо решать _конкретную_ задачу. Любая задача имеет специфику, которую универсальный ГА использовать не в состоянии.
Здравствуйте, Den Raskovalov, Вы писали:
DR>Ибо я тут приводил ссылку на замечательный сайт Keld Helsgaun
возможно все познается в сравнении.
за ссылку большое спасибо, очень полезный ресурс нашел через нее http://www.tsp.gatech.edu/ — я как раз такое искал и никак не мог найти
по поводу генетических алгоритмов ты же сам очень хорошо написал — если правильно заточить
код этого Keldа посмотрел, интересно. еще раз спасибо за ссылку
Здравствуйте, bipka, Вы писали:
B>емэйл дай. пришлю свою древнюю дурацкую статью (на 2м курсе писал про решение TSP ГА. кое чем может поможет при реализации
Здравствуйте, gid_vvp, Вы писали:
_>Hi, All.
_>Ещё вопрос возник...
_>Есть ли способы оценить длинну этого самого наименьшего пути, не находя сам путь?
Да.
Можно быстро построить минимальное остовное деревео (МОД).
Длина оптимального пути, проходящего через все вершины, будет не меньше суммы длин рёбер МОД.
Кстати, испольуя МОД можно быстро построить путь, который будет максимум в полтора раза длиннее оптимального (если надо, могу рассказать, как).
И ещё. Для Вашей задачи существует e-приближённый алгоритм. Т.е. для любой заданной точности e > 1, этот алгоритм будет за полиномиальное от количества точек время находить путь, который длинне оптимального, максимум, в e раз. Я его не знаю, но можно поискать в инете. Этот вариант будет хорош тем, что если заранее определиться с приемлимой точностью/скоростью, например, e=1.1, то можно потом быть уверенным в "качестве" получившегося пути.
Здравствуйте, What, Вы писали:
W>Да. W>Можно быстро построить минимальное остовное деревео (МОД). W>Длина оптимального пути, проходящего через все вершины, будет не меньше суммы длин рёбер МОД. W>Кстати, испольуя МОД можно быстро построить путь, который будет максимум в полтора раза длиннее оптимального (если надо, могу рассказать, как).
Да, интересно узнать.
W>И ещё. Для Вашей задачи существует e-приближённый алгоритм. Т.е. для любой заданной точности e > 1, этот алгоритм будет за полиномиальное от количества точек время находить путь, который длинне оптимального, максимум, в e раз. Я его не знаю, но можно поискать в инете. Этот вариант будет хорош тем, что если заранее определиться с приемлимой точностью/скоростью, например, e=1.1, то можно потом быть уверенным в "качестве" получившегося пути.
Здравствуйте, gid_vvp, Вы писали:
_>Hi, All.
_>Помогите советом, если кто-нибудь сталкивался...
_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000. _>Точки заданы кординатами на плоскости
_>Подскажите алгоритм который лучше других справится с данной задачей, естественно нужен не идеальный путь а лишь приближённый.
_>P.S. _>про задачу коммивояжера знаю, но интересует именно задача с таким огромным чилом пунктов.
Метод Гилмора-Гомори имеет сложность О(n log n) и применим для графов с неравенством треугойника.
Привет
C>Метод Гилмора-Гомори имеет сложность О(n log n) и применим для графов с неравенством треугойника.
Ссылку? Я встречал метод Гилмора-Гомори. Но это был метод решения целочисленной задачи о рюкзаке. А вообще мне казалось, что даже задача на плоскости с Эвклидовой метрикой NP-полна.
Euclidean TSP
Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. The problem still remains NP-hard, however many heuristics work better.
Euclidean TSP is a particular case of TSP with triangle inequality, since distances in plane obey triangle inequality. However, it seems to be easier than general TSP with triangle inequality. For any c>0, there is a polynomial time algorithm that finds a tour of length at most (1+c) times the optimal on any graph (Arora, 1997). In practice, the running time of this algorithm is too large and heuristics with weaker guarantees are used but they also perform better on instances of Euclidean TSP than on general instances.
Здравствуйте, gid_vvp, Вы писали:
W>>Кстати, испольуя МОД можно быстро построить путь, который будет максимум в полтора раза длиннее оптимального (если надо, могу рассказать, как).
_>Да, интересно узнать.
Строим МОД. Дальше будем избавляться от вершин нечётной степени (их обязательно чётное число). Строим граф из вершин нечётной степени. Вес ребра Cij — мин. путь i -> j. Так как у нас точки на плоскости, мы можем сразу взять Cij = sqrt((xi — xj)^2 + (yi — yj)^2); строим совершенные паросочетания минимального веса. Рёбра паросочетания добавляем в остовное дерево. Получаем, цикл, проходящий через все вершины графа, возможно несколько раз. Длина цикла = длина МОД + длина паросочетаний <= 1,5 длина МОД <= 1.5 длина оптимального решения. Дальше можно пропустить вершины, которые уже посещали, и получим решение.
Здравствуйте, Den Raskovalov, Вы писали:
DR>Привет
C>>Метод Гилмора-Гомори имеет сложность О(n log n) и применим для графов с неравенством треугойника.
DR>Ссылку? Я встречал метод Гилмора-Гомори. Но это был метод решения целочисленной задачи о рюкзаке. А вообще мне казалось, что даже задача на плоскости с Эвклидовой метрикой NP-полна.
Pohozhe ljapnul glupost'. U Gilmore-Gomory tam rasstojanija opredeljajutsja kak dostatochno krivye integraly, i mne pokazalos', chto evklidova metrika udovletvorjaet tem uslovijam.
Original'naja stat'ja opublikovana v 1m nomere Naval Research Logistics v 1954 godu, no tam kvadratnyj algoritm, kotoryj byl potom uluchshen. V ljuboj knizhke o TSP etot algoritm opisan. Na russkom mozhno pochitat' v knige Tanaev, Sotskov i Strusevich, "Teorija raspisanij: mnogostadijnye sistemy" ili kak-to pohozhe.
W>Строим МОД. Дальше будем избавляться от вершин нечётной степени (их обязательно чётное число). Строим граф из вершин нечётной степени. Вес ребра Cij — мин. путь i -> j. Так как у нас точки на плоскости, мы можем сразу взять Cij = sqrt((xi — xj)^2 + (yi — yj)^2); строим совершенные паросочетания минимального веса. Рёбра паросочетания добавляем в остовное дерево. Получаем, цикл, проходящий через все вершины графа, возможно несколько раз. Длина цикла = длина МОД + длина паросочетаний <= 1,5 длина МОД <= 1.5 длина оптимального решения. Дальше можно пропустить вершины, которые уже посещали, и получим решение.
Спасибо за ответ, в скором времени попробую реализовать, если что буду спрашивать.
Здравствуйте, gid_vvp, Вы писали:
_>Hi, All.
_>Помогите советом, если кто-нибудь сталкивался...
_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000. _>Точки заданы кординатами на плоскости
_>Подскажите алгоритм который лучше других справится с данной задачей, естественно нужен не идеальный путь а лишь приближённый.
_>P.S. _>про задачу коммивояжера знаю, но интересует именно задача с таким огромным чилом пунктов.
Насколько я помню, в Кормане разбирается такой алгоритм.
Здравствуйте, gid_vvp, Вы писали:
_>Hi, All.
_>Помогите советом, если кто-нибудь сталкивался...
_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000. _>Точки заданы кординатами на плоскости
_>Подскажите алгоритм который лучше других справится с данной задачей, естественно нужен не идеальный путь а лишь приближённый.
_>P.S. _>про задачу коммивояжера знаю, но интересует именно задача с таким огромным чилом пунктов.
Keyword: гамильтонов путь (цикл) минимального веса. Если число точек огромно, необходимо использовать эвристики, например, тот же жадный алгоритм.
Ибо я тут приводил ссылку на замечательный сайт Keld Helsgaun на котором есть замечательный исходник, кооторый зашибительно точно решал у меня на машине TSP на 2000 вершин за примерно минуту. Ибо не может универсальный по своей сути ГА хорошо решать _конкретную_ задачу. Любая задача имеет специфику, которую универсальный ГА использовать не в состоянии.
