距離メトリックヒューリスティックinformedness

Question

垂直移動は許可されていますか？

すべてのケースでそれらをテストしている間は、第2のヒューリスティックは常に対角線になり、検出されるノードの数はマンハッタンよりもかなり小さいことがあります。しかし、これは必ずしもそうではなく、これが私を混乱させるものです。

Answer 1

与えられた現在の点a = (x1, y1)と目標b = (x2, y2)。 dist1(a, b)はマンハッタン距離を示し、dist2(a, b)は提案する他のヒューリスティックを示します。我々は持っている：私は負の数の平方根を取っているので、代わりにちょうど違いにより、絶対差の平方根を取るためにあなたの新しい提案ヒューリスティックビットを変更

dist1(a, b) = |x1 - x2| + |y1 - y2|

dist2(a, b) = max(sqrt(|x1 - x2|), sqrt(|y1 - y2|))

注意を問題につながるだろう。とにかく、それは、どのようなaとb、dist1(a, b) >= dist2(a, b)のためにそれを見ることは容易でなければなりません。

両方のヒューリスティックは、垂直方向と水平方向のみの移動が許可されているグリッドの場合には許容されるため、通常は2つの最大ヒューリスティック（マンハッタン距離）がより効果的です。真実。

OPでは、実際には、「発見されたノードの数」を測定していると言いましたが、これは2番目のヒューリスティックの方が小さい（より良い）ことがあります。これで、A *アルゴリズムを実行していることを意味していると仮定し、フロンティア/オープンリスト/プライオリティキュー/あなたが望む任意の言葉でポップされたノードの数を測定していると仮定します使用する。

私の推測では、複数のノードがフロンティアで等しいスコア（多くの場合fと呼ばれます）を持つ場合には、タイブレークが悪いことがあります。あなたが提案した第2のヒューリスティックは、現在のノードとゴールの間の対角線に沿ってノードを好む傾向がありますが、マンハッタンの距離にはそのような傾向はありません。フロンティアの複数のノードが等価（f）の得点を持つ場合の良いタイブレーカーは、これまでの高い実コスト（多くの場合、gと呼ばれる）とヒューリスティックコスト（多くの場合、h ）。実際には、fのスコアが等しい場合はgまたはhのスコアを明示的に比較するか、すべてのヒアリスティックスコアに1（たとえば、1.0000001）より少し大きい数字を掛けるだけで実装できます。詳細については、http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties