8

AI（人工知能）で使用される検索のアルゴリズムのいくつかを理解するのにいくつかの問題があります。

  • A*とIDA*（Iterative Deeping A Star）の正確な違いは何ですか？ヒューリスティック関数だけですか？もしそうなら、私はまだIDA *がどのように機能するか想像できません..：/
  • IDA *はBFS（幅優先探索）と同じですか（拡張の深さが1レベルだけの場合、つまり、1レベルずつ「下」に移動します。IDA*とBFSの間に違いはありますか）
  • IDDFS（反復深化深さ優先探索）は、ヒューリスティック関数（ IDDFSの0に相当）を除いて、IDA *と同じですか。
  • IDDFSとは正確には何ですか？1レベル下に移動してから、 DFS（Depth-First Search）を使用しますか？その場合、この方法では、多くの状態が1つよりもはるかに多く計算（拡張）されます。または、次のようになります。特定の深さのDFSを使用し、「リーフ」（最後に拡張されたノード）を格納し、それらを反復処理して使用します。再びDFS（実際にはBFSですか？）
  • 「反復」はどこから来るのですか？私が見るように、IDDFSはまったく反復的ではなく、それでも再帰的であり、BFSとDFSを混合するだけですか？または私は間違っていますか？または、この「反復」は再帰の反対とは何の関係もありませんか？
  • IDA *の「反復」とは何ですか？

いくつか例を挙げていただけますか？私はこれらのアルゴリズムについて一日中読み、それらの長所と短所、複雑さなどを知っていますが、良い例を見つけることができませんでした（A*を除いて;BFSとDFSを知っています、他は私を悩ませます）。さまざまな場所でIDA*の擬似コードを見つけましたが、それらはすべて完全に異なっていました。

例はアルゴリズムを理解するための最良の方法です。しかし、私は見つけることができません。TopCoderでさえ、IDA*について何も見つかりませんでした。

ウィキの記事を読んだのですが、何か新しいものを探しています（：

どうもありがとう！

編集： ここにいくつかの素晴らしい記事がありますが、それらは理論的すぎます。例も具体的なこともありません。しかし、それでも非常に便利です。私はそれらをお勧めします（=

4

1 に答える 1

4

反復的な深化の深さ優先検索から始めましょう。

深さ優先検索は効率的ですが、すぐに正しい答えが見つかるとは限りません。したがって、深さ 1 まで DFS を実行します。答えが見つからない場合は、深さ 2 まで実行します。答えが見つかるまで繰り返すか、あきらめることにします。長さ N のパスがある場合、長さ N + 1 のパスを検索することはないため、これにより、検索ツリーで最短パスが自動的に得られます。

実装するために行う必要があるのは、深さ優先検索を変更して、N ノードの深さになるようにし (つまり、N の深さの場合は新しいノードを生成しない)、N を増やして呼び出すことです。 N の値以上のものを保存し、DFS に対して行うことは何でも保存します。

反復には、検索の深さを繰り返し増やすことが伴います。分岐係数が 2 より大きい場合、パフォーマンスは驚くほど良好になる可能性があります。その場合、深さ制限のある DFS のコストのほとんどは到達した最低レベルにあるためです。

最初に DFS の反復的な深化を学び、それを IDA* に適用します。私は 15 年以上前にこれらの検索に関する初期の Korf の論文を読みましたが、IDA* がどのようにうまく機能するかは覚えていませんが、主な問題は、そもそも反復深化を理解していないことです。

于 2010-12-07T22:07:47.393 に答える