Russel & Norvig の本は、これらのアルゴリズムに関する優れたリファレンスです。しかし、IDA* が A* よりもかなり難しいという点には同意しません。スライディング ブロック パズルを解くために AI を書かなければならないプロジェクトのために、これを行いました。これは、番号付きのタイルの N x N グリッドを持ち、単一の空きスペースを使用して、タイルが移動するまでタイルをスライドさせるというおなじみの問題です。昇順で。
想起：
F(n) = g(n) + h(n).
TotalCost = PathCost + Heuristic.
g(n) = パス コスト、初期状態から現在の状態までの距離
h(n) = ヒューリスティック、現在の状態から最終状態までのコストの見積もり。許容できるヒューリスティックである (したがって A* の最適性を保証する) ために、コストを過大評価することはできません。A* に対するヒューリスティックの過大評価/過小評価の影響の詳細については、この質問を参照してください。
Iterative Deepening A* は単なるA* であり、通過できるノードの F 値に制限があることに注意してください。これFLimitは、外側の反復ごとに増加します。反復するたびに、検索を深めています。
前述のスライディング ブロック パズルを解くために A* と IDA* の両方を実装するC++ コードを次に示します。std::priority_queueカスタム Comparator でを使用して、F 値によって優先順位付けされたキューにパズルの状態を格納していることがわかります。また、A* と IDA* の唯一の違いは、FLimitチェックの追加と、 this をインクリメントする外部ループであることにも注意してくださいFLimit。これがこの問題に光を当てるのに役立つことを願っています。
Russell＆Norvigの第3章と第4章をチェックして、IDA*を正しくプログラムするのは難しいことを理解してください。R＆Nによっても説明されている再帰的最良優先探索（RBFS）、または単純な古いA*を試してみることをお勧めします。後者は、を使用して実装できますstd::priority_queue。
IIRC、R＆Nは、第1版でIDA *について説明し、第2版でそれをRBFSに置き換えました。私はまだ第3版を見ていません。
2回目の編集に関しては、ゲームについては調べていませんが、ヒューリスティックを導出するための適切な手順は、問題を緩和することです。ヒューリスティックを簡単に表現および実装できる（そして計算が安価な）バージョンを導出するまで、ゲームのルールを取り除きます。または、ボトムアップアプローチに従って、メインルールをチェックして、どれが簡単なヒューリスティックを許可するかを確認し、それを試して、必要に応じて他のルールを追加します。
DFID は、ヒューリスティック関数が定数 0 である IDA* の特殊なケースです。つまり、ヒューリスティックを導入するための規定がありません。問題がヒューリスティックを使用せずに解決できるほど小さくない場合は、IDA* (または A* ファミリーの他のメンバー) を使用するしかないようです。とはいえ、IDA* はそれほど難しくありません。AIMA の作成者が提供する実装は、Lisp コードの約半分のページにすぎません。C++ の実装では、その 2 倍以上かかることはないと思います。