都市間の旅費を最小限に抑える

Question

こんにちは、k都市に旅行する日数がn日となる最適化問題があり、旅行の総費用が最小限に抑えられるように旅行を計画する必要があります。

2都市uとvの間の旅費は、旅行することに決めた日によって異なります（したがって、uとvの間の旅費はf（u、v、n）です）。私が旅行している日）、1日に1回しか旅行することができません。 同じ都市に滞在することもできます。

これを最短経路アルゴリズムで解決する方法はありますか？

Answer 1

これはNP完全な問題です（ハミルトニアンパスから減るので）。これと標準的なトラベリングセールスマン問題との唯一の大きな違いは、エッジの重みがの動的であることです。これは、O（V V E！）の複雑さとO（V^3）最悪の時間でサイクル全体が解決できるという、1回の前処理コストに直面していることを意味します。

インテリジェントトランスポーテーション-TSP問題について説明しているこのpaper IEEEで公開された同様の問題の詳細をいくつか確認できました。