* Алгоритм не работает должным образом - PullRequest
Новая
       24

* Алгоритм не работает должным образом

8 голосов
/ 09 августа 2011

Мне нужна помощь в реализации моего алгоритма 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 ]

7 голосов
/ 09 августа 2011

Вы меняете приоритет элемента в PriorityQueue после его вставки. Это не поддерживается, поскольку приоритетная очередь не знает, что объект изменился. Что вы можете сделать, это удалить и повторно добавить объект при его изменении.

Приоритет изменяется в строке: y.f_score = y.g_score + y.h_score;. Эта строка происходит после добавления y в приоритетную очередь. Обратите внимание, что простого перемещения строки openset.add(y); после расчета стоимости будет недостаточно, поскольку y, возможно, было добавлено на предыдущей итерации.

Из вашего кода также не ясно, является ли используемая вами эвристика допустимой . Если это не так, это также приведет к тому, что вы получите неоптимальные пути.

Наконец, примечание по производительности: метод contains для ArrayList и PriorityQueue требует линейного времени для запуска, что делает время выполнения вашей реализации неоптимальным. Вы можете улучшить это, добавив логические свойства к узлам, чтобы указать, находятся ли они в закрытых / открытых наборах, или используя структуру данных набора.

3 голосов
/ 09 августа 2011

Приоритетная очередь не обновляет позицию элемента при изменении его приоритета.Поэтому свойство кучи не имеет места.Измененный приоритет влияет на добавление / удаление других элементов, но не восстанавливает свойство кучи.

, поэтому вы не получаете лучший элемент из открытого -> вы не найдете кратчайшего пути.

Выможет: 1) записать свою собственную кучу и поддерживать в ней индекс 2) добавить еще один объект в PQ и пометить старый как недопустимый (вместо узла необходимо поместить какой-либо объект с флагом достоверности и ссылкой на узел в очередь).

2) имеют худшую производительность, и я советую против этого, но некоторые навигационные программы используют этот подход (или, по крайней мере, несколько лет назад, когда он использовался).

edit: Лучшая практика - вставлять неизменяемый (или, по крайней мере, снеизменяемые части, что означает приоритет) объектов в PriorityQueue

...