Маршрут между А и В со станциями между

Я явно скучаю по лесу сквозь деревья...

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

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

1 ответ

Решение

Вы переосмысливаете это. Есть только шесть (3*2*1) возможных путей через три промежуточных узла. Просто проверь их все.

В более крупных случаях вы можете свести свою проблему к TSP следующим образом:

Если s является начальным узлом и t последний узел, добавить ребро с нулевым весом между s а также t и бесконечно тяжелый край между s и каждый второй узел, и между t и каждый второй узел.

Проблема NP-трудна, но чрезвычайно хорошо изучена. Существует множество точных и приблизительных алгоритмов, которые вы можете изучить.

Другие вопросы по тегам