ヒューリスティック関数の許容性を証明する方法

Question

私は、目標までの実際の距離を決して過大評価するヒューリスティック関数を許容可能といいます。ヒューリスティックな関数が実際にはありますが、正式な証明を与える方法はわかりません。ヒューリスティックな関数が許容できることを私はどのように証明できますか？例：Manhattan Distanceヒューリスティック。

Answer 1

目標からの実際の距離を正式に定義することができれば、許容可能なヒューリスティックを作成するために制約を単純に排除することができます。

例： ポイント（x1、y1）からポイント（x2、y2）までのマンハッタン距離は| x1-x2 | + | y1-y2 |に等しい。 ヒューリスティックを思いつくために用語を削除するだけで済みます。たとえば、h = | x1-x2 |となります。 これが許容可能なヒューリスティックであることを証明するには、| x1-x2 | | x1-x2 | + | y1-y2 |

... for all x1、x2、y1、y2。

許容可能な別のヒューリスティックは直線距離であり、これは常にマンハッタン距離よりも小さいことを証明できます。

一般に、制約を緩和することは、許容できるヒューリスティックにつながります。

距離を使って作業している場合、直線距離は常に過大評価されることはないため、許容可能なヒューリスティックです。

これがあなたの質問に答えるかどうか教えてください:)