■

ε-admissible Searchについて。
A*の探索には式、f()=g()+h()が用いられる。
gはノードまで実際にかかったコスト。
hはヒューリスティックで目的地までの見積もりコスト。通常、幾何学的な距離みたいな単純な式が用いられる。

hの見積もりが実際のコストよりも小さい場合、A*が最短経路を見つけることは数学的に保障されている。逆にいうと、見つかった経路の最適性を保障するためにはこの条件が満たされている必要がある。
hの見積もりが実際にかかるコストに近いほどA*で展開されるノードは少なくなる。で、h()=0の場合ダイクストラ法。よって一般に最短経路を求める場合、幾何学的な距離みたいなnot overestimatedな見積もり距離h()が存在する場合はA*の方が速い。

で、逆に見積もりが実際のコストよりも過剰な場合はどうなるか。
一般に、展開されるノード数が減り探索は高速になるが、得られた経路の最適性は保障されない。

過剰に見積もるっていってもこのままじゃ定式化できないので、εって係数を加えて
f()=g()+ ε *h()って式にする。hは通常のA*と同じくadmissible。よってεの値がどれくらい過剰に見積もるのかを決める。
ε=1の時A*と同様。でε>1ならば最短経路は得られないが探索量が減って高速。得られる経路は実際の最短経路と比べ、最悪の場合でもε倍。
後、式見てればわかるけど、f()全体におけるg()の割合が、探索が進むにつれて大きくなる。よって過剰に見積もられたhが影響するのは主に探索初期の部分。

以上より、ε-admissible Searchはεを調整することによって計算速度と経路の質とのバランスが取りやすいことが特徴。あと最悪の場合でもε倍までって制約があること。
あと、εを定数ってことにしたけど探索の深さに合わせて変化させてく方法も。

で、この辺の研究が1970年代に行われたらしい。