11

ノードが実数 (正と負) に重み付けされている無向グラフを通る最短経路を見つける必要があります。これらの重みは、ノードに入ることによって獲得または解放できるリソースのようなものです。

パスの総コスト (リソースの合計) はそれほど重要ではありませんが、0 より大きくなければならず、長さは可能な限り短くする必要があります。

たとえば、次のようなグラフを考えてみましょう。

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

最短パスは AEFED です

ダイクストラのアルゴリズムだけではうまくいきません。負の値を処理できないからです。そこで、いくつかの解決策を考えました。

最初のものは、ダイクストラのアルゴリズムを使用して、重みを考慮せずに、各ノードから出口ノードまでの最短経路の長さを計算します。これは、A* のようなある種のヒューリスティック値のように使用できます。このソリューションが機能するかどうかはわかりません。また、非常にコストがかかります。Floyd-Warshall のアルゴリズムを実装することも考えましたが、どうすればよいかわかりません。

別の解決策は、重みを考慮せずにダイクストラのアルゴリズムを使用して最短パスを計算することでした。パスのリソースの合計を計算した後、ゼロ未満の場合は、各ノードを調べて、リソースの合計をすばやく増やすことができる隣接ノードを見つけ、それをに追加します。パス (必要に応じて数回)。このソリューションは、リソースの合計を増やすのに十分な可能性があるノードがある場合には機能しませんが、計算された最短パスから遠く離れています。

例えば：

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

この問題を解決するのを手伝ってくれませんか?

編集:最短経路を計算するときに、リソースの合計がゼロに等しいポイントに到達した場合、その経路は有効ではありません。ガソリンがなくなると先に進むことができないためです。

4

4 に答える 4

4

編集：質問を十分に読んでいませんでした。この問題は、通常の単一ソース最短経路問題よりも高度です。役立つかもしれない別のアルゴリズムを提供するためだけに、この記事を今のところ残しておきます。

Bellman-Ford アルゴリズムは、負の重みを持つエッジが存在する場合でも、単一ソースの最短経路問題を解決します。ただし、負のサイクル(重みの合計が負のグラフ内の循環パス) は処理されません。グラフに負のサイクルが含まれている場合、問題が NP 完全になると私は信じているため、問題が発生している可能性があります (最長単純経路問題に対応するため)。

于 2012-01-06T17:05:04.967 に答える
2

これは洗練された解決策のようには思えませんが、循環パスを作成する機能を考えると、それを回避する方法はわかりません。しかし、私はそれを繰り返し解決します。2番目の例を使用して-Aの点から始めて、それにAの値を与えます。1つの「ターン」を移動します-これで2つのポイントがあります。1つは値5のBにあり、もう1つは値5のDにあります。もう一度移動します-追跡するポイントが4つあります。C：45、A：15、A：15、E：0。Eにあるものが振動して有効になる可能性があるため、まだ投げ出すことはできません。移動や蓄積など。正の値でエンドノードに初めて到達したときは完了です（ただし、同じターンに追加の同等のパスが入る場合があります）

追跡するポイントの数が非常に急速に増加するという点で明らかに問題があり、実際のグラフは例よりもはるかに複雑であると思います。

于 2012-01-06T16:29:38.830 に答える
1

私はMikebが提案したのと同じようにそれを行います：可能な状態、すなわち（位置、燃料左）ペアのグラフを幅優先探索します。

サンプルグラフの使用：

サンプルグラフから得られた状態グラフ

  • 八角形：燃料がなくなった
  • ボックス：スペース上の理由で子ノードが省略されています

このグラフを幅優先で検索すると、そのようなルートが存在する場合に実際に目標に到達する最短ルートが得られることが保証されます。そうでない場合は、グラフに無限ループが含まれる可能性があるため、しばらくすると（xノードが検索された後、またはすべての負のスコアの絶対値よりも大きいスコアのノードに到達したときに）あきらめる必要があります。

同じ長さでコストが異なる複数のパスを見つける可能性があるため、最も安いパス（燃料に関して）も見つけたい場合は、ゴールを見つけるのをすぐに中止しないようにする必要があります。

于 2012-01-07T10:46:48.817 に答える
0

最小ウェイト（この場合は5）の絶対値をすべてのウェイトに追加してみてください。それは負のciclicパスを回避します

現在の最短経路アルゴリズムでは、一部のノードでソリューションを組み合わせて他のノードの最短経路を調整するのに役立つため、すべてのノードへの最短経路を計算する必要があります。1つのノードだけにそれを作る方法はありません。

幸運を

于 2012-01-06T15:19:51.633 に答える