2

簡単にするために、グラフがあるとします。

O O P O |
O O O O O
O | O | O
O O O O O
A O O O O

幅優先探索を使用して、最短経路でAからPに移動します。ここで、位置は|で指定されます。制限区域です。どうすればこの結果を達成できますか？ある場所（この場合はP）を見つけるために使用される幅優先探索は常に見ましたが、パス距離を保存して最短距離を計算するために使用される実装は見たことがありません（以前に訪問した場所を保存する効率的な方法もさらなる精査からそれらを除外します）。また、必然的に大きく、大規模なプッシュとポップを必要とするグラフに対して、通常どのキューが提案されますか？

4

4 に答える 4

6

幅優先検索の優れた点は、最短経路を自動的に見つけることです (ノードにアクセスしたときに、どこから来たかを追跡する必要があるだけです)。幅優先検索では、キューの先頭に最も安価なパスがあり、最後に高価なパスが常にあります。目標を達成するとすぐにP、パスの長さが最小であることが保証されます。

Anstd::queueは、それを実装するための絶対に良い選択です。

あなたのコメントに応えて：ノード/頂点のキューがあります（あなたの場合、これらはあなたのセルです）。ノードにアクセスすると、以前にアクセスしたことのないすべてのネイバーがキューに追加されます。訪問したノードとパスがどこから来たかを追跡するには、ノードごとに 1 つの要素でstd::array/を囲みます。std::vector wherefrom;次に (疑似コード!)

take element v from queue
 for each neighbour x of v
    if wherefrom[x] != NULL
     wherefrom[x] = v
     add x to end of queue

ターゲットノードに到達したらP、バックトラックしwherefromてパスを見つけることができます。

于 2013-01-30T01:29:37.123 に答える
3

ダイクストラのアルゴリズムを読んでから、A*検索に進むことをお勧めします。

C++でこの問題を解決する簡単な方法は次のとおりです。

  1. マップ内のノードごとに1つの要素（この例ではサイズ25）を使用して、-1に初期化されたintのstd :: vector（「トレイル」と呼びます）を作成します。これは、どのノードがすでに検索されているか、およびそれらがどこから検索されたかを示すために使用されます。'trail'値が-1のノードは検索されておらず、'trail'値が8のノードはノード8から検索されています。

  2. intsのstd::queueを作成します（これを「search_queue」と呼びましょう）。次に、「A」を含むノードのIDをプッシュし、その「trail」値をそれ自体にマークします。たとえば、「A」がノード20の場合、trail[20]を20に設定します。これは、トレイルがその時点で開始したことを記録します。

  3. 'search_queue'からフロントノードをポップし、それぞれのネイバーを順番に見て、トレイル値が-1で、制限されていない（'|'を含まない）場合は、キューにIDを追加します。

  4. 'P'が見つかるまで（目標に到達しました！）、またはキューが空になるまで（有効なパスがない）、手順3を繰り返します。

  5. 「P」が見つかった場合は、「trail」ベクトルを使用してパスを最初にトレースします。各ノードは、それ自体を指すノードに到達するまで、パス内の前のノードを指します。それがあなたが始めたところです、それであなたは今完全な道を持っています！

幅優先探索の性質により、アルゴリズムが最初に検出する有効なパスが可能な限り最短のパスになることが保証されるため、距離を計算する必要はありません。

于 2013-01-30T01:49:02.140 に答える
2

APO | の 2 次元配列があると仮定します。値。不明な場合は、ブルート フォース検索を使用して A を見つける必要があります。

パスの場合、A からの最短パスは、1 手の位置のセットを作成することによって見つけることができます (つまり、上、右、および斜めの移動が許可されている場合は右上)。そうするとき、同じ正方形に戻らないように、どの位置が訪問されたかを追跡したいので、元の配列に何かをする必要があります (例えば、訪問した位置を「O」から「o」に変更する) か、別の配列を持っています。このためだけの配列。1 手の位置から、まだ訪れていない合法的な 2 手の位置のセットを作成できます。「P」が見つかるまで続けます。

コンテナーの選択について: 上記のアルゴリズムでは、何もポップしません。ベクトルを使用するだけです。

最適化として、P もローカルにして、2 つの間の最も明白なパスの深さ優先トラバーサルを試してみたい場合があります。 」は、目的の行に到達するまで許可され、列に到達するまでは「右」です。right-else-up も、または代わりに実行できます。

于 2013-01-30T01:44:31.160 に答える
0

マップを取得したら:

O O P O |
O O O O O
O | O | O
O O O O O
A O O O O

グラフを定義し1、エッジがあるかどうかを示します。

1 1 P 1 0
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
A 1 1 1 1

どこa_ij = 0 iff m_ij = | and elsewhere a_ij = 1

次に、ダイクストラのアルゴリズムまたはベルマンフォード アルゴリズムを実行します。

を使用することを主張する場合BFSは、それが同様に機能する理由を次に示します。

最短経路を探すとき、幅優先探索はどのように機能しますか?

于 2013-01-30T01:33:53.730 に答える