一貫性のある許容可能なヒューリスティック
Consistent Admissible Heuristics
解決：
ラッセルとノーヴィグが指摘するように 人工知能：現代的なアプローチ （最も一般的に使用されるAI教科書）許容できるが一貫性のないヒューリスティックを考え出すのは困難です。
明らかに、グラフ内のノードの値を選択して、ノードが表すヒューリスティックが許容可能であるが一貫性がないようにすることができます。 Felner et alによるこの論文には、これが可能な2つの方法の良い例がありますが、少し密度が高いので、要約します。
- このヒューリスティックはで一貫性がありません
c1は、親ノードよりも目標に到達するためのコストに低い（つまり、情報量の少ない）下限を与えているためです。親ノードを介して目標に到達するためのコスト見積もりは少なくとも10です（パスのコストがpは5であり、ヒューリスティック推定はpも5）です。目標を達成するためのコスト見積もりただし、c1はわずか8です（親のコスト（5）、親からのパスのコスト（1）、およびヒューリスティックな見積もりc1（2））。 - このグラフは無向であるため、このヒューリスティックは次の場合にも一貫性がありません。
c2、から行くのでc2からpには上記と同じ問題があります。
Felner et alは、許容できるが一貫性のないヒューリスティックのいくつかの具体的な例も提供しています。 8パズルの問題を考えてみましょう。
このパズルには、1から8までの番号が付けられた8つのスライディングタイルと、1つの空きスペースがあります。タイルは順不同で始まります（左の画像のように）。目標は、タイルを空のスペースにスライドさせることによって、パズルを右上に示す状態にすることです。この問題の古典的なヒューリスティック（各タイルから想定される場所までのマンハッタン距離）は許容され、一貫性があります。
ただし、別のヒューリスティックを思い付く可能性があります。マンハッタンの1、2、3からゴール状態にあるはずの場所までの距離（つまり、平方数）を見たいだけかもしれません。ヒューリスティックは、すべてのタイルのマンハッタン距離よりも情報量が少ないものの、それでも許容可能で一貫性があります。
ただし、追加の正方形のグループ（おそらく、5、6、および7）を選択するとします。次に、各ノードでヒューリスティックを計算する方法は、これらのセット（1、2、および3）の1つをランダムに選択することです。または（5、6、および7）で、ゴール位置までのマンハッタン距離を計算します。このヒューリスティックは まだ許容されます -ゴール状態に到達するために必要な移動数を過小評価または一致させることしかできません。しかし、それは 一貫性がなくなった -各ノードのヒューリスティック推定値の間に明確な関係はありません。
長い間死んでいますが、とにかく2セントを差し上げます。これを考える最も簡単な方法は、許容可能なヒューリスティックは、特定の定義された目標ノードに到達するときにオーバーシュートできないと言うのに対し、一貫したヒューリスティックは、任意のノードに到達するときにオーバーシュートできないと言うことだと思います。これにより、関係が明確になります。ゴールノードはあるノードであるため、一貫したヒューリスティックが許容されます。ただし、admissibleは1つのノードに対してのみこのプロパティを保証するため、admissibleは一貫性を意味するものではありません。
一貫性のあるヒューリスティックは、三角不等式に従う許容可能なヒューリスティックと考えるのが最善です。
コスト（a-> c）b）+コスト（b-> c）コストは隣接ノード間の実際のコストを使用して計算され、それ以外の場合はヒューリスティックを使用して計算されることを理解した上で、検索スペース内の任意の3つのノードa、b、およびcについて。