1

リソースレベルを含むノードのグラフがあり、それらは正と負になる可能性があります。原則はテントウムシであるか、オブジェクトが各ノードから生命を得るか、ノードによって損傷を受けます。

キュー構造を使用して BFS を実装することができました:-

ノードリソースのないグラフが与えられた

  a---b---e
  |       |
  c---d   f

ルートテーブルは次のとおりです:-

node    parent
===============
a       null
b       a
c       a
d       c
e       b
f       e

したがって、(a) が開始ノードで (f) が終了ノードであると仮定すると、ルートは親を使用してプロットされます。最も速いルートは下のフェバからです。

私はこれをJavaコードで解決しました。問題は、各ノードがあなたを殺したり生きたりできるリソースを持つこのメソッドをどのように使用するかです。

つまり、いくつかのノードが-20で、他のノードが+10を与えるとします

使用されているキュー構造を考慮してルートを決定する方法がわかりません。

誰にもアイデアはありますか？

必ずしもJavaコードは必要ありませんが、何でも役に立ちます。ソリューションの理論と、どのデータ構造を使用できるかなどに本当に興味があります...

私の考えは多分

child  parent  resource
=======================
a       b       20+
b       a       10-
c       b       5+

さまざまなルートを保存する方法がわからないため、このテーブルには 1 つのルートしか保存されません。

4

1 に答える 1

0

すべての辺の長さが同じでない場合、BFS は最短経路を見つけるために実際には使用されません。Bellman Ford Algorithmをお勧めします。Dijkstra のアルゴリズムと同様に、与えられたグラフの最短経路を計算するために使用されます。ただし、ダイクストラのアルゴリズムとは異なり、すべての辺の長さが正であるとは限らないグラフを操作できます (質問をしたようです)。

これを説明するビデオがあります（OpenCourseWare経由）。

于 2012-04-22T16:37:00.913 に答える