追加条件での最速パスの検索

Question

無向グラフに複数の直接接続がある場合、Dijkstraのアルゴリズムが正しく動作するかどうかは疑問です。

例えば：

私は最速のパスを見つけるためにダイクストラを使用したいが、追加の条件があります。エッジ上のすべてのadditional_dataの合計は、> = xにすることはできません。だから、もしそれがその重さの端から出てきたなら、3は間違って使いました、私のプログラムは2番目のエッジで試してみるでしょう。

編集： 私の仕事は、エッジからのadditional_dataの合計がxより大きくなることができないという追加の条件の下で、最速のパスを見つけることです。この問題の対処方法を教えてください。

EDIT2：私はこのlinkを見つけたたくさんそれまではインターネットを研究してきました

（恵みに設定）。 私が求めていることをする方法についての説明があります。 （上中級acapite）

私はこれを何とか今何とかしようとしていますが、私はこのアルゴリズムを正しく理解できないと心配しています。私はこの問題を手伝ってくれる人の中に、もう少し具体例を説明してほしいと思います（いくつかの最初のステップ）。ここでは例を示します。

Answer 1

これを処理するDijkstraのアルゴリズムを変更できると思います。 Dijkstraのアルゴリズムは、基本的に、すべてのノードへの最短経路を列挙したテーブルを段階的に構築することによって機能します。代わりに、与えられたコストですべてのノードへの最短パスをリストしたテーブルを作成します。または、むしろ、所定のコスト以下で、すなわち所与の予算で。

さらに、正式には、元のグラフを別のグラフに変換し、そのグラフにDijkstraを適用することができます。 additional_dataコストが常に整数であると仮定すると、変換は次のとおり

1. がn毎に元のノードを取り、ノードのセットを作成する（N、C）の値まで0からCのすべての整数値についてあなたが許容できるadditional_dataの最大合計）
2. すべての元の接続n1 - > n2を重みwとadditional_data aと取り、すべてのノード（n1、c）からノード（n2、 c + a）は、それぞれ重みwを有する。

元のグラフモデルのノードは、空間内の位置にある。変換されたグラフモデル内のノードは、状態変数が位置する状態空間内の位置、およびこれまでに費やされた予算の量に位置する。

予算のxをAからZにしたい場合、Dijkstraのアルゴリズムを使って（A、0）からノードの1つ（Z、c < = x）までのルートを見つけるだけです。

EDIT：私は修正ダイクストラのアルゴリズムを実装しました：https://bitbucket.org/twic/roadsproblem。その要点はsrc/solver.pyです。

Answer 2

あなたの追加条件は、多くの困難な問題になります。それを見ると、ソースとターゲットの間の可能なすべてのパスを見つけ出し、合計エッジウェイトでソートして、追加の条件が成立しているかどうかを1つずつチェックすることだけが可能だと思います。

しかし、2つの頂点間の可能なすべてのパスを見つける問題はNP-Hardです。 DFSのわずかに修正されたバージョンは、そのトリックを行うことができるかもしれませんが、おそらくすべての場合にそうではありません。

Answer 3

Dijkstraのアルゴリズムは、必要な距離がソースノードと宛先だけではないので、この問題の良い解決策ではないと思います。ここで*検索アルゴリズムに基づいたソリューションです。\

まず、グラフの各ノード対のための少なくともweightと少なくともadditional_dataを取得するためにadditional_dataに基づいweight、その後に基づいてFolydWarshallを行います。

FloydWarshall(Weights); 
    FloydWarshall(Additional_datas); 

第二に、我々は構造次のような要素が優先度キューに基づいてA *検索を実行（例として使用するCコードを。）プライオリティキューは、自動的にすべての候補者にweights_sum以上を取得します。 weights_nowは、現在の体重*検索アルゴリズムで

struct NODE 
    { 
     int node; 
     int weights_expected; 
      int weights_now; 
     int additional_datas_now; 
      bool visited; 
    }; 
    bool operator < (const NODE &A,const NODE &B) 
    { 
     return A.weights_expected>B.weights_expected || (A.weights_expected==B.weights_expected && 
    A.additional_datas_now>B.additional_datas_now); 
    } 

、

1) we first put the source node into priority queue. 
    2) while Priority Queue is not empty: 
     Set **A** equal to the head of priority queue and pop out the head of priority queue. 
     A.visited=True; 
     if A is the destination node **Dest**, **return** A.weights_expected. 
     For each neighbors **B** of node **A**, 
      if A.visited==False **and** A.additional_datas_sum+|AB|.additional_data+Additional_datas[B][Dest]<=x, 
       1) B.additional_datas_now=A.additional_datas_now+|AB|.additional_data;  
       2) B.weights_now=A.weights_now+|AB|.weight; 
       3) B.weights_expected=B.weights_now+Weights[B][Dest]; 
       3) push node B into priority Queue. 
    3) Print "Do not find a proper path" //if code came to here, that means the if in 2) do not return a value. 

Aである一方、*検索は最悪であるため、まだNP困難になる宛先ノードに現在のノードを通るパスの最良の推測weights_expectedですそれぞれの可能なパスを検索する必要があります。ただし、単純なDFS検索よりもはるかに高速で、検索パスを大幅に削減できます。

Answer 4

2つ目の可能なパスを追加するノード間にコスト0のコピーを作成できます。

ようなので、（擬似コード）

Node 1____ 
|   | 
|path1 | 
|cost=3 |path2 cost=5 
|   | 
Node 2____/ 

はこのようになります。

Node 1____cost=0____Node 1a 
|   path 1a  | 
|path1    |path2 
|cost=3    |cost=5 
|      | 
Node 2________________/ 

ないこれが機能するかどうかを確認しますが、それはアイデアです。

Answer 5

ここでは、見つけたアルゴリズムがあなたの問題の例をどのように処理するかについて説明します。

問題は、途中の累積コストが7より大きくならないように、node oneとnode fourの間の最短経路を見つけることです。

node oneからノードnode twoまでの距離、190の距離、および4のコストです。距離195とコスト3のパスを使用してnode twoからnode fourに移動します。合計で、パスは385の距離と7のコストを持ちます。

ステップ1

それでは、どのようなアルゴリズムは、これを見つけるのですか？最初のステップは、あなたがやったように、マトリックスminArray(i,j)を設定することです。配列の(i,j)要素は、ノードjに到達するために移動する必要がある距離を正確にiの金額で保持します。そこからスタート

何の要素を訪問されていないと我々は左上の要素がゼロに設定されている7「金銭」とnode oneから開始されているからです。上の表の空白は、配列内のinfinityに設定されている値に対応しています。

ステップ2

次に、我々は、アレイの最小値を見つけ、これは位置(remaining money, node) = (7,1)にゼロです。この要素はvisitedに設定されています（要素の状態はminArrayと同じサイズの行列visitedArrayを使用して追跡されます）。つまり、node oneが選択されています。 node oneに接続するすべてのノードは、対応するエッジをトラバースすることによって値で更新されます。我々はそこに着くために1のコストを払っておりますので、我々はnode threeに到達するために191の距離を行っているし、我々が残っているお金が6であることを意味

ここ

minArray(6,3) = 191。同じようにminArray(3,2)は190に設定されています。赤い四角は、要素(7,1)が訪問したことを示しています。

ステップ3

今、私たちは再び、（minArray(3,2) = 190ある）最低未訪問の要素を見つけるvisitedにそれを設定し、それに接続するすべての要素を更新。これは、距離が累積され、残りの金額が現在の値からコストを差し引いて計算されることを意味します。

node twoから戻ってnode oneに行くにはあまりにも高価であることに注意してください。 minArray(6,3) = 191を選択

ステップ4

次のステップは、次のようになります。

ステップ5

3つのステップ以降の配列は次のようになります。ここでは、382に等しい要素と383に等しい要素が選択されています。要素の値は、それが現在の値の改善（すなわち、より低い）である場合にのみ更新されることに留意されたい。

ステップ6

配列は、すべての要素がいずれかの訪問または静止無限大値を有するまで充填し続けます。

最終工程

最後のステップは、4列の最小値を見つけることによって、総距離を見つけることです。最小値のminArray(0,4) = 385が正しい解に対応していることがわかります。

注：列4の値がすべて無限であった場合は、有効な解決策がないことを意味します。このアルゴリズムはまた、列4に等しい距離と最小距離の複数の値がある場合、最も安いものが選択されることを指定する。

Answer 6

追加の条件は、ダイクストラを破ります。このように考えると、グラフにA→B、B→Cのグラフがある場合、Bを含む最短経路A→Cは確かにA→Bの最小経路です→C。あなたのケースでは、A→BとB→Cが有効であるかもしれないので、A→B→Cは有効でないかもしれないので、この状態は成立しません。

これは、紙を掴んで試してみるところです。

あなたのグラフを見て、あなたは（4）に（1）から行きたいと仮定した場合、あなたは以下のエッジを導入することにより、（3）を除去する方法がわかります

• （1） - >（4）、[390]、[2]
• （1） - >（2）、[383]、[3]
• （2） - >（4）、[391]、[3]

すべてのエッジを削除して一直線にすると、問題はやや簡単になります。ノードごとに、[距離、追加]それは目標を達成するために費用がかかります。実行可能な解決策ではないので、追加の「最大」または「残りの追加」<を保存する必要はありません。また、同じ距離に複数の距離がある場合は、最小限の距離を維持する必要があります。

最後のノード（または、注文した方法によっては最初のノード）の距離が最短になるソリューションが最適なソリューションです。道路を下っている場合は、そこにどのようにアクセスしたかについての指針を保持していました（たとえば、行列の値を更新して変更した要素も保存した場合など）。

ここでは、x軸をノード、y軸を「ノードごとのリスト」として、問題が除去されていないフォームにあるときに同じことを行うことができます。

それはそれを行う必要があります。

Answer 7

はあなたaddittionalデータは、ベルマン - フォード法におけるエッジパラメータの数であるという仮定でベルマン - フォード法を使用することができます。

Answer 8

この問題はNP完全です。複数の人によって説明されたアルゴリズムよりもアルゴリズムは効率的ではありません（Tom Anderson、user1884905）。

証明： 非負の数のサブセット和を減らすことによって。

サブセット和（N個）のインスタンスAをとります。 N + 1個のノードがあるグラフを作成します。ノードiとi + 1に対して、重み= 0、additional_data = A [i]、重み= A [i]、additional_data = 0の2つの経路を作る。x（additional_dataの合計の上限）を選択します。

アルゴリズムは加重和を最小限に抑えなければならないことに注意して、additional_dataの合計も最大化します。したがって、選択された最初の種類のパスは、サブセットサム問題の結果として数値に関連付けられたパスになります。