8

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*アルゴリズムは、皆さんのおかげで完全に機能するようになりました。:-)

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

4

2 に答える 2

7

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

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

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

最後に、パフォーマンスに関する注意事項：containsメソッドの実行ArrayListにPriorityQueueは線形時間がかかります。これにより、実装の実行時間が最適ではなくなります。これを改善するには、ノードにブールプロパティを追加して、ノードが閉じた/開いたセットにあるかどうかを示すか、セットデータ構造を使用します。

于 2011-08-09T14:29:37.220 に答える
3

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

したがって、開いた状態から最良のアイテムを取得することはできません->最短経路が見つかりません。

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

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

編集：ベストプラクティスは、不変（または少なくとも優先度を意味する不変部分を含む）オブジェクトをPriorityQueueに挿入することです。

于 2011-08-09T14:29:34.350 に答える