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*算法现在已经完美运行了！:-)

这是我第一次发帖，这个论坛真的很棒！

- Johan Berg

---

如果不了解您的问题域，回答这个问题可能非常困难，甚至是不可能的。您是否正在寻找穿过L1空间（例如网格）的路径？如果不是，您可能想改用欧几里得距离启发式算法。 - Fred Foo

Answer 1

您正在更改已插入的元素在PriorityQueue中的优先级。这是不支持的，因为优先队列不知道对象已更改。当对象更改时，您可以将其删除并重新添加。

优先级在此行更改：y.f_score = y.g_score + y.h_score;。此行在将y添加到优先级队列后发生。请注意，仅将openset.add(y);移动到计算成本之后是不够的，因为y可能已在前一次迭代中添加。

从您的代码中也不清楚您使用的启发式是否可接受。如果不是，则会导致您获得次优路径。

最后，性能提示：对于ArrayList和PriorityQueue上的contains方法需要线性时间才能运行，这将使您的实现运行时间非最优。您可以通过向节点添加布尔属性以指示它们是否在关闭/打开集中，或使用集数据结构来改进此问题。

- interjay

Answer 2

优先队列在改变其优先级时不会更新项目的位置。 因此，堆属性不成立。 改变优先级会影响其他项目的添加/删除，但它不能修复堆属性。

因此，您无法从打开中获取最佳项目 -> 您找不到最短路径。

您可以： 1）编写自己的堆并维护索引。 2）将另一个对象添加到PQ中，并将旧对象标记为无效（您必须将节点替换为带有有效性标志和引用节点的某些对象）。

2）会导致更差的性能，我建议不要使用，但某些导航软件使用这种方法（或至少几年前曾经使用）。

编辑：最佳实践是将不可变（或至少具有不可变部分即优先级）对象插入PriorityQueue。

- Alpedar

---

即使您自己编写了最小堆（minheap）或其他数据结构，我也很难想象如何以比移除旧项目并重新插入新项目更高效的方式来更改项目的优先级（如果有，请告诉我）。因此，个人而言，我会选择移除并添加具有新优先级的项目。 - Voo

请问您能帮我看一下代码吗？我真的不太明白在哪里以及如何使用新的优先级删除或添加项目。 - Johan Berg

前段时间，我曾尝试过这样做（但我不确定是否正确，并且它在性能上是否值得），通过根据优先级变化的方向进行筛选上/下。这比总是遍历整个堆的删除+添加更快。 - Alpedar