dfid（dept-first iterative deeping）vs. ida*（iterative-deeping a*）

Question

これら2つのアルゴリズムの利点と短所は何だろうと思います。書きたい Addemup C ++は解決しましたが、どの（IDAまたはDFID）アルゴリズムを使用するかはわかりません。

私が見つけた最高の記事はです これです, 、しかし、それは古すぎるようです - '93。新しいものはありますか？

Ida*の方が良いと思いますが..？他にアイデアはありますか？

どんなアイデアや情報が役立ちます。

ありがとう ！ （：

編集： Ida*に関するいくつかの良い記事とアルゴリズムの良い説明？

編集2： または、そのゲームのいくつかの良いヒューリスティック機能？私はいくつかのことを考える方法がわかりません：/

Answer 1

Russel＆Norvigの本は、これらのアルゴリズムに関する優れた参照であり、Larsmansにそれを提案するための仮想ハイファイブを与えます。しかし、私はIDA*がA*よりもプログラムするのが難しい方法であることに同意しません。スライディングブロックパズルを解決するためにAIを書かなければならなかったプロジェクトのためにそれをやった - 番号付きタイルのn x nグリッドを持っているという馴染みのある問題、そして単一の空きスペースを使用してタイルをスライドさせるまで、昇順で。

想起：

F(n) = g(n) + h(n).

TotalCost = PathCost + Heuristic.

g（n）=パスコスト、初期状態から現在の状態までの距離

H（n）=ヒューリスティック、現在の状態から終了状態へのコストの推定。許容可能なヒューリスティック（したがって*の最適性を確保する）になるために、いずれにせよ、コストを過大評価することはできません。 この質問を参照してください。.

a*を深める反復的であることを忘れないでください a*ノードのf値に制限がある場合、トラバースが許可されています. 。これ FLimit 外側の反復ごとに増加します。反復ごとにあなたがいます 深化 検索。

これが私のC ++コードです A*とIDA*の両方を実装して、前述のスライドブロックパズルを解決します。あなたは私がaを使用していることがわかります std::priority_queue f値で優先されるキューにパズル状態を保存するカスタムコンパレーターを使用します。また、A*とIDA*の唯一の違いは、 FLimit これを増やす外側のループを確認します FLimit. 。これがこのテーマに光を当てるのに役立つことを願っています。

Answer 2

チェックアウト ラッセル＆ノーヴィグ, 、第3章と第4章、およびIDA*が正しくプログラムするのが難しいことを認識しています。 R＆Nまたはプレーン古いa*によっても説明されている再帰的なベストファースト検索（RBFS）を試してみてください。後者はanを使用して実装できます std::priority_queue.

IIRC、R＆Nは初版でIDA*を説明し、2番目のRBFSに置き換えました。私はまだ第3版を見ていません。

あなたの2回目の編集に関して、私はゲームを調べていませんが、ヒューリスティックを導き出すための良い手順は リラックスした問題. 。ヒューリスティックが簡単に表現され、実装されている（および計算が安く）バージョンを導き出すまで、ゲームのルールを取り除きます。または、ボトムアップアプローチに従って、主なルールをチェックして、どれが簡単なヒューリスティックを認めているかを確認し、それを試して、必要に応じて他のルールを追加します。

Answer 3

DFIDは、ヒューリスティック関数が定数0です。言い換えれば、ヒューリスティックを導入するための規定はありません。問題がヒューリスティックを使用せずに解決できるほど十分に小さい場合、Ida*（またはA*ファミリーの他のメンバー）を使用する以外に選択肢がないようです。そうは言っても、Ida*はそれほど難しくありません： 実装 AIMAの著者によって提供されるのは、LISPコードの約半分のページにすぎません。 C ++の実装には2倍以上かかることはないと思います。