А * алгоритм не работает должным образом
Мне нужна помощь с моей реализацией алгоритма 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* теперь работает отлично благодаря вам, ребята! :- )
Это был мой первый пост, и этот форум действительно удивительно!
2 ответа:
Вы меняете приоритет элемента в
PriorityQueue
после его вставки. Это не поддерживается, так как приоритетная очередь не знает об изменении объекта. То, что вы можете сделать, это удалить и повторно добавить объект, когда он изменяется.Приоритет изменяется в строке:
y.f_score = y.g_score + y.h_score;
. Эта строка появляется после добавленияy
в приоритетную очередь. Обратите внимание, что простого перемещения строкиopenset.add(y);
В после расчета стоимости будет недостаточно, так какy
, возможно, были добавлены в предыдущем итерация.Из вашего кода также не ясно, является ли используемая вами эвристика допустимой. Если это не так, это также приведет к тому, что вы получите неоптимальные пути.
Наконец, замечание о производительности: методcontains
наArrayList
иPriorityQueue
требует линейного времени для выполнения, что сделает время выполнения вашей имплемемтации неоптимальным. Это можно улучшить, добавив логические свойства к узлам, чтобы указать, находятся ли они в закрытых/открытых наборах, или используя структуру данных набора.
Приоритетная очередь не обновляет позицию элемента при изменении его приоритета. Поэтому свойство кучи не удерживается. Изменение приоритета влияет на добавление / удаление других элементов, но не восстанавливает свойство кучи.
Поэтому вы не получаете лучший элемент из open - > вы не находите кратчайший путь.
Вы можете: 1) написать свою собственную кучу и поддерживать индекс в ней 2) Добавьте другой объект в PQ и отметьте старый как недопустимый (вы должны вместо узла поставить некоторый объект с флаг валидности и узел ссылки в очередь).
2) имеют худшую производительность, и я не советую этого делать, но некоторые навигационные программы используют этот подход (или, по крайней мере, несколько лет назад он использовался).
Edit: рекомендуется вставлять неизменяемые (или по крайней мере с неизменяемыми частями, что означает приоритет) объекты в PriorityQueue