一貫したヒューリスティック

人工知能における経路探索問題の研究では、ヒューリスティック関数の推定値が、隣接する頂点から目標までの推定距離とその隣接頂点に到達するためのコストの合計値以下である場合、その関数は一貫している、または単調であると言われます。

正式には、すべてのノードNとNの各後続 ノード Pについて、 Nからゴールに到達するための推定コストは、 Pに到達するためのステップ コストとPからゴールに到達するための推定コストの合計よりも大きくなりません。つまり、次のようになります。

${\displaystyle h(N)\leq c(N,P)+h(P)}$そして

${\displaystyle h(G)=0.\,}$

どこ

• hは一貫したヒューリスティック関数である
• Nはグラフ内の任意のノードである
• PはNの子孫である
• Gは任意の目標ノード
• c(N,P)はNからノードPに到達するコストである。

非公式には、各ノードi は、次のノードに到達するためのコストを考慮して、常にノードi+1での推定値以下となる推定値を提供します。

一貫したヒューリスティックも許容される。つまり、目標に到達するためのコストを過大評価することはない（ただし、逆は常に真であるわけではない）。非負のエッジを想定すると、これは帰納法によって簡単に証明できる。^[1]

を目標ノードの推定コストとします。これは、基本条件が 0 ≤ 0 として自明に真であることを意味します。各項の展開により、ヒューリスティックは一貫しているため、与えられた項は真のコスト に等しいため、真のコストによって上限が定められているため、任意の一貫したヒューリスティックも許容されます。 ${\displaystyle h(N_{0})=0}$${\displaystyle h(N_{i+1})\leq c(N_{i+1},N_{i})+h(N_{i})\leq c(N_{i+1},N_{i})+c(N_{i},N_{i-1})+...+c(N_{1},N_{0})+h(N_{0})}$${\displaystyle \sum _{i=1}^{n}c(N_{i},N_{i-1})}$

逆は明らかに真ではありません。なぜなら、常に真のコストより低いヒューリスティックを構築できるものの、それにも関わらず、たとえば、最も遠いノードから近づくにつれてヒューリスティック推定値を増やし、推定値がせいぜい真のコスト になったときに とするなど、一貫性がないからです。 ${\displaystyle h(N_{i})}$${\displaystyle h^{*}(N_{i})}$${\displaystyle h(N_{i-1})=h(N_{i})-c(N_{i},N_{i-1})}$

一貫性のあるヒューリスティックスは、部分解の推定最終コストが任意のパスに沿って単調に非減少であるため、単調と呼ばれます。ここで、は開始ノードからへの最適パスのコストです。ヒューリスティックスが一貫性を持つためには、三角不等式に従うことが必要かつ十分です。 ^[2]${\displaystyle f(N_{j})=g(N_{j})+h(N_{j})}$${\displaystyle g(N_{j})=\sum _{i=2}^{j}c(N_{i-1},N_{i})}$${\displaystyle N_{1}}$${\displaystyle N_{j}}$

A*探索アルゴリズムでは、一貫性のあるヒューリスティックを使用するということは、ダイクストラのアルゴリズムが最短経路問題を解く際に要求するのと同じ条件（負のコストのエッジがない）で、ノードが拡張されると、そのノードに到達するコストが可能な限り低くなることを意味します。実際、探索グラフに一貫性のある のコストが与えられている場合、A* はダイクストラのアルゴリズムを使用したそのグラフ上での最良優先探索と同等です。^[3] 許容されるヒューリスティックが一貫していないというまれな事態が発生した場合、ノードは、新しい最良の（これまでの）コストが達成されるたびに、繰り返し拡張する必要があります。 ${\displaystyle c'(N,P)=c(N,P)+h(P)-h(N)}$${\displaystyle h}$

与えられたヒューリスティックが許容できるが一貫性がない場合、次の式を使用して、経路に沿ったヒューリスティック値を人為的に単調非減少に強制することができます。 ${\displaystyle h}$

${\displaystyle h'(P)\gets \max(h(P),h'(N)-c(N,P))}$

の代わりに のヒューリスティック値として、 はパス上の直前のノード、 です。このアイデアは László Mérō ^[4]によるもので 、現在では pathmax として知られています。一般に信じられていることとは反対に、pathmax は許容可能なヒューリスティックを一貫性のあるヒューリスティックに変換するものではありません。たとえば、A* が pathmax と許容可能だが一貫性のないヒューリスティックを使用する場合、最初に展開されたときにノードへの最適なパスがあることは保証されません。^[5]${\displaystyle P}$${\displaystyle h(P)}$${\displaystyle N}$${\displaystyle P}$${\displaystyle h'(start)=h(start)}$

• 許容されるヒューリスティック