我的 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* 算法现在可以完美运行了! :-)
这是我的第一篇文章,这个论坛真的很棒!
最佳答案
在 PriorityQueue
中插入一个元素后,您正在更改该元素的优先级。这不受支持,因为优先级队列不知道对象已更改。您可以做的是在对象发生变化时删除并重新添加该对象。
优先级在行中更改:y.f_score = y.g_score + y.h_score;
。此行发生在将 y
添加到优先级队列之后。请注意,仅将 openset.add(y);
行移动到计算成本之后是不够的,因为 y
可能已在先前的迭代中添加。
从您的代码中也不清楚您使用的启发式是否是 admissible .如果不是,它也会导致您获得次优路径。
最后,一个性能说明:ArrayList
和PriorityQueue
上的contains
方法需要线性时间运行,这将使运行时间你的实现不是最优的。您可以通过向节点添加 boolean 属性以指示它们是否在封闭/开放集中,或通过使用集合数据结构来改进这一点。
关于java - A* 算法无法正常工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6997604/