A *アルゴリズムが正しく動作しない

Question

私のA *アルゴリズムの実装にはいくつかの助けが必要です。 アルゴリズムを実行すると目的が見つかりますが、パスは最短ではありません.-P

ここに私のコードはありますか？ 私はそれが私の問題である再構築パスかもしれないと思うが、わからない。すべての偉大な答えをみんなに

public class Pathfinder { 

public List<Node> aStar(Node start, Node goal, WeightedGraph graph) { 
    Node x, y; 
    int tentative_g_score; 
    boolean tentative_is_better; 

    FScoreComparator comparator = new FScoreComparator(); 
    List<Node> closedset = new ArrayList<Node>(); 
    Queue<Node> openset = new PriorityQueue<Node>(10, comparator); 
    openset.add(start); 

    start.g_score = 0; 
    start.h_score = heuristic_cost_estimate(start, goal); 
    start.f_score = start.h_score; 

    while (!openset.isEmpty()) { 
     x = openset.peek(); 

     if (x == goal) { 
      return reconstruct_path(goal); 
     } 

     x = openset.remove(); 
     closedset.add(x); 

     for (Edge e : graph.adj(x)) { 

      if (e.v == x) { 
       y = e.w; 
      } else { 
       y = e.v; 
      } 

      if (closedset.contains(y) || y.illegal) { 
       continue; 
      } 

      tentative_g_score = x.g_score + e.weight; 

      if (!openset.contains(y)) { 
       openset.add(y); 
       tentative_is_better = true; 
      } else if (tentative_g_score < y.g_score) { 
       tentative_is_better = true; 
      } else { 
       tentative_is_better = false; 
      } 

      if (tentative_is_better) { 
       y.g_score = tentative_g_score; 
       y.h_score = heuristic_cost_estimate(y, goal); 
       y.f_score = y.g_score + y.h_score; 
       y.parent = x; 
      } 

     } 

    } 

    return null; 

} 

private int heuristic_cost_estimate(Node start, Node goal) { 
    return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y); 
} 

private List<Node> reconstruct_path(Node current_node) { 
    List<Node> result = new ArrayList<Node>(); 

    while (current_node != null) { 
     result.add(current_node); 
     current_node = current_node.parent; 
    } 

    return result; 
} 

private class FScoreComparator implements Comparator<Node> { 

    public int compare(Node n1, Node n2) { 
     if (n1.f_score < n2.f_score) { 
      return 1; 
     } else if (n1.f_score > n2.f_score) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

}

ありがとう！ 私のA *アルゴリズムは皆さんのおかげで完璧に動作します！ :-)

これは私の最初の投稿であり、このフォーラムは本当に素晴らしいです！

Answer 1

にオブジェクト。優先度キューはオブジェクトが変更されたことを認識しないため、これはサポートされていません。あなたができることは、オブジェクトが変更されたときにオブジェクトを削除して再追加することです。

優先度は、y.f_score = y.g_score + y.h_score;行で変更されています。この行は、優先度キューにyを追加した後に発生します。以前の繰り返しでyが追加されている可能性があるため、コストを計算した後に行openset.add(y);を移動するだけでは不十分です。

また、使用したヒューリスティックがadmissibleであるかどうかは、コードから明らかではありません。そうでない場合は、最適ではないパスを取得します。

最後に、パフォーマンスノート：ArrayListとPriorityQueueのメソッドの実行には時間がかかりますが、実行時間が最適ではありません。これを改善するには、ノードにブール値プロパティを追加して、ノードがクローズ/オープンセットにあるかどうか、またはセットデータ構造を使用するかどうかを指定します。

Answer 2

優先度キューは、優先度を変更したときにアイテムの位置を更新しません。 したがって、ヒーププロパティは保持されません。 変更された優先度は他の項目の追加/削除に影響しますが、ヒーププロパティは修復されません。

したがって、あなたは最善のアイテムを開くことができません - >あなたは最短のパスを見つけることができません。

次のことが可能です。 1）独自のヒープを書いて、それ 2へのインデックスを維持する）（あなたの代わりにノードの有効フラグでいくつかのオブジェクトを入れて、にノードを参照する必要がありますPQに別のオブジェクトを追加し、無効として古いものをマークキュー）。

2）パフォーマンスが悪くて助かりましたが、一部のナビゲーションソフトウェアではこのアプローチを使用しています（少なくとも数年前から使用していました）。

編集：ベストプラクティスは不変（又は少なくとも優先順位を意味imutable部で）を挿入し、あるあなたがそれを挿入した後PriorityQueueの要素の優先度を変更する優先度つきキュー