許容可能なヒューリスティック

コンピュータサイエンス、特に経路探索に関連するアルゴリズムでは、ヒューリスティック関数は、目標に到達するコストを過大評価しない、つまり、目標に到達するために推定されるコストが経路上の現在の地点からの最低コストよりも高くない場合に許容されると言われます。^{[ 1 ]}言い換えれば、下限として機能する必要があります。

これは一貫性のあるヒューリスティクスの概念に関連しています。一貫性のあるヒューリスティクスはすべて許容可能ですが、許容可能なヒューリスティクスすべてが一貫性があるとは限らないのです。

情報探索アルゴリズムでは、許容可能なヒューリスティックを用いて目標状態に到達するコストを推定します。ヒューリスティックが探索問題に対して許容可能であるためには、推定コストは常に目標状態に到達する実際のコスト以下でなければなりません。探索アルゴリズムは、許容可能なヒューリスティックを用いて、現在のノードから目標状態への最適な経路を推定します。例えば、A*探索では、評価関数（ここで） ${\displaystyle n}$現在のノードは：

${\displaystyle f(n)=g(n)+h(n)}$

どこ

${\displaystyle f(n)}$＝評価関数。

${\displaystyle g(n)}$= 開始ノードから現在のノードまでのコスト

${\displaystyle h(n)}$＝現在のノードから目標地点までの推定コスト。

${\displaystyle h(n)}$はヒューリスティック関数を使用して計算されます。許容できないヒューリスティックを使用すると、A* アルゴリズムは、の過大評価により、探索問題の最適解を見落とす可能性があります。${\displaystyle f(n)}$。

${\displaystyle n}$ノードです

${\displaystyle h}$ヒューリスティック

${\displaystyle h(n)}$コストは以下のように示されます${\displaystyle h}$目標に到達する${\displaystyle n}$

${\displaystyle h^{*}(n)}$目標に到達するための最適なコストは${\displaystyle n}$

${\displaystyle h(n)}$以下の場合は許容される。${\displaystyle \forall n}$

${\displaystyle h(n)\leq h^{*}(n)}$

許容可能なヒューリスティックは、問題の緩和版から、あるいは問題のサブ問題に対する正確な解を格納するパターンデータベースからの情報から、または帰納的学習法を用いることによって導き出すことができる。

15パズル問題には、許容されるヒューリスティックの2つの異なる例が適用される。

• ハミング距離
• マンハッタンまでの距離

ハミング距離は、配置ミスしたタイルの総数です。タイルを正しく並べるために必要な移動回数は、配置ミスしたタイルの数以上であるため（配置されていないタイルはそれぞれ少なくとも1回は移動させる必要がある）、このヒューリスティックが妥当であることは明らかです。目標（正しい順序のパズル）に到達するまでのコスト（移動回数）は、パズルのハミング距離以上になります。

パズルのマンハッタン距離は次のように定義されます。

${\displaystyle h(n)=\sum _{\text{すべてのタイル}}{\mathit {距離}}({\text{タイル、正しい位置}})}$

以下のパズルを考えてみましょう。プレイヤーは、数字が正しい順序になるように各タイルを移動させたいと考えています。この場合、マンハッタン距離は許容可能なヒューリスティックです。なぜなら、すべてのタイルは、自身と正しい位置との間の少なくともその数だけ移動させる必要があるからです。^{[ 2 ]}

添え字は各タイルのマンハッタン距離を示しています。表示されているパズルの合計マンハッタン距離は次のとおりです。

${\displaystyle h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36}$

許容可能なヒューリスティックが、反復ごとに複数の候補パスのうち評価値（現在のコスト＋ヒューリスティック）が最も低いパスのみを進め、探索が目標に到達した時点で終了し、そして重要なことに、終了する前にすべての最適パスを閉じるアルゴリズムで使用される場合（特別な注意を払わなければ、A* 探索アルゴリズムでこのようなことが可能になる^{[ 3 ]}）、このアルゴリズムは最適パスでのみ終了できます。その理由を理解するために、次の背理法による証明を考えてみましょう。

このようなアルゴリズムが、真のコストがT _trueであるパス T で終了し、真のコストがS _trueである最適パス S よりも大きいパス Tで終了したと仮定します。これは、終了する前に、T の評価コストが S の評価コスト以下であったことを意味します (そうでなければ S が選択されていたはずです)。これらの評価コストをそれぞれT _evalとS _{eval と}します。上記は次のようにまとめられます。

S_真< T_真

T _eval ≤ S _eval

ヒューリスティックが許容可能であれば、この最後から2番目のステップでT _eval = T _trueとなります。なぜなら、T に対するヒューリスティックによる真のコストの増加は許容不可能であり、ヒューリスティックは負の値をとることができないからです。一方、許容可能なヒューリスティックではS _eval ≤ S _trueが必要となりますが、これは上記の不等式と組み合わせるとT _eval < T _true、より具体的にはT _eval ≠ T _trueとなります。T _evalとT _trueは等しくもあり等しくもないということはあり得ないので、我々の仮定は誤りであったに違いありません。したがって、最適経路よりもコストの高い経路で終了することは不可能であるはずです。

例として、^{[ 4 ]}次のようなコストがあるとしましょう（ノードの上/下のコストはヒューリスティック、エッジのコストは実際のコストです）。

0 10 0 100 0 スタート ---- O ----- ゴール | | 0| |100 | | O ------- O ------ O 100 1 100 1 100

したがって、予想総コストが${\displaystyle f(n)}$、 は${\displaystyle 10+0=10}$そうすれば、目標は候補者となり、${\displaystyle f(n)}$等しい${\displaystyle 10+100+0=110}$そうすれば、明らかに下位のノードを1つずつ選択し、その後更新された目標が続きます。なぜなら、それらはすべて${\displaystyle f(n)}$より低い${\displaystyle f(n)}$現在の目標、つまり彼らの${\displaystyle f(n)}$は${\displaystyle 100,101,102,102}$つまり、目標は候補の一つではあったものの、他にもっと良い経路が存在したため、それを選ぶことはできなかった。このように、許容可能なヒューリスティックを用いることで最適性を確保できる。

ただし、許容可能なヒューリスティックは最終的な最適性を保証できるものの、必ずしも効率的であるとは限らないことに注意が必要である。

• 一貫性のあるヒューリスティック
• ヒューリスティック関数
• 検索アルゴリズム