algorithm - なぜこのヒューリスティックが許容されるのですか？

Question

Tic Tac Toeの場合、私の講師は、Tic Tac Toeでの次の動き（Oプレーヤーの観点から）の許容可能なヒューリスティック（距離を過大評価しないことを意味します）を提示しました。

Oの可能な行数-Xの可能な行数

私が疑問に思っていたのは、なぜこのヒューリスティックが許容されるのかということです。

Answer 1

そうではありません。

O..
XOX
OX.

次に、ゴールまでの距離=（3-1）= 2

ゴールまでの実際の距離、1（勝つためO）

2> 1、したがってそれは過大評価されました。

それとも私は何かが足りないのですか？

Answer 2

ウィキペディアから：

ヒューリスティック関数は、目標を達成するためのコストを過大評価しない場合に許容されると言われます

つまり、ヒューリスティックを使用している場合、これは、目標に対する実際のコストが推定コスト以上であることが保証されている場合にのみ許容されるということです。この良い例は、A*パスファインディングアルゴリズムのヒューリスティックです。そのアルゴリズムでは、通常、ターゲットへの直接の道路があるように、ターゲットまでの距離を推定するヒューリスティックを使用します。距離を過大評価するヒューリスティックを使用すると、可能な限り最短のパスが見つからない可能性があります。