Здравствуйте, можете подсказать какой-то не особо заумный алгоритм оптимизации машрута! Если детальней описать проблему, то у меня имеется какой-то маршрут, и я знаю все расстояния между каждой точкой и всеми остальными. В результате мне нужно получить длину маршрута меньше, чем была до того, как мы его оптимизировали. То есть обход по тем же точкам должен получиться меньше по общей длине маршрута. Как вообще сравнивать между собой ближайшие точки, есть ли какая-то теорема что ли, которая позволяет сделать меньше затрат в операциях и, следовательно, в коде, или нужно изобретать свой велосипед? Мне нужно будет реализовать это на Java.
2 ответа
Описанная Вами задача идеально подходит под алгоритм поиска минимального остовного дерева. Все точки представте в виде вершин графа, пути между точками - ребра графа. Вес каждого ребра - это расстояние между точками. Далее применяете алгоритм поиска минимального остовного дерева, мне больше всего нравиться Крускал с системой непересекающихся множеств. Можете также погуглить "минимальное остовное дерево".
UPD: Все наврал, описанная задача - задача коммивояжёра
-
-
1Мне кажется, что тут скорее задача комивояжера, т.к. требуется найти именно путь (обход)– dzhioev27 фев 2012 в 15:38
-
да, когда ответили что первая и последняя совпадают, сам понял ) 27 фев 2012 в 15:39
-
1да, это действительно будет задача коммивояжера в замкнутом виде, ну а идею с графом можете взять свыше) 27 фев 2012 в 15:48
-
Ну я так почитал, сделал такие выводы! Так как у меня маршрут может состоять больше чем с 5 точек, то алгоритм комивояжера не подходит, потомучто он будет очень долго перебирать все варианты... А алгоритм Краскала расчитан для незамкнутых графов-это во первых, во вторых, может я не правильно понял, но мне кажется, что ребра, оптимизированных с его помощью маршрутов, будут пересекаться, а мне это никак не подходит!!! Скажите, пожалуйста где я туплю или другой какой-то выход!!!– 13th1327 фев 2012 в 19:57
Рекомендую начать с алгоритма дейкстры, он проще в понимании: дейкстра на википедии
-
Да я уже и сам понял что проще, читай коментарий мой выше! Он наверное скрыт был, поэтому ты не видел, но все равно СПАСИБО!!)))– 13th1327 фев 2012 в 22:36