Маршрут между А и В со станциями между
Я явно скучаю по лесу сквозь деревья...
я знаю о проблеме коммивояжера, но есть ли другой алгоритм / проблема, которая лучше соответствует моим потребностям / описанию? Мне нужно описать мою проблему с помощью такого математического описания.
У меня до пяти баллов с известной начальной и конечной точкой. Так что мне просто нужно рассчитать кратчайший путь для посещения всех трех точек между этими двумя. Дейкстра и подобные алгоритмы пытаются найти кратчайший путь между двумя точками, поэтому здесь они, вероятно, не будут посещать все точки между ними. Или есть алгоритм, который находит кратчайший путь и посещает все точки между двумя точками?
1 ответ
Вы переосмысливаете это. Есть только шесть (3*2*1) возможных путей через три промежуточных узла. Просто проверь их все.
В более крупных случаях вы можете свести свою проблему к TSP следующим образом:
Если s
является начальным узлом и t
последний узел, добавить ребро с нулевым весом между s
а также t
и бесконечно тяжелый край между s
и каждый второй узел, и между t
и каждый второй узел.
Проблема NP-трудна, но чрезвычайно хорошо изучена. Существует множество точных и приблизительных алгоритмов, которые вы можете изучить.