ヒューリスティック関数とは、探索問題において現在の状態からゴールまでに必要なコストや距離を大まかに見積もる評価関数のことです。探索範囲を絞り込み、最適な解を効率的に見つけるために利用されます。
ヒューリスティック関数とは
ヒューリスティック関数は、探索問題において「ゴールまであとどれくらいコストがかかるか」を経験的・直感的に予測する評価関数です。
詳しく解説
グラフ探索や探索木を用いた問題解決において、すべてのルートを総当たりで調べると計算量が爆発的に増大します。ヒューリスティック関数（通常は記号h(n)で表記）は、現在のノードから目標ノードまでの推定残りコストを計算することで、見込みの高い経路を優先的に探索できるようにします。特にA*アルゴリズムや最良優先探索などの探索アルゴリズムにおいて中核的な役割を果たします。関数の設計において、推定コストが決して実際の最小コストを超えない性質を許容性と呼び、この性質が満たされるとA*アルゴリズムは常に最適解を見つけることが保証されます。
具体例・使われ方
カーナビの経路探索で、道路網の実際の曲がりくねりを無視して目的地までの直線距離（ユークリッド距離）を見積もりとして利用するケースや、グリッドマップ上での移動におけるマンハッタン距離の計算が代表的です。また、8パズルなどのパズルゲームで「正解の位置にないピースの数」をゴールまでの残り手数として見積もる際にも用いられます。
似た用語との違い
コスト関数が「スタート地点から現在地までに実際に消費したコスト」を正確に計算するのに対し、ヒューリスティック関数は「現在地からゴールまでに必要と予想されるコスト」を推定する点で異なります。また、厳密な数理最適化の目的関数とは異なり、計算の高速化のために近似や経験則を取り入れている点も特徴です。
注意点
ヒューリスティック関数による推定値が不正確すぎると、探索効率が極端に低下したり、最適解が見つからなくなったりします。また、見積もりを正確にしようとして関数の計算自体が複雑になりすぎると、探索全体の実行時間がかえって長くなるというトレードオフに注意が必要です。