3

私は現在、EdX の Berkeley AI クラスを受講しており、A* 検索について検討しています。以前に A* グラフ検索を使用したことがあり、後継者をフリンジ/キューに追加するときに、後継者がフリンジまたは探索済み/クローズド セットにある場合は後継者を追加しないように実装しました。ただし、クラスの教授は、A* グラフ検索の場合、フリンジにノードを追加し、それらをポップして、それらが既に探索セットにある場合はスキップする必要があると言っていました (つまり、それらを展開することを拒否しますが、それでも追加します)フリンジまで繰り返されるノード)。

ウィキペディアの疑似コードhttp://en.wikipedia.org/wiki/A_star#Pseudocodeでは、A* は別の方法で実行されているようで、探索された/ にない場合にのみフリンジ/キューに追加します。すでに閉じたセット。ただ、後継者のGスコアを極限まで抑えるダイクストラらしい部分もある。

これはすべて、一貫した最適なヒューリスティックを使用していることを前提としています。誰かがそれを実装した結果をよりよく理解するのを手伝ってくれませんか ありがとう!

4

1 に答える 1

3

以前に遭遇したノードを処理するための2つのアプローチについて話している

最初のアプローチでは、アイテムをキューからポップして、閉じたセットに追加します。その場合、後続をキューに追加する必要があります。サクセサがすでにキューにある場合は、その値を更新するだけです (したがって、最小になります)。これには、少なくとも n 回のルックアップ操作が必要です (ノードの後続ノードごとに 1 回)。ノードがすでにキューにあるたびに、その値を新しい値と比較し、場合によっては優先度を更新する必要があります。最悪のシナリオでは、キューに対して n 回のルックアップ、n 回の比較、および n 回の更新操作を実行する必要があります。

あなたの 2 番目のアプローチ (教授からのアプローチ) では、すべての後継者が既に存在するかどうかを確認せずにキューに入れられます。これにより、ノードを評価するときに n 回の挿入のみが必要になります。ただし、キューのノードをポップするたびに、そのノードが既にクローズド セットにあるかどうかを調べる前に確認する必要があります。これには、キューに追加したノードごとに 1 つのルックアップ操作が必要です (ただし、キューにはありません)。1 つのノードがキューに複数回存在する可能性があります (最初のアプローチでは、キューにコピーが 1 つだけ存在します)。

ご覧のとおり、両方のアプローチの違いは、使用するキューの種類 (フィボナッチ ヒープ、バイナリ ヒープなど) と、それぞれの操作のコストによって異なります。更新操作にコストがかかる場合は、2 番目の方法の方が高速です。2 番目の方法では、キューにより多くのメモリが必要になります (同時に同じノードの複数のコピーを含めることができるため)。キューが大きくなり、それに対する操作に影響を与えます。

使用するキューを確認し、必要な操作とグラフに基づいて最適なアプローチを決定する必要があります。

于 2012-10-06T12:58:26.397 に答える