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

Computer science pathfinding concept

コンピュータサイエンス、特に経路探索に関連するアルゴリズムにおいて、ヒューリスティック関数は、目標到達にかかるコストを決して過大評価しない場合、つまり目標到達にかかるコストの見積りが経路上の現在の地点から考えられる最低コストよりも高くない場合、許容されると言われます。^[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)}$

工事

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

例

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

• ハミング距離
• マンハッタン距離

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

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

${\displaystyle h(n)=\sum _{\text{all tiles}}{\mathit {distance}}({\text{tile, correct position}})}$

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

4 3	6 1	3 0	8 1
7 2	12 3	9 3	14 4
15 3	13 2	1 4	5 4
2 4	10 1	11 1

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

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

最適性の証明

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

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

S_真< T_真

T_評価≤ S_評価

もし我々のヒューリスティックが許容可能であれば、この最後から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 | | ○ ------- ○ ------ ○100 1 100 1 100

したがって、期待される総コスト、つまりは であるため、明らかに最上位の中間ノードから開始することになります。次に、目標ノードは の候補となり、は に等しくなります。次に、明らかに最下位ノードを順に選択し、その後、更新された目標ノードを選択します。なぜなら、それらのノードはすべて、現在の目標のよりも低い、つまりだからです。つまり、目標ノードが候補であっても、より良い経路がまだ存在するため、それを選択することはできません。このように、許容されるヒューリスティックによって最適性を確保できます。 ${\displaystyle f(n)}$ ${\displaystyle 10+0=10}$ ${\displaystyle f(n)}$ ${\displaystyle 10+100+0=110}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$ ${\displaystyle 100,101,102,102}$

ただし、許容されるヒューリスティックは最終的な最適性を保証できますが、必ずしも効率的ではないことに注意してください。

参照

• 一貫したヒューリスティック
• ヒューリスティック関数
• 検索アルゴリズム

参考文献

1. ラッセル SJ; ノーヴィグ P. (2002). 『人工知能：現代的アプローチ』 プレンティス・ホール. ISBN 0-13-790395-2。
2. Korf, Richard E. (2000)、「許容ヒューリスティック関数の設計と分析における最近の進歩」(PDF)、Choueiry, Berthe Y.; Walsh, Toby (編)、『抽象化、再定式化、近似：第4回国際シンポジウム、SARA 2000 ホースシューベイ、米国、2000年7月26日～29日議事録』、第1864巻、Springer、pp.  45～ 55、CiteSeerX 10.1.1.124.817、doi :10.1007/3-540-44914-0_3、ISBN  978-3-540-67839-7、 2010年4月26日閲覧
3. Holte, Robert (2005). 「ヒューリスティック探索に関するよくある誤解」.第3回組合せ探索シンポジウム (SoCS) の議事録. 2022年8月1日時点のオリジナルよりアーカイブ。 2021年7月10日閲覧。
4. 「なぜ許容ヒューリスティックスは最適性を保証するのか？」アルゴリズム。Stack Overflow 。2018年12月11日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Admissible_heuristic&oldid=1310940842"