問題タブ [floyd-warshall]

これには新しい一連の目のペアが必要です。何らかの理由で、正しいシーケンスと距離の行列が生成されないため、以下が私の実装です。

これは C# であり、DistanceMatrix は double [,] であり、SequenceMatrix は文字列 [,] です。

これらは次のように開始されます: http://puu.sh/951Tz/5ef27e3996.png

何らかの理由で、次の出力が得られます。

さらに情報が必要な場合は、このページをF5します:)

初期化後の距離行列

Floyd-Warshall アルゴリズムを使用して、2 つ以上のノード ペア間の最短ルートを計算する簡単なプログラムを作成しようとしています。

Villageノードを表すクラスと、ノードRoad間の道路を表すクラスを使用しています。TransportRequestコードのさらに下では、最短パスを生成する必要がある 2 つのノードを表すクラスも呼び出しています。

上記のコードは、ランダムに生成されたノードと距離のほとんどで正常に動作するように見えますが、以下のようないくつかの場合に失敗します。

ノード A からノード E までの最短ルートを計算しようとすると、答えは常に A > B > C > D > E (合計 37) ではなく、A > E (合計 100) になります。

各ノード間の道路は双方向です。つまり、この場合、A から B と B から A は両方とも 10 です。

行列 dist[] には、各ノード ペア間の正しい距離が正しく取り込まれています。ノードのペアを結ぶ道路がない場合、デフォルトの距離を 1000000 単位に設定しています。

さまざまなフォーラム (これを含む) で複数の質問を検索しましたが、この問題に取り組んでいるようには見えません。アルゴリズムは正しく実装されていると思いますが、特定の状況で正しく機能しない場所と理由がわかりません。

この問題を解決するために 1 週​​間以上取り組んできたので、この問題について助けていただければ幸いです。

よろしくお願いします。

私の担当者が非常に少ないので、これはおそらくSOで尋ねるのは悪い質問ですが、私は何時間も他のソリューションを調べてきました.私のコードは、私が遭遇した実用的なソリューションとほぼ同じです. 低担当者に基づく質問を無視しないでください。

出力行列 d[][] には、指定された頂点のペア間の最短経路の (誤った) 長さが含まれています。Python 用の networkx ライブラリで提供されているソリューションが使用されています。

抜粋として、n=20の結果が提供されています。オーバーフローがあるため、無限大 (つまり 99999) より大きいパスは出力しません。

グラフは次のようになります。

My Floyd-Warshall アルゴリズムの実装 (C)

Floyd-Warshall アルゴリズムに対する Networkx ソリューション (Python)

実装：

テスト クライアント (Python)

i = j Cii = 0 および i != j Cij > 0 である非負の重み Cij を持つ n 個のノードを持つ重み付き無向完全グラフが与えられたとします。任意の 2 つの間の最大最短経路を見つける必要があるとします。ノード i と j。ここでは、Floyd-Warshall を簡単に使用したり、Dijkstra を n 回使用したりして、n^2 のすべての最短経路の中で最大のものを見つけることができます。

ここで、Cij は定数ではなく、0 <= Aij <= Bij である Aij と Bij の 2 つの値を取ることができると仮定します。また、Aii = Bii = 0 もあります。最大最短経路も見つける必要があると仮定しますが、m 個のエッジが値 Bij を取り、その他の Aij を取らなければならないという制約があります。また、m > n^2 の場合、すべてのエッジは Bij に等しくなります。しかし、最短パス i -> p1 -> ... -> pk -> j を見つけるとき、そのパスで Bij の値を取るためにそれらのエッジを選択する必要があるという意味で、最悪の場合に興味があります。その方向に固定ノードがある場合、そのパス値は最大になります。

たとえば、長さ 4 iklj のパスがあり、そのパスの最適解では、1 つの重みだけが Bij に変更され、他の重みは Aij の値を取る場合。そして、m1 = Bik + Akl + Alj、m2 = Aik + Bkl + Alj、m3 = Aik + Akl + Blj とすると、そのパスの値は max{m1, m2, m3} です。したがって、i と j の間のすべてのパスの中で、最大値 (この例で説明) が最小になるようなパスを選択する必要があります (これは、最短パスの定義の変形です)。そして、すべてのペア i と j に対してそれを行う必要があります。

各パスでいくつ変更する必要があるかという制約は与えられませんが、完全なグラフで変更する必要がある重みの数である m の値が与えられます。そして問題は、説明したように、最短経路の最大値を見つけることです。

また、私の質問は次のとおりです。これはNP困難な問題ですか、それとも多項式の解が存在しますか?

Floyd-Warshall アルゴリズムでは、頂点の任意のペアについて最短パス コストが計算されます。追加の簿記により、実際のパス (頂点のリスト) を最短パスに保つことができます。

Floyd-Warshall を拡張して、任意の頂点のペアについて、上位 K の最短経路が見つかるようにするにはどうすればよいですか? たとえば、K=3 の場合、3 つの最短経路が計算されて維持されるという結果になりますか?

私はSedgewickのJava 実装を使用しています。

この質問は以前に何度か回答されていることは知っていますが、状況を改善するために以前の回答をすべて確認しましたが、役に立ちませんでした。

