反復的深化 スター (ID A*) は、メモリ境界検索です。s'私の質問は、ID A*のオープン状態から新しい状態に到達したときに、すでに「オープン状態」または「クローズ状態」にあるsかどうかをテストしないのはなぜですか?s'
「問題の状態のグラフ」はツリーであるため、状態が2回到達することはないため、たとえば数独などの問題の場合。ただし、他の問題、たとえば 8 パズルでは、何度も同じ状態になる可能性があります。したがって、状態がすでに「訪問」されているかどうか (オープン状態またはクローズ状態のいずれか) を確実にテストする必要があります。
このようなテストを実行する必要がある場合、考えられるすべての状態の大きなハッシュ テーブルを格納する必要があるため、ID A* はもはやメモリ バウンドではありません。
メモリ プロファイルを小さく保つために、s' が重複しているかどうかはテストしません。一般に、IDA *は実際には同じ状態を複数回展開します。
AI プログラミングとは、多くの場合、アルゴリズムをさまざまに調整して、ニーズに最適なものを見つけることです。新しい状態が既に訪問されている可能性が非常に高い場合は、状態が既に訪問されているかどうかを判断する余分なオーバーヘッドを追加すると、パフォーマンスが向上する可能性があります。ただし、アルゴリズムが問題にどのように適合するか、使用可能なメモリ、処理能力、スケーラビリティなど、考慮すべき他の多くの変数がある場合があります。優れた AI プログラマーであるということは、さまざまなアルゴリズムの長所と短所を知っており、各アルゴリズムのパフォーマンスに影響を与えるさまざまな問題の数を見てきたことを意味すると思います。ID A* のようなアルゴリズムは、ある状態に到達したかどうかを考慮しないように制限されていると考える必要はないと思います。再突入状態を考慮してパフォーマンスが向上すると思われる場合は、