_>Помогите советом, если кто-нибудь сталкивался...
_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000. _>Точки заданы кординатами на плоскости
_>Подскажите алгоритм который лучше других справится с данной задачей, естественно нужен не идеальный путь а лишь приближённый.
Достаточно просто доказывается тот факт, что жадный алгоритм (каждый раз берем ближайшую точку), строит путь не длинее 2 раз по сравнению с оптимальным.
Мне когда-то приходилось использовать код, написанный Keld Helsgaun (http://www.akira.ruc.dk/~keld/), код рулит Рекомендую.
Здравствуйте, gid_vvp, Вы писали:
W>>Кстати, испольуя МОД можно быстро построить путь, который будет максимум в полтора раза длиннее оптимального (если надо, могу рассказать, как).
_>Да, интересно узнать.
Строим МОД. Дальше будем избавляться от вершин нечётной степени (их обязательно чётное число). Строим граф из вершин нечётной степени. Вес ребра Cij — мин. путь i -> j. Так как у нас точки на плоскости, мы можем сразу взять Cij = sqrt((xi — xj)^2 + (yi — yj)^2); строим совершенные паросочетания минимального веса. Рёбра паросочетания добавляем в остовное дерево. Получаем, цикл, проходящий через все вершины графа, возможно несколько раз. Длина цикла = длина МОД + длина паросочетаний <= 1,5 длина МОД <= 1.5 длина оптимального решения. Дальше можно пропустить вершины, которые уже посещали, и получим решение.
DR>>Достаточно просто доказывается тот факт, что жадный алгоритм (каждый раз берем ближайшую точку), строит путь не длинее 2 раз по сравнению с оптимальным.
_>Первое что мне пришло в голову это этот алгоритм _>Но хочется чего-то ещё...
Геометрический случай TSP (когда есть неравенство треугольника) очень хорошо исследован.
Неплохо работают генетические алгоритмы, если их заточить прямыми руками
Еще рулят разные вариации локальной оптимизации (строим жадный пусть, а потом перебираем блоки по 10-20 смежных точек и там что-то перебираем).
Здравствуйте, gid_vvp, Вы писали:
_>Да всё идёт к нему: генетическому алгоритму... _>Может есть ещё варианты?
на самом деле, если сравнивать с другими алгоритмами, ГА дает весьма неплохой результат, особенно если время критично. _>Попробую сформулировать чётко: _>1. На плоскости расположено 10000 точек, их расположение задано координатами (в декартовой системе координат) _>2. Необходимо, начиная с некоторой наперёд заданной точки, обойти всё 10000 точек таким образом, чтобы путь оказался наименьшим.
ну тогда и нет разницы, с какой именно точки обходить _>Но в алгоритме Литла, помоему, как-то оценивается минимальный путь... _>Вот и хотелось бы узнать на сколько точно это и возможно ли вообще?
имхо — только реализовать несколько алгоритмов и сравнивать. сам я давно хочу написать развернутую статью по сравнению алгоритмов для решения задачи коммивояжера, причем я очень надеюсь, что ГА там будет одним из лучщих
но все времени не хватает _>Хотя Вы уже ответели что нет. _>Может кто-нибудь ещё скажет?
емэйл дай. пришлю свою древнюю дурацкую статью (на 2м курсе писал про решение TSP ГА. кое чем может поможет при реализации
Здравствуйте, Den Raskovalov, Вы писали:
DR>Геометрический случай TSP (когда есть неравенство треугольника) очень хорошо исследован.
неравенство треугольника — Это что?
DR>Неплохо работают генетические алгоритмы, если их заточить прямыми руками
Ага проверю заодно степень прямоты моих рук
DR>Еще рулят разные вариации локальной оптимизации (строим жадный пусть, а потом перебираем блоки по 10-20 смежных точек и там что-то перебираем).
Привет
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.
> Необходимо найти минимальный путь соединяющий данную точку со всеми > остальными, которых порядка 10 000. > Точки заданы кординатами на плоскости >
Алгоритм Дейкстры?
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Den Raskovalov, Вы писали:
DR>Достаточно просто доказывается тот факт, что жадный алгоритм (каждый раз берем ближайшую точку), строит путь не длинее 2 раз по сравнению с оптимальным.
Первое что мне пришло в голову это этот алгоритм
Но хочется чего-то ещё...
DR>Мне когда-то приходилось использовать код, написанный Keld Helsgaun (http://www.akira.ruc.dk/~keld/), код рулит Рекомендую.
Здравствуйте, Den Raskovalov, Вы писали:
DR>>>Геометрический случай TSP (когда есть неравенство треугольника) очень хорошо исследован.
_>>неравенство треугольника — Это что?
DR>Для любых точек A, B, C ( |AB|+|BC| >= |AC| )
> Насколько я понял, этот алгоритм не даёт путь который включает ВСЕ > точки, а только лишь наименьший путь между двумя через некоторе число > точек >
Он даёт наикратчайшее расстояние от одной вершины графа до всех остальных!!!
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Stanky, Вы писали:
>> Насколько я понял, этот алгоритм не даёт путь который включает ВСЕ >> точки, а только лишь наименьший путь между двумя через некоторе число >> точек >> S>Он даёт наикратчайшее расстояние от одной вершины графа до всех остальных!!!
А как у него со временем работы?
на 10 000 точках? если приходилось?
> А как у него со временем работы? >
Я уж не помню — глянь сам!!!
> на 10 000 точках? если приходилось? >
Не приходилось, но прога реализующая его осталась (с исходниками)!!!
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Stanky, Вы писали:
>> А как у него со временем работы? >> S>Я уж не помню — глянь сам!!!
>> на 10 000 точках? если приходилось? >> S>Не приходилось, но прога реализующая его осталась (с исходниками)!!!
Здравствуйте, Stanky, Вы писали:
>> Есть ли способы оценить длинну этого самого наименьшего пути, не находя >> сам путь? >> S>А можно как-то поконкретней?
Конечно можно
Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего пути и теперь неплохо было бы знать на сколько он хуже идеального...
> Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего > пути и теперь неплохо было бы знать на сколько он хуже идеального... >
Наверное я не выспался, так как вообще не понимаю тебя!!!
Кто хуже? Какого идеального?
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Stanky, Вы писали:
>> Вот реализовал я алгоритм какой-нибудь для нахождения этого наименьшего >> пути и теперь неплохо было бы знать на сколько он хуже идеального... >> S>Наверное я не выспался, так как вообще не понимаю тебя!!! S>Кто хуже? Какого идеального?
Я сам невыспался.
Чтобы знать на сколько путь найденный каким-либо приближённым алгоритмом длиннее идеального наименьшего пути мне надо знать длинну идеального пути(самого короткого из всех возможных) пути.
Вот и хочется узнать есть ли способы узнать длинну этого самого короткого пути
> Ему памяти нехватает. > Кушает 400 Мб и ещё просит >
А ты думал массив из воздуха браться будет?
Ну даже 400 метров не так уж и много — у нас в распоряжении почти 2ГБ!!! Я создавал массивы и 16384 * 16384!!!
А реально ли нужен массив 10000 * 10000? Например если граф неориентированный, то можно получить экономию в 2 раза, если массив сильно разреженый, то так же можно исхитриться!!!
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Я ж понимаю
S>Ну даже 400 метров не так уж и много — у нас в распоряжении почти 2ГБ!!! Я создавал массивы и 16384 * 16384!!! S>А реально ли нужен массив 10000 * 10000? Например если граф неориентированный, то можно получить экономию в 2 раза, если массив сильно разреженый, то так же можно исхитриться!!!
Дело в том что в этом моём графе получается что все вершины соеденины со всеми
> Дело в том что в этом моём графе получается что все вершины соеденины > со всеми >
Ну и в чём проблема-то?
Кстати ты так и не ответил: граф ориентированный?
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Stanky, Вы писали:
>> Дело в том что в этом моём графе получается что все вершины соеденины >> со всеми >> S>Ну и в чём проблема-то? S>Кстати ты так и не ответил: граф ориентированный?
похоже что он направленый, у него все рёбра ориентированы
и т.к. все вершины связаны со всеми то алгоритм Дейкстры выдаёт путь от выршины к вершине напрямую, без захода во все остальные. необходимо же чтобы получался путь из одной точки в другую с заходом во все имеющеися точки
> и т.к. все вершины связаны со всеми то алгоритм Дейкстры выдаёт путь от > выршины к вершине напрямую, без захода во все остальные. >
Нафига он тогда такой красивый нужен?
Ты вообще програмулину, что я тебе кинул запускал?
Там всё очень наглядно можно посмотреть!!!
Например имеем (в хорошем смысле) матрицу стоимости:
В строке хранятся расстояния от вершины с номером строки до вершины с номером столбца, -1 — означает, что вершина недостижима!!!
Например: расстояние от 0-й вершины, до 1-й равно 10, а вот из 1-й в 0-ю попасть нельзя (-1)!!!
Ну дык вот, алгоритм Дейкстры для данной матрицы стоимости выдаст такой результат (идём от 0-й ко всем остальным):
Привет
_>Помогите советом, если кто-нибудь сталкивался...
_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000. _>Точки заданы кординатами на плоскости
Во избежании дальнейшей путанницы автору предагается четко описать стоящую перед ним задачу. Очень желательно с примерами.
Здравствуйте, gid_vvp, Вы писали:
_>про задачу коммивояжера знаю, но интересует именно задача с таким огромным чилом пунктов.
от увеличения количества пунктов задача коммивояжера ну никак не становится другой задачей.
сформулирована она нечетко и, если это все-таки задача коммивояжера с таким огромным числом пунктов, то я бы все-таки порекомендовал использовать генетический алгоритм.
по поводу оценки приближенного решения — никак только сравнивать с другими же приближенными. точного решения задачи коммивояжера для 10000 пунктов ты не найдешь никогда
Здравствуйте, bipka, Вы писали:
B>от увеличения количества пунктов задача коммивояжера ну никак не становится другой задачей.
Полностью согласен
B>сформулирована она нечетко и, если это все-таки задача коммивояжера с таким огромным числом пунктов, то я бы все-таки порекомендовал использовать генетический алгоритм.
Да всё идёт к нему: генетическому алгоритму...
Может есть ещё варианты?
Попробую сформулировать чётко:
1. На плоскости расположено 10000 точек, их расположение задано координатами (в декартовой системе координат)
2. Необходимо, начиная с некоторой наперёд заданной точки, обойти всё 10000 точек таким образом, чтобы путь оказался наименьшим.
B>по поводу оценки приближенного решения — никак
Жаль, конечно...
Но в алгоритме Литла, помоему, как-то оценивается минимальный путь...
Вот и хотелось бы узнать на сколько точно это и возможно ли вообще?
Хотя Вы уже ответели что нет.
Может кто-нибудь ещё скажет?
B>только сравнивать с другими же приближенными. точного решения задачи коммивояжера для 10000 пунктов ты не найдешь никогда
Здравствуйте, Den Raskovalov, Вы писали:
DR>Во избежании дальнейшей путанницы автору предагается четко описать стоящую перед ним задачу. Очень желательно с примерами.
Здравствуйте, Stanky, Вы писали:
S>Нафига он тогда такой красивый нужен? S>Ты вообще програмулину, что я тебе кинул запускал? S>Там всё очень наглядно можно посмотреть!!!
Здравствуйте, bipka, Вы писали:
B>имхо — только реализовать несколько алгоритмов и сравнивать. сам я давно хочу написать развернутую статью по сравнению алгоритмов для решения задачи коммивояжера, причем я очень надеюсь, что ГА там будет одним из лучщих B>но все времени не хватает
Надеюсь пару штук реализую.
B>емэйл дай. пришлю свою древнюю дурацкую статью (на 2м курсе писал про решение TSP ГА. кое чем может поможет при реализации
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) и применим для графов с неравенством треугойника.
Здравствуйте, 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: гамильтонов путь (цикл) минимального веса. Если число точек огромно, необходимо использовать эвристики, например, тот же жадный алгоритм.
Рекомендую.
