> Необходимо найти минимальный путь соединяющий данную точку со всеми > остальными, которых порядка 10 000. > Точки заданы кординатами на плоскости >
Алгоритм Дейкстры?
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
_>Помогите советом, если кто-нибудь сталкивался...
_>Необходимо найти минимальный путь соединяющий данную точку со всеми остальными, которых порядка 10 000. _>Точки заданы кординатами на плоскости
_>Подскажите алгоритм который лучше других справится с данной задачей, естественно нужен не идеальный путь а лишь приближённый.
Достаточно просто доказывается тот факт, что жадный алгоритм (каждый раз берем ближайшую точку), строит путь не длинее 2 раз по сравнению с оптимальным.
Мне когда-то приходилось использовать код, написанный Keld Helsgaun (http://www.akira.ruc.dk/~keld/), код рулит Рекомендую.
Здравствуйте, Den Raskovalov, Вы писали:
DR>Достаточно просто доказывается тот факт, что жадный алгоритм (каждый раз берем ближайшую точку), строит путь не длинее 2 раз по сравнению с оптимальным.
Первое что мне пришло в голову это этот алгоритм
Но хочется чего-то ещё...
DR>Мне когда-то приходилось использовать код, написанный Keld Helsgaun (http://www.akira.ruc.dk/~keld/), код рулит Рекомендую.
DR>>Достаточно просто доказывается тот факт, что жадный алгоритм (каждый раз берем ближайшую точку), строит путь не длинее 2 раз по сравнению с оптимальным.
_>Первое что мне пришло в голову это этот алгоритм _>Но хочется чего-то ещё...
Геометрический случай TSP (когда есть неравенство треугольника) очень хорошо исследован.
Неплохо работают генетические алгоритмы, если их заточить прямыми руками
Еще рулят разные вариации локальной оптимизации (строим жадный пусть, а потом перебираем блоки по 10-20 смежных точек и там что-то перебираем).
Здравствуйте, Den Raskovalov, Вы писали:
DR>Геометрический случай TSP (когда есть неравенство треугольника) очень хорошо исследован.
неравенство треугольника — Это что?
DR>Неплохо работают генетические алгоритмы, если их заточить прямыми руками
Ага проверю заодно степень прямоты моих рук
DR>Еще рулят разные вариации локальной оптимизации (строим жадный пусть, а потом перебираем блоки по 10-20 смежных точек и там что-то перебираем).
Здравствуйте, 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>Не приходилось, но прога реализующая его осталась (с исходниками)!!!
Рекомендую.