私がする必要があるのは、ループを並列化して、各都市 (または内側のループ) が並列に処理されるようにすることです。しかし、parfor を使用しているときに、「parfor の変数 A を分類できません」というエラーが表示されます。2d 行列のサイズは n X n に固定されています。問題がわかりません。親切に私を助けてください...

私が提供した c 実装は mpi.h を使用して行われました。mpicc を使用します。私が達成する必要があるのは、n個のプロセスが必要であり、それぞれがその地方都市から他のすべての都市への最短経路を見つける責任があるということです。

異なる場合はその都度。私の場合：

最短パスを計算する関数は次のとおりです。

必要だと言われたメソッドに関する限り、プログラムに必要なもののスケルトンは既にあります。ただし、それ以外は、このプログラムのコーディングを開始する方法がわかりません。詳細は以下の通りです。 私は自分のプログラムを私のためにやってくれるように頼んでいるわけではありません。テキスト ファイルを取得するためにユーザー入力を読み込む必要があることはわかっています。私の大学ではスキャナーを使用していますが、それがコンストラクター、メイン、または別のメソッドに必要かどうかはわかりません。

1. 単一のコマンド ライン パラメータ、つまり行で区切られた文字列のペアのリストを含むテキスト ファイルを受け入れます。これらの文字列のペアは、依存グラフのエッジを表します。たとえば、A.java B.java という行は、A.java から B.java への依存エッジを表します。上記のグラフを表すファイルは次のようになります。 Main.java A.java A.java B.java

2. ファイルから読み取った各文字列を一意の整数識別子にマップします。このマッピングにより、ファイル名を配列インデックスに簡単に変換できます。

3. (上記の) 一意の整数識別子のそれぞれを元の文字列にマップします。

4. 文字列間の依存関係を表す隣接行列を計算します。

5. 隣接行列に対して推移閉包操作を実行して、文字列間の推移的な依存関係を表す新しい閉包行列を生成します。この操作を実行する簡単な方法は、Floyd-Warshall アルゴリズムです。このトピックについて調査することをお勧めします。

6. 出力は、コース Web サイトのサンプル出力ファイルで示されている形式に従う必要があります。コースの Web サイトには、サンプルの入力ファイルと対応する出力ファイルがあります。この例では、出力は同じ形式である必要があります。目標は、出力情報を魅力的で読みやすい形式にして、以下にリストされている各方法が正しく機能することを明確にすることです。

7. プライベート フィールドを持つメソッドは、クラスの内部状態の可変部分を返すのではなく、getNameIdMap、getIdNameMap、getRoots などの型を返します。そのマップのコピー (クローン)、リストが返されます。このようにして、呼び出し元は、クラスの内部状態に影響を与えることなく、完全に使用可能なオブジェクト (リストやマップなど) を取得します。

プログラムは、次のメソッドも提供する必要があります。

1. public Map getNameIdMap() - 文字列から一意の整数識別子へのマッピングを返します。整数識別子は、指定された文字列の隣接行列と閉包行列へのインデックスを表します。注: Python では、戻り値は、キーが文字列で値が int のペアを持つ辞書である必要があります。

2. public Map getIdNameMap() - 一意の整数識別子から元の文字列へのマッピングを返します。注: Python では、戻り値は、キーが int で値が文字列のペアを持つ辞書である必要があります。

3. public int[][] getDependenceGraph() - ファイル間の依存関係を表す隣接行列を返します。

4. public int[][] getTransitiveDependenceGraph() - 推移閉包操作が適用された後に依存グラフを返します。

5. public List getRoots() - 他のファイルが依存していないファイルに対応する文字列のリストを返します (例: 上記の例の Main)。注: Python では、戻り値も文字列のリストです。

6. public List getLeaves() - 他のファイルに依存しないファイル (上記の例の B など) に対応する文字列のリストを返します。注: Python では、戻り値も文字列のリストです。

7. public void removeLeaf(String leaf) - 隣接および推移閉包行列の両方から葉を削除します。これは、X が Y に依存し、Y が削除されるリーフである場合、X の Y への依存も削除されることを意味します。これにより、X が新しいリーフになる場合とならない場合があります。ファイルが論理的に削除されたことを示すために、マトリックスで特別な番号 (つまり、0 と 1 以外) を使用することを検討してください。

8. public List firewall(String node) - 指定されたファイルの「クラス ファイアウォール」を計算します。ソフトウェア エンジニアリングでは、クラス ファイアウォールの概念により、システムでメンテナンスが実行される場合、変更されたクラスと変更によって影響を受けるクラスのみを再テストする必要があると述べられています。注: Python では、戻り値も文字列のリストです。この方法では、間接的および直接的に影響を受けるクラスを再テストする必要があります。たとえば、クラス A がクラス B に依存し、クラス B がクラス C に依存している場合、クラス C を変更すると、クラス A と B を再テストする必要があります。

9. public void printParallelGroups() - ファイルのコンパイルを並列化したいとすると、他のファイルのコンパイルをトリガーしないファイルを特定する必要があります。これらは依存関係グラフの葉です。このメソッドは、並行してコンパイルできるファイルを識別し、そのファイルのリストを出力して、グラフから削除します。メソッドは、すべてのファイルが「コンパイル」されるまで、このプロセスを繰り返す必要があります。