ヒューリスティック探索とA*

ヒューリスティック探索は、目標までの残りのコストを問題固有の推定値として利用し、どの状態を優先的に探索するかを導きます。A*はその典型的なアルゴリズムであり、これまでに費やしたコストと目標までの推定コストの合計の順に状態を展開します。

Definition

ヒューリスティック探索とは、開始点からの既知のコストと残りのコストのヒューリスティック推定値を組み合わせた評価関数を用いてフロンティアを順序付ける情報付き探索です。A*はf(n) = g(n) + h(n)を使用し、hが許容可能である場合に最適です。

Scope

このトピックでは、ベストファースト探索とA*アルゴリズムを中心とした情報付き（ヒューリスティック）探索戦略について扱います。これには、ヒューリスティック関数（許容性、一貫性/単調性）の設計と特性、これらの特性がもたらす最適性と効率性の保証、および反復深化A*（IDA*）などのメモリ制限付きバリアントが含まれます。ヒューリスティクスがどのように構築されるか（緩和された問題、パターンデータベース）と、それらが精度と計算のトレードオフをどのように行うかについても考察します。データからのヒューリスティクス学習は、機械学習のサブフィールドに属します。

Core questions

• ヒューリスティックを許容可能にするものは何か、そしてなぜ許容可能性がA*の最適性を保証するのか？
• 一貫性（単調性）は、保証をどのように強化し、ノードの再展開をどのように防ぐのか？
• 例えば、問題の緩和されたバージョンから、どのようにして良いヒューリスティクスが設計されるのか？
• IDA*のようなメモリ制限付きバリアントは、限られた空間で最適性をどのように維持するのか？

Key concepts

• 評価関数 f = g + h
• 許容可能なヒューリスティック
• 一貫性のある（単調な）ヒューリスティック
• 欲張りベストファースト探索
• A*探索
• 反復深化A*（IDA*）
• ヒューリスティック優越性
• 緩和された問題とパターンデータベース

Key theories

許容可能なヒューリスティックの下でのA*の最適性

ヒューリスティックhが真の残りコストを決して過大評価しない場合、A*はf = g + hを増加させながらノードを展開し、最小コスト経路を返すことが保証されます。同じヒューリスティック情報を使用するアルゴリズムの中で、A*は最適に効率的です。

緩和によるヒューリスティック設計

許容可能なヒューリスティクスは、問題の緩和されたバージョン（行動に対する制約が少ないもの）を解くことによって系統的に導き出すことができます。これは、より簡単な問題の正確なコストが元の問題の下限となるためです。優越的な（より情報量の多い）ヒューリスティクスは、より少ないノードを展開します。

メモリ制限付きヒューリスティック探索

反復深化A*は、増加するfコスト閾値によって制限された連続的な深さ優先探索を実行し、解の深さに対して線形なメモリでA*のような最適性を達成します。

Clinical relevance

ヒューリスティック探索は、地図やゲームにおける経路探索、ロボット工学における動作計画、自動プランナーやパズルソルバー内の探索エンジンを支えています。ヒューリスティック設計の実践的な技術は、大規模な問題が許容可能な時間内に解決可能であるかを直接的に決定します。

History

A*アルゴリズムはHart、Nilsson、Raphael（1968）によって導入され、ヒューリスティック探索に形式的な最適性の基礎を与えました。Pearlの1984年のモノグラフ『Heuristics』は決定的な理論的考察を提供し、Korfの1985年のIDA*はA*のメモリコストの問題に対処しました。これらの成果は、AI教育における中核的な教材であり続けています。

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

許容可能なヒューリスティックとは何ですか？

ヒューリスティックは、どの状態から目標に到達するまでの真のコストを決して過大評価しない場合、許容可能であると言えます。許容可能性は、A*が最適な（最小コストの）解を見つけることを保証する条件です。

欲張りベストファースト探索とA*の違いは何ですか？

欲張りベストファースト探索は、ヒューリスティック単独（h）に基づいて目標に最も近いと思われる状態を展開します。これは高速ですが、最適解から大きく外れる可能性があります。A*は、これまでに発生した実際のコスト（g）を追加し、f = g + hによって展開します。これにより、ヒューリスティックが許容可能である場合に最適性が維持されます。