検索アルゴリズムを理解するためのヘルプが必要です(A*、IDA*、DFS、BFS、IDDFSなど)
-
09-10-2019 - |
質問
AI(人工知能)で使用される検索のアルゴリズムの一部を理解するいくつかの問題があります。
- 間の正確な違いは何ですか * と ida*(星の反復深い星)?ヒューリスティックな機能ですか?もしそうなら、私はまだida*の仕組みを想像することはできません..:/
- は Ida* と同じ BFS(幅広い検索) (拡張の深さが1レベルしかない場合、つまり、1つのレベルを「ダウン」しているだけです。間に違いはありますか Ida* と BFS)
- は IDDFS(反復深度深度検索) と同じ Ida*, 、ヒューリスティック関数を除いて(これは0に相当します iddfs)
- 正確には何ですか iddfs - 下に移動します 一つだけです レベル、次に使用します DFS(深さfirst検索)?もしそうなら、このようにして多くの州が計算され(拡張された)(拡張)、それはこのようなものです - 使用 - DFS 特定の深さで、「葉」(最後の拡張されたノード)を保存し、それらを繰り返して使用します DFS 繰り返しますが(実際、そうです BFS?)
- どこ "反復的「出身ですか?私が見るように、 iddfs まったく反復的ではありません、それはまだ再帰的であり、ただミックスするだけです BFS と DFS?または私は間違っていますか?またはこれ「反復的「再帰の反対とは何の関係もありませんか?
- とは "反復的" にとって Ida* ?
いくつかの例を提供していただけませんか?私はこれらのアルゴリズムについて一日中読みました、私はそれらの利点と欠点、複雑さなどを知っていますが、私は良い例を見つけることができませんでした(*;私はBFSとDFSを知っています、他の人は私を悩ませます)。私はさまざまな場所でida*の擬似コードを見つけましたが、それらはすべて完全に異なっていました。
例は、アルゴリズムを理解するための最良の方法ですが、見つかりません。でさえ トップコダー Ida*については何も見つかりませんでした。
Wikiの記事を読んで、何か新しいものを探しています(:
どうもありがとう!
編集: ここでいくつかの素敵な記事, 、しかし、それらはあまりにも理論的です。例はありません、具体的なことはありません。しかし、それでも非常に便利です。私はそれらをお勧めします(=
解決
反復深さの深さの深さ検索から始めましょう。
アイデアは、深さの最初の検索は効率的であるが、必ずしもすぐに正しい答えにヒットするわけではないということです。したがって、DFSを1の深さまで行います。答えが見つからない場合は、2の深さまでそれを行います。答えが見つかるまで繰り返します。長さnのいずれかがある場合、長さn + 1のパスを検索しないため、検索ツリーの最短パスが自動的に提供されます。
実装するために必要なことは、深さ第一検索を変更することです。これにより、nノードが深くなります(つまり、深くn深い場合は新しいノードを生成しないでください)。 nの値とDFSのために何をするかは何でも保管してください。
反復は、検索の深さを繰り返し増加させることに伴います。その場合、深さに縛られたDFSのコストのほとんどが最も低いレベルに達したため、パフォーマンスは驚くほど良好である可能性があります。
最初に反復的なDFSを学び、それをIDA*に適用します。私は15年以上前にこれらの検索に関する初期のKorf論文を読みましたが、Ida*がどのようにうまく機能するか覚えていませんが、あなたの主な問題は、そもそも反復的な深化を理解していないことです。