A *経路探索

Question

私が現在使用してC++で*を実装しようとしています：http://www.policyalmanac.org/games/aStarTutorial.htm

をしかし、私は斜めの動きを含めないことを決めた最初のバージョンのために。それは現在のポイントの隣人をチェックするループポイントcにおける要約セクションで

：

for each neighbour of the current square (above, below, left, right) 
    if neighbour on closed list or not walkable { 
     continue 
    } 

    if neighbour not in open list { 
     add to open list 
     set parent of neighbour to current square 
     update F, G, H values 
    } else if neighbour is on open list { 
     check to see if this path to that square is better, 
     using G cost as the measure. A lower G cost means that this is a better path. 
     If so, change the parent of the square to the current square, 
     and recalculate the G and F scores of the square. 
    } 

私は唯一の4方向の移動を許容していた場合、私はまだどうかを確認するためにグラムコストをチェックする必要がありますその広場への道は良いですか？例えば、開始点から始まり、開始点の4つの隣接点は全て同じgを有する。

Answer 1

より低いGコストをチェックする点は、よりよいものが見つかると、その正方形の新しいパスを設定することです。最初にAから正方形Cへのパスを見つけることができます。しかし、後で検索するとき、Cの隣人と異なるパスを見つけるでしょう。Cが閉じたリストにない場合、Cへの新しいパスのGコストは、最初のものよりも低くなるので、より良いG（したがってF）値でCを更新したいとします。

Answer 2

状況を分析しましょう。基本的なポイントは、グラフのすべてのエッジが同じ重みを持つことです。

現在、頂点がcで、隣人nを分析しているとします。次に、近隣のnの更新された距離は、distance(c) + wとなります。ここで、wは均一なエッジの長さです。今問題はnが別のパスを経由する距離よりも大きい距離を持つことができるかどうかです。

nの親のpが長いパスにつながるとします。次に、nの距離はdistance(p) + wです。その式がcから更新されたコストよりも大きくなるようにするためには、次のようなニーズに保持する：

distance(p) + w > distance(c) + w 
distance(p) > distance(c) 

のでpは遠く離れてcより開始されてからでなければならないであろう。 Dijkstraのアルゴリズムを使用した場合、これはpがcの後に修正されることを意味するため、これは不可能です。しかし、あなたはA *を使って、ヒューリスティックで順序を決定します。したがって、次の2つの条件を満たす必要があります。

distance(p) > distance(c) 
distance(p) + heuristic(p) <= distance(c) + heuristic(c) 
<=> heuristic(p) <= heuristic(c) - (distance(p) - distance(c)) 

これはあなたのヒューリスティックに帰着します。広く使用されているマンハッタン距離ヒューリスティックはこれを可能にします。したがって、このヒューリスティックを使用する場合、より低いコストをチェックする必要があります。あなたのヒューリスティックが上記の条件を許容しない場合（例えば、ダイクストラの場合のような一定のヒューリスティック）、あなたはしません。