1

Здравствуйте, можете подсказать какой-то не особо заумный алгоритм оптимизации машрута! Если детальней описать проблему, то у меня имеется какой-то маршрут, и я знаю все расстояния между каждой точкой и всеми остальными. В результате мне нужно получить длину маршрута меньше, чем была до того, как мы его оптимизировали. То есть обход по тем же точкам должен получиться меньше по общей длине маршрута. Как вообще сравнивать между собой ближайшие точки, есть ли какая-то теорема что ли, которая позволяет сделать меньше затрат в операциях и, следовательно, в коде, или нужно изобретать свой велосипед? Мне нужно будет реализовать это на Java.

3
  • А все точки маршрута надо использовать?
    – dzhioev
    27 фев 2012 в 15:28
  • ну да, начальная и конечная - одинаковые, то есть это одна и та же точка
    – 13th13
    27 фев 2012 в 15:35
  • Учи мат.часть :) Это дискретная математика :) 27 фев 2012 в 17:30

2 ответа 2

2

Описанная Вами задача идеально подходит под алгоритм поиска минимального остовного дерева. Все точки представте в виде вершин графа, пути между точками - ребра графа. Вес каждого ребра - это расстояние между точками. Далее применяете алгоритм поиска минимального остовного дерева, мне больше всего нравиться Крускал с системой непересекающихся множеств. Можете также погуглить "минимальное остовное дерево".

UPD: Все наврал, описанная задача - задача коммивояжёра

6
  • ага, спасибо, похоже на правду)) ща почитаю
    – 13th13
    27 фев 2012 в 15:36
  • 1
    Мне кажется, что тут скорее задача комивояжера, т.к. требуется найти именно путь (обход)
    – dzhioev
    27 фев 2012 в 15:38
  • да, когда ответили что первая и последняя совпадают, сам понял ) 27 фев 2012 в 15:39
  • 1
    да, это действительно будет задача коммивояжера в замкнутом виде, ну а идею с графом можете взять свыше) 27 фев 2012 в 15:48
  • Ну я так почитал, сделал такие выводы! Так как у меня маршрут может состоять больше чем с 5 точек, то алгоритм комивояжера не подходит, потомучто он будет очень долго перебирать все варианты... А алгоритм Краскала расчитан для незамкнутых графов-это во первых, во вторых, может я не правильно понял, но мне кажется, что ребра, оптимизированных с его помощью маршрутов, будут пересекаться, а мне это никак не подходит!!! Скажите, пожалуйста где я туплю или другой какой-то выход!!!
    – 13th13
    27 фев 2012 в 19:57
0

Рекомендую начать с алгоритма дейкстры, он проще в понимании: дейкстра на википедии

1
  • Да я уже и сам понял что проще, читай коментарий мой выше! Он наверное скрыт был, поэтому ты не видел, но все равно СПАСИБО!!)))
    – 13th13
    27 фев 2012 в 22:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.