Кратчайший путь, соединяющий n точек

введите здесь описание изображения

У меня есть n точек, и мне нужно соединить их все, чтобы минимизировать конечное расстояние. На изображении выше представлен алгоритм, который в каждом узле соединяется с ближайшим, но окончательный результат может быть действительно таким.

Я много искал, я знаю несколько алгоритмов поиска пути, но не знаю ни одного, который решает именно этот случай. Я нашел вопрос на Math Stackexchange, но ответ не содержит никакого алгоритма - https://math.stackexchange.com/a/581844/156584.

Есть ли алгоритм, решающий именно эту задачу? В противном случае я могу переборщить.

Правка: некоторые пояснения относительно результата, которого я ожидаю: каждый узел может быть соединен с двумя другими узлами, создавая непрерывный путь (например, взять ручку и, даже не поднимая ее, соединить узлы, сводя к минимуму конечное расстояние). Я не хочу создавать цикл (это проблема коммивояжера).

PS: этот вопрос также можно перевести как «полный граф с n вершинами и желание выбрать набор ребер таким образом, чтобы граф был связан, но сумма весов ребер минимизирована»


graph algorithm shortest-path
person andrepcg    schedule 15.10.2014    source источник
comment
полный граф с n вершинами и желание выбрать набор ребер таким образом, чтобы граф был связным, но сумма весов ребер минимизирована. Решение здесь называется minimum spanning tree, но MST и кратчайший путь Проблемы совсем другие! На всякий случай: en.wikipedia.org/wiki/Shortest_path_problem   -  person Svetlin Zarev    schedule 15.10.2014
comment
Это проблема пути коммивояжера, которая тесно связана с TSP, поскольку применимы многие из тех же методов, в частности, динамическое программирование и метод ветвления и границы.   -  person David Eisenstat    schedule 15.10.2014

Ответы (1)


arrow_upward
2
arrow_downward

Эта задача известна как задача о кратчайшем гамильтоновом пути и является NP-трудной. Поэтому, если количество точек невелико, вы можете использовать поиск с возвратом или динамическое программирование, чтобы найти оптимальное решение. Если количество точек велико, вы можете использовать эвристику и/или приближения, чтобы получить относительно хороший ответ (правда, в этом случае не всегда возможно найти лучший).

person kraskevich    schedule 15.10.2014
comment
У вас случайно нет ссылки? Мне было бы интересно. - person BLBA; 24.04.2020