航空路線に関する先の質問を拡大する

THIS私が言及した質問です。ここで与えられた答えは、経路の停止回数がユーザーによって指定されていない場合に機能しますが、停止/接続の数をユーザーが明示的に指定する場合、このソリューションはどのように変化しますか？だから最適なルート問題はそれほどありませんが（まだありますが）、やや最適な状態で、N個の停止点（ノード）を持つ経路を見つけることはますます進むでしょう。航空路線に関する先の質問を拡大する

出典

2011-02-08 Robert Toth

この問題は残念ながらHamiltonian path problemからの減少によってNP-hardであることが知られています。これは、正確にN個の停止を行う最短経路を見つける問題を本当に解決したいのであれば（もちろん、サイクルを必要としないと仮定した場合）、おそらくアルゴリズムを得ることは期待できませんそれはNの多項式です。

出典

2011-02-09 02:40:13 templatetypedef

確かにNで指数関数的です.Nが上限を持つ場合はO（1）です。いいえ？ –

@Mike Dunvaley-はい、でも、いくつかのことを覚えておく必要があります。まず、O（1）は「高速」を意味するものではない。あなたのNが大きければ、アルゴリズムのランタイムが非実用的に大きくなるような巨大な定数で終わるかもしれません。第2に、アルゴリズムがNで指数関数であるという事実は、アルゴリズムが固定Nに対してO（1）であることを意味しない。たとえば、アルゴリズムがO（k^N）であれば、kはグラフのサイズですが、アルゴリズムはN> 3の場合には非常に高価になる可能性があります。 – templatetypedef

私は同意します。私はちょうど、3つ以上のリンクが本当にまれである、私は疑いがあるので、非多項式であることが学術のようなものであること、航空路線の問題のために考えていた。 –

航空路線に関する先の質問を拡大する

答えて

関連する問題