私が理解している限り、ヒューリスティックの許容範囲は、特定の評価されたノードの「距離に対する実際のコスト」の範囲内にとどまっています。状態空間での A* ソリューション検索用にいくつかのヒューリスティックを設計する必要があり、負の値を返す場合があるヒューリスティックを使用して多くの肯定的な効率を得たため、特定のノードをより「密接に形成」して目標に近づけることができました。州はフロンティアでより高い地位を占めています。
しかし、これは容認できないのではないかと心配していますが、これを確認するのに十分な情報をオンラインで見つけることができません. テキサス大学のこの論文は、後の証明の1つで「...ヒューリスティック関数は非負であるため」と言及しているようです。誰でもこれを確認できますか？ヒューリスティック関数として負の値を返すと、g コストが負になるためだと思います (したがって、A* の「デフォルト」のダイクストラ風の動作に干渉します)。
結論: 負の値を生成するヒューリスティック関数自体は許容できないわけではありませんが、A* の保証を破る可能性があります。
興味深い質問です。基本的に、許容性の唯一の要件は、ヒューリスティックがゴールまでの距離を決して過大評価しないことです。これは重要です。誤った場所での過大評価は、人為的に最良のパスを別のパスより悪く見せ、探索を妨げる可能性があるからです。したがって、過大評価を提供できるヒューリスティックは、最適性の保証を失います。過小評価しても同じコストはかかりません。特定の方向に進むコストを過小評価すると、最終的にエッジの重みが加算されて、別の方向に進むコストよりも大きくなるため、その方向も調査します。唯一の問題は効率の低下です。
すべてのエッジに正のコストがある場合、負のヒューリスティック値は過小評価になる可能性があります。理論的には、過小評価はより正確な見積もりよりも悪くなるはずです。これは、パスの潜在的なコストに関する情報が厳密に少なくなり、より多くのノードが拡張される可能性が高いためです。とはいえ、不採用にはなりません。
ただし、負のヒューリスティック値が A* の保証された最適性を破ることが理論的に可能であることを示す例を次に示します。
このグラフでは、ノード A と B を通過する方が明らかに優れています。これには、ノード C と D を通過するコストである 6 ではなく、3 のコストがあります。ただし、C と D の負のヒューリスティック値D は、ノード A と B を探索する前に、A* がそれらを通って最後に到達するようにします。本質的に、ヒューリスティック関数は、手遅れになるまで、このパスが大幅に改善されると考え続けます。A* のほとんどの実装では、これは間違った答えを返しますが、f(n) の最大値が見つけたパスのコストよりも大きくなるまで他のノードを探索し続けることで、この問題を修正できます。このヒューリスティックについて、容認できないことや矛盾することは何もないことに注意してください。A* ヒューリスティックのルールとして、非負性がそれほど頻繁に言及されていないことに、私は本当に驚いています。
もちろん、これが示しているのは、結果を恐れずに負の値を返すヒューリスティックを自由に使用することはできないということだけです。特定の問題に対する特定のヒューリスティックが、否定的であるにもかかわらず、たまたまうまく機能する可能性は十分にあります。あなたの特定の問題では、このようなことが起こっている可能性は低いです (そして、それがあなたの問題でうまく機能することは本当に興味深いと思いますが、なぜそうなのかについてもっと考えたいと思っています)。