алгоритм или подход к задаче пути, кратчайший путь с n точками для n <= 12

Question

у меня есть n точек на 2d плоскости, с n <= 12, и мне нужно расстояние до кратчайшего доступного пути, включая все точки, начиная с любой из них, но не делая замкнутый контур </p>

Я безуспешно пытаюсь найти Флойд-Маршала, задачу коммивояжера и другие алгоритмы.

Для моего учителя эта задача считается ПРОСТОЙ, поэтому я не думаю, что для этого потребуются приближения ароры или около того, но я не знаюКаков наилучший подход для решения этой проблемы, но, может быть, какой-то динамический алгоритм и что-то вроде

for i = 0 to n
    for j = 0 to n
    if path_distance(i,j) < mininum
        set minimum

любая помощь?

Answer 1

Если и только если n <= 12, я бы порекомендовал Алгоритм ветвления и границы , который является улучшенной версией алгоритма перебора.

Answer 2

Я предоставлю только подсказку , так как это домашняя работа:

Рекурсия очень полезна при устранении подобных проблем.

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

Answer 3

Если вы знаете, что у вас есть только двенадцать точек и вы хотите найти кратчайший путь, который посещает каждый узел ровно один раз, тогда вы всегда можете просто перебрать решение, попробовав все возможные перестановки узлов и вычислив длинупуть по этой перестановке.Это не очень хорошо масштабируется, но если у вас есть фиксированная верхняя граница для числа узлов, то это должно быть разумно.