DFID（Dept-First Iterative Deeping）対IDA *（反復盗聴A *）

Question

これらの2つのアルゴリズムの利点と欠点は何ですか？ AddEmUp C++を解決したいと思っていますが、（IDAまたはDFID）アルゴリズムを使用するかどうかはわかりません。

私が見つけた最高の記事はthis oneですが、それは古すぎるようです - 93。それより新しい？

私はIDA *が良いと思うけど...？他のアイデア？

任意のアイデアや情報が参考になります。

ありがとうございます！ （：

EDIT： IDA *とアルゴリズムの良い説明についていくつかの良い記事

EDIT2：？？か、そのゲームのためのいくつかの良いヒューリスティック機能私はどのようにいくつかを考えるには考えています。/

Answer 1

The Russel & Norvigの本は、これらのアルゴリズムに関する優れたリファレンスであり、私はlarsmansにそれを提案するためのバーチャルハイレベルを与えます。しかし、私はIDA *がA *よりプログラムするのがかなり難しいとは考えていません。私は、スライディングブロックパズルを解決するためにAIを書く必要があったプロジェクトのためにそれをやってきました.N x Nグリッドの番号付きタイルを持ち、1つのフリースペースを使ってタイルをスライドさせて昇順で

リコール：

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

TotalCost = PathCost + Heuristic. 

G（N）=パスコスト、現在の状態に初期

H（N）=ヒューリスティック、現在の状態からコストの見積もりからの距離終了状態にする。許容ヒューリスティックである（したがってA *の最適性を保証する）ためには、いかなる場合でもコストを過大評価することはできません。 See this question for more info on the effects of overestimating/underestimating heuristics on A*。

は、反復は、あなたがを通過することを許可されたノードのF値の上限である*ちょうど A *を深めることを覚えておいてください。このFLimitは外側の反復ごとに増加します。各反復であなたは深化です。

Here's my C++ code前述のスライドブロックパズルを解くためにA *とIDA *の両方を実装します。カスタムのComparatorでstd::priority_queueを使用して、F値によって優先順位が付けられたキューにパズル状態を格納することがわかります。また、A *とIDA *の唯一の違いは、FLimitのチェックと、これを増やす外側のループの追加であることに注意してください。FLimit。私はこれがこの主題についていくつかの光を放つのを助けることを望む。

Answer 2

チェックアウトRussell & Norvig、第3章と第4章、およびIDA *が正しくプログラムすることは困難であることを認識しています。あなたは再帰的な最良優先探索（RBFSを）しようとする場合があり、また、* R & N、または、昔ながらのAで説明後者はstd::priority_queueを使用して実装できます。

IIRC、R & Nは第1版でIDA *を記述し、次に第2版でRBFSに置き換えました。私はまだ第3版を見ていない。

2回目の編集に関して、私はゲームを見ていませんが、ヒューリスティックスを導く良い手順は、の緩和された問題です。ヒューリスティックが容易に表現され実行される（そして安価に計算できる）バージョンを導き出すまで、ゲームのルールを削除します。または、ボトムアップの方法では、メインルールをチェックして、どのルールが容易なヒューリスティックであるかを確認してから、それを試して、必要に応じて他のルールを追加します。

Answer 3

DFIDは、ヒューリスティック関数が定数0であるIDA *の特別なケースです。言い換えれば、ヒューリスティックを導入するための規定はない。ヒューリスティックを使用せずに問題が解決できないほど問題が少ない場合は、IDA *（またはA *ファミリーの他のメンバー）を使用するしかありません。つまり、IDA *は本当に難しいことではありません.AIMAの著者によって提供されたimplementationは、Lispコードの約半ページです。私は、C++の実装はそれを2倍以上とすべきではないと思います。