6

AIMA ( Artificial Intelligence: A Modern Approach ) のアルゴリズムの説明はまったく正しくありません。「必要」とはどういう意味ですか? メモリ制限とは何ですか? キューのサイズまたは処理されたノード? 現在のノードに子がまったくない場合はどうなりますか?

このアルゴリズム自体が正しいかどうか疑問に思っています。私はインターネットを検索しましたが、まだ誰も実装していません。

ありがとう。

4

2 に答える 2

3

PDFを使用して、C# でグラフ検索を実装することができました。

フロンティア (オープン リスト)、リーフ リスト、「ツリー ブランチ」リストの 3 つのリストを使用しました。

  • Frontier はキューであり、PDF に記載されています。これは、最良のものから最悪のものへと並べ替えられた一般的な優先順位のキューです。

  • リーフ リストは、最悪から最良の順に並べ替えられたリーフのみを保持します。どのリーフを忘れるかを決定するときに必要になります。SMA は、枝全体ではなく、葉だけを忘れます。

  • ツリー ブランチ リストは、子がすべてメモリ内にある完全に展開されたノードを保持します。状態の交差をテストするために必要になります。

フロンティア リストとリーフ リストには高速バイナリ ヒープを使用し、ツリー ブランチ リストにはハッシュ テーブルを使用しました。

ノードは次の追加情報を保持する必要があります。

  • 位置を持つ後続イテレータ (後続リストを指すには位置が必要です)。追加したばかりのノードを忘れてしまう可能性があるため、途中で忘れてしまった場合は、後継者の列挙をゼロにリセットしてはいけません。位置には IEnumerator、int を使用し、「終了」フラグには bool を使用します。

  • 後継者リスト。これは、f-cost の上方伝搬のために必然的に必要になります。また、[ブロックされた、忘れられた、存在する] などの単純な後継状態リストも保持しています。忘れてブロックされたノードを追跡するために必要です。(ブロック - グラフ内 - より速く拡大したいくつかのノードによって)

  • PDFで言及されている2つのF、現在のF、そして最も忘れられている後継F.

  • ノードの深さ

フロンティア リストとリーフ リストの両方のノードの並べ替えは、次のように行う必要があります。リーフ リストは、まったく同じ条件を使用して逆順に並べ替えられます。

基本的なアルゴリズムの概要は次のとおりです (PDF に似ています)。

  • 「終了」フラグがある場合は、フロンティアから最適なノードを選択します。覚えていることはわかっており、反復子をリセットします。この場合、忘れられた最適な後継ノード F をリセットする必要があります (複雑な理由により)。

  • この後継者がまだリストにない場合 (思い出すと、ある可能性があります)、それを生成し、PDF で説明されているように F に設定します。

  • 次に、最も複雑なことに従います。同じ状態のノードがフロンティアまたはツリー ブランチ リストに存在するかどうかをテストします。そうであれば、後で何をすべきかを説明します。そうでない場合は、単に子をフロンティアに追加します (そして親をリーフ リストから削除します)。

  • 後継者の列挙が終了するすべての場合で、いわゆる f-cost のバックアップを行い、忘れられたノードがない場合 (およびいくつかの後継者がある場合)、現在のノードをフロンティアから削除し、ツリーに追加します。支店リスト。

忘れる方法: 葉リストから最初の葉 (最悪の葉) を選び、それをフロンティアから削除し、親の後継者リストから削除し、必要に応じて親の忘れられた後継者の F を更新 (減少) し、親がフロンティアにない場合- ツリー ブランチ リストから削除し、フロンティアに追加し、葉の場合は葉リストに追加します (後継者がなくなった場合)。

すでにフロンティアまたはツリー ブランチ リストにある後継者を生成した場合の対処方法。まず、2 つのノードの PathCost + H (「元の」F) を比較します。バックアップされた F をまったく比較できないことに注意してください。これは機能しません。それが良くない場合は、後続の状態をブロック済みに設定するだけです。そうである場合、最悪のノードが巨大なサブツリーのルートである可能性があります (複雑すぎて再度説明できません)。この唯一のケースでは、サブツリーを完全にカットし、SMA は一度に多数のノードを忘れます。悪いノードをより良いノードに置き換えた後、その親の後継者リスト、フロンティア、リーフ リスト、さらにはツリー ブランチ リストから悪いノードを削除し (そこにある可能性もあります!)、その親に対して後継者の状態をブロックに設定し、ドンします。 「悪いノードかどうかを確認することを忘れないでください」

多分私は最も単純な実装を持っていないかもしれませんが、それは私のために働く唯一のものです. テストには 8 パズルを使用しました。最小 (n+1) メモリ (開始ノードのカウント) で n ステップを解き、従来の a-star で解の最適性をチェックしました。すべての詳細を把握するために 20 ～ 30 時間ほど費やしました。主な問題は失敗したテスト ケースの複雑さにありました。何千ものランダムシードの広範なテスト。また、優先キューにも注意してください-多くの場合、アイテムを再挿入する必要があり、Fが変更されたり、Fが最も忘れられたり、「終了」フラグが変更されたりします-ソート順が変更されます。デキューごとにバイナリヒープの一貫性をチェックすることになりました。そして、エンドレス サイクリングの最も複雑なバグを取り除くための主なアイデアは、すべての場合に F を減少させないことを確認することです。このように、F は増加し続けます。

実用的な実装ソースを数週間後に共有します。

于 2013-01-31T23:18:05.910 に答える
2

この PDFは AIMA の SMA* セクションだと思います。本を持っていない人向けです。

最初に、ウィキペディアの疑似コードの行に明らかなエラーがあることに注意してください。

parent.successors.remove(parent);

そのはず

parent.successors.remove(badNode);

(親が自分の後継者になるにはどうすればよいでしょうか?)

「必要」とはどういう意味ですか?

その親がまだキューにない場合は、それをキューに追加する必要があります。そうしないと、このノードを再度検索することになります。

メモリ制限とは何ですか? キューのサイズまたは処理されたノード?

キューは、利用可能なすべてのメモリを占有します。処理されたノードのキューはありません。これがまさに、SMA* がノードを再走査してスタックする可能性がある理由です。

現在のノードに子がまったくない場合はどうなりますか?

ノードに子がない場合、それはリーフ ノードです。リーフ ノードの場合は、ターミナル ノードです。その場合、それがゴール ノードでない場合、その f-cost を無限大に設定し、その情報をその親に伝達します。

于 2009-12-13T20:47:41.907 に答える