経路探索アルゴリズム

Question

有向グラフ、開始点、終了点、および時間制限を指定します。 各頂点には、この位置がどの程度魅力的であるかを表す「値」があります。頂点から別の頂点に移動するコストもあります。

私が必要とするのは、制限時間内で最大 "値"のパスを見つけることです。

Answer 1

問題を部分的に回答するには、次のような削減を使用してサブ問題としてKnapsack問題が含まれているため、考慮する問題はNP -hardです。利益p_1,...,p_nおよび重量w_1,...,w_nと目標容量Cによって定義nアイテムによって与えられるナップザック問題のインスタンスを考える

、次のようにグラフを定義します。

左側には、ソースノードsと右側に端末ノードtがあります。 i番目の項目については、2つのノードyes_iおよびno_iを定義します。これは、それぞれの項目を選択したり選択したりしないことに相当します。 yes - ノードの魅力はp_iであり、no - ノードの魅力はゼロです。

ノードのペアは、ソースと端末間の列に配置されていると想像することができます。各ノードは、前の列の2つのインエッジ（ソースに接続されている最初の列を除く）にあります。これらのエッジのそれぞれの重みは、yesのノードのインエッジである場合に限りw_iであり、ノードがnoノードのエッジである場合はゼロです。最後の列は端末に接続されています。

sからtまでの各パスは、列単位で各列の項目を選択するかどうかを決定する必要があります。同様に、アイテムの選択は、sからtまでのパスに対応します。辺の重みの定義により、経路の総重量は項目の選択の総重量に等しく、選択された項目の総重量は選択された項目の総重量と等しい。

合計で、Knapsackインスタンスの実現可能な解と、記述されたパス問題の構築されたインスタンスの両方を取得します。合計で、これは問題の問題が、サブ問題としてナップサック問題（NP -hardであることが知られている）を含むので、NP -hardであることを意味する。

また、NP -hardnessは、完全なグラフのすべての場所の魅力を1に設定することでわかります。この問題の特殊なケースは、NP -completeであることが知られているHamiltonian Path問題の決定版です。