15

無向グラフに複数の直接接続がある場合に、ダイクストラのアルゴリズムが正しく機能するかどうか疑問に思います。

例えば：

ここに画像の説明を入力してください

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

編集：私のタスクは、エッジからの合計がadditional_dataxを超えることができないという追加の条件の下で、最速のパスを見つけることです。この問題の処理方法を教えてください。

edit2 :(報奨金の設定）

私はこのリンクを見つけるまでインターネットをたくさん研究してきました。私が求めていることを行う方法の説明があります。（上中級アキャピテ）

どういうわけか2日間使用しようとしていますが、このアルゴリズムが正しく理解されていないのではないかと心配しています。例についてもう少し説明して、この問題について私を助けてくれる人を何人かお願いしたいと思います（最初のステップはほとんどありません）。次に例を示します。

ここに画像の説明を入力してください

4

8 に答える 8

8

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

より正式には、元のグラフを別のグラフに変換してから、そのグラフにダイクストラを適用できます。additional_dataコストが常に整数であると仮定すると、変換は次のようになります。

  1. すべての元のノードnを取得し、0から予算の値（許容できるadditional_dataの最大合計）までのcの整数値ごとにノードのセット（n、c）を作成します
  2. 重みwとadditional_dataaを持つすべての元の接続n1->n2を取得し、すべてのノード（n1、c）からノード（n2、c + a）への接続のセットを作成します。それぞれの重みはwです。

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

xのバジェットでAからZに移動する場合は、ダイクストラのアルゴリズムを使用して、（A、0）からノードの1つ（Z、c <= x）へのルートを検索します。

編集：変更されたダイクストラのアルゴリズムを実装しました：https ：//bitbucket.org/twic/roadsproblem 。その核心はにありsrc/solver.pyます。

于 2013-01-06T18:02:26.383 に答える
5

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

問題は、途中の累積コストがを超えてはならないという追加の条件を使用して、とのnode one間の最短経路を見つけることです。node four7

私たちが見つけたい解決策は、最初node oneにノードに移動することです。node two距離は。です。そして、距離とコストのパスを使用するようになります。合計すると、パスの距離とコストは。になります。1904node twonode four19533857

ステップ1

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

元の配列。

node one最初は訪問された要素はなく、 「お金」から始めているので、7左上の要素はゼロに設定されています。上記の表の空のスペースはinfinity、配列で設定されている値に対応しています。

ステップ2

次に、配列の最小値を見つけます。これは、位置のゼロ(remaining money, node) = (7,1)です。この要素はに設定されますvisited（要素の状態はvisitedArrayと同じサイズの行列を使用して追跡されますminArray）。これは、を選択したことを意味しnode oneます。これで、接続するすべてのノードがnode one、対応するエッジをトラバースすることによって値で更新されます。

アレイ1。

これは、私たちが到達するためにminArray(6,3) = 191距離を置いたことを意味し、私たちが残したお金は、そこに到達するためのコストを支払ったためです。同様に、に設定されます。赤い四角は、その要素が訪問されたことを示します。191node three61minArray(3,2)190(7,1)

ステップ3

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

配列2。

node oneから戻るにはコストがかかりすぎることに注意してくださいnode two。

ステップ4

次のステップ、選択minArray(6,3) = 191は次のようになります。

配列3。

ステップ5

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

配列4。

ステップ6

配列は、すべての要素が訪問されるか、無限の値を持つまでいっぱいになり続けます。

アレイ5。

最終段階

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

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

于 2013-01-14T13:30:27.167 に答える
1

必要な距離は送信元ノードと宛先だけではないため、ダイクストラのアルゴリズムはこの問題の良い解決策ではないと思います。これがA*検索アルゴリズムに基づくソリューションです。\

最初に、に基づいてFolydWarshallを実行しweight、次にに基づいて、グラフ内の各ノードペアの最小値と最小値additional_dataを取得します。weightadditional_data

  FloydWarshall(Weights);
  FloydWarshall(Additional_datas);

次に、次の構造のような要素を持つ優先度キューに基づいてA *検索を実行します（例としてcコードを使用します）。優先度付きキューは、すべての候補で最小のweights_sumを自動的に取得します。weights_expectedは、現在のノードから宛先ノードまでのパスの最良の推測ですが、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);
    }

A *検索アルゴリズムでは、

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困難になります。ただし、単純なDFS検索よりもはるかに高速で、多くの検索パスカットを実行します。

于 2013-01-07T21:30:14.600 に答える
1

あなたの追加の条件は問題を非常に難しくします。それを見ると、あなたができる唯一のことは、ソースとターゲットの間のすべての可能なパスを見つけ、それらを合計エッジウェイトで並べ替えてから、追加の条件が満たされるかどうかを1つずつ確認することだと思います。

ただし、2つの頂点間のすべての可能なパスを見つける問題は、NP困難です。わずかに変更されたバージョンのDFSでうまくいく可能性がありますが、すべての場合ではない可能性があります。

于 2013-01-06T17:55:52.943 に答える
1

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________________/

これが機能するかどうかはわかりませんが、それはアイデアです。

于 2013-01-11T23:45:58.497 に答える
1

追加の条件はDijkstraを壊します。グラフにパスA->Bがあり、グラフにエッジB-> Cがある場合、Bを含む最短パスA->Cは確かにA->Bの最小パスです。 ->C。あなたの場合、この条件は当てはまりません。A->BとB->Cは有効かもしれませんが、A->B->Cは無効かもしれないからです。

さて、これはあなたが一枚の紙をつかんでこれを試すポイントです。

グラフを見て、（1）から（4）に移動したいと仮定すると、次のエッジを導入して（3）を削除する方法に注意してください。

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

直線以外のすべてのエッジを削除すると、問題はやや簡単になります。ノードごとに、目標に到達するためにかかる[距離、追加]の量を追跡できます。追加の>maxまたは'残りの追加の'<0を保存する必要はありません。これは、実行可能なソリューションではないためです。また、等しい追加の距離が複数ある場合は、最小距離のみを保持する必要があります。

最良の解決策は、最後のノード（または注文方法によっては最初のノード）の距離が最小のソリューションです。将来的には、そこにたどり着いた方法を示したままにしている場合（たとえば、マトリックスの値を更新すると、それを変更した要素も格納されます）、パスをバックトラックすることもできます。

ここで、問題が除去されていない形式で、提案した行列を使用して同じことを実行できることに注意してください。x軸はノード、y軸は「ノードごとのリスト」です。

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

于 2013-01-16T08:53:42.540 に答える
1

ベルマンフォードアルゴリズムは、追加データがベルマンフォードアルゴリズムのエッジ数パラメーターであると仮定して使用できます。

于 2013-01-17T14:04:29.933 に答える
1

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

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

部分和（N個）のインスタンスAを取ります。N+1ノードがあるグラフを作成します。ノードiとi+1の場合、2つのパスを作成します。1つはweight = 0、additional_data = A [i]、もう1つはweight = A [i]、additional_data=0です。x（additional_dataの合計の制限）を選択します。

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

于 2013-01-17T16:36:22.737 に答える