Продолжая предыдущий вопрос о маршрутизации авиакомпаний

Question

ЭТО - это вопрос, который я имел в виду. Ответ, данный там, работает, если количество остановок на маршруте не указано пользователем, но как это решение изменится, если количество остановок / соединений должно быть явно указано пользователем? Таким образом, это не было бы такой же проблемой оптимального маршрута (хотя это все еще есть), это было бы больше по линии нахождения маршрута с ТОЧНО N остановками (узлами) в нем, в то же время все еще будучи несколько оптимальным.

Answer 1

К сожалению, эта проблема является NP-трудной из-за сокращения от задачи о гамильтоновом пути .Это означает, что если вы действительно хотите решить проблему поиска кратчайшего пути, который делает ровно N остановок (при условии, конечно, что вам не нужны циклы), то вам, вероятно, не стоит ожидать получения алгоритмаэто полином по Н.