在前面關於航空公司路線的問題上擴展

Question

THIS是我所指的問題。如果用戶未指定路線中的停靠點數量，那麼給出的答案有效，但如果停靠點/連接的數量由用戶明確指定，該解決方案將如何改變？所以它不會像最優路線問題那麼多（儘管它仍然是），它將更多地沿着尋找具有完全N個停止點（節點）的路線，同時仍然有些優化。

Answer 1

不幸的是，這個問題被稱爲NP-hard，從Hamiltonian path problem減少。這意味着，如果你確實想要解決找到最短路徑的問題，那就是N次停止（當然，假設你不需要任何週期），那麼你可能不應該期望得到一個算法那是N中的多項式。