Рубрики
Без рубрики

Графики в Java – A* Алгоритм

В этой статье мы рассмотрим теорию и реализацию A* на Java с подробными объяснениями и практическими примерами.

Автор оригинала: Darinka Zobenica.

Вступление

A * – это алгоритм графа эвристического поиска путей. Это означает, что при заданном взвешенном графике он выводит кратчайший путь между двумя заданными узлами.

Алгоритм гарантированно завершается для конечных графов с неотрицательными весами ребер. Кроме того, если вам удастся обеспечить определенные свойства при разработке вашей эвристики , она также всегда будет возвращать почти оптимальное решение довольно эффективным способом.

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

В этой статье мы рассмотрим:

  • Некоторые характеристики, которые мы стремимся иметь в наших алгоритмах эвристического поиска в целом.
  • Покажите логическую прогрессию от жадного поиска к*.
  • Выполните вышеупомянутые условия, которые позволяют A* оптимально и эффективно решить нашу проблему.

Характеристики поиска по графу

Мы начнем с описания некоторых вещей, которые мы, как правило, хотим выполнить с помощью нашего алгоритма.

Ниже приведены все очень важные показатели, которые отделяют A* от других подобных алгоритмов, и поэтому их следует тщательно понимать, если мы хотим осмысленно применить их на практике:

  1. Полнота – это свойство алгоритма, которое гарантирует, что алгоритм завершится решением, если решение существует.
  2. Оптимальность – это свойство, которое гарантирует, что наше алгоритмическое решение будет наилучшим доступным решением, основанным на критериях, которые мы поставили в качестве нашей цели.
  3. Сложность времени и памяти – измеряет эффективность использования ресурсов наших алгоритмов и, следовательно, их практическую применимость.

Недостатки других алгоритмов

Столкнувшись с проблемой нахождения кратчайшего пути в графике за разумное время, многие из нас испытывали бы искушение пожертвовать оптимальностью и пойти на жадное решение – всегда выбирать край с наименьшим весом – идти вдоль потока с наименьшим сопротивлением.

Наблюдательный читатель может заметить, что, делая это, мы также пожертвовали полнотой – жадный поиск иногда может застрять в бесконечных циклах. Мы можем сделать что – то получше.

Если вы подумали об алгоритме Дейкстры , очки для вас! Это отличный алгоритм для поиска кратчайшего пути, а также довольно эффективный. Он выполняет эту работу даже при вычислениях огромного масштаба, таких как маршрутизация по всему Интернету. Это также полный и оптимальный .

Значит, работа сделана, верно?

Не так быстро.

Хотя Дейкстра может быть наилучшим возможным решением для некоторых реальных проблем, она может потратить много времени на проверку альтернативных путей, особенно в плотном графике со многими узлами. Фактически, Дейкстра оценивает каждый узел в графике. Даже те, кто стоит за этим, уходят от цели. Если бы цель находилась прямо перед текущим узлом, она все равно оценивала бы узлы на противоположной стороне графика, даже если бы она могла просто оценить промежуточные узлы между собой и целью.

Это все равно, что смотреть на всю карту города на каждом шаге, который вы делаете по направлению к кофейне, вместо того, чтобы направлять свой поиск в общем направлении магазина.

Если бы мы могли каким-то образом направить его в общем направлении, к целевому узлу, мы могли бы пропустить много ненужной работы.

Допустим, мы можем примерно угадать расстояние между двумя узлами. Возможно, мы пытаемся рассчитать путь движения по дороге между двумя точками на Земле. Мы могли бы сказать, что расстояние полета по прямой-это приблизительная оценка того, насколько они далеки друг от друга. Что, если бы мы использовали эту оценку для выбора следующего узла вместо использования веса ребра?

Этот подход называется лучший поиск и часто повышает нашу эффективность, но мы часто получаем неоптимальное решение.

Это подводит нас к тому, как A* удалось решить все эти проблемы.

Примечание: Некоторые ссылаются на A* как информированный Дейкстра .

Алгоритм A* в Java

Стартовые условия:

  • У нас есть начальный узел (называемый start ) и целевой узел (называемый target ).
  • У нас есть взвешенный ориентированный граф из n узлов.

Цель:

  • Найдите кратчайший путь от начала до конца

Функция затрат – f(n)

Мы хотим определить, в какой узел переходить на каждом шаге. Для этого мы разработаем математическую функцию f(n) , которая будет измерять, насколько хорош узел-кандидат для включения в наш кратчайший путь.

Это функция затрат , и мы захотим свести ее к минимуму, чтобы получить оптимальный результат.

Функция затрат представляет собой сумму функции перемещения и эвристической функции .

Функция перемещения – g(n)

Поскольку мы находимся на узле n , мы знаем, сколько нам потребовалось, чтобы добраться туда с начального узла. Мы назовем это функцией перемещения – g(n) .

Если мы скажем, что f(n)=g(n) мы создадим алгоритм Дейкстры. На каждом шаге мы выбирали бы узел с наименьшими затратами для доступа из start – узел с наименьшим значением для g(n) . Это означает, что в нашей функции отсутствует, так сказать, “направляющий компонент”.

Эвристическая функция – h(n)

Мы назовем этот направляющий компонент эвристическим и обозначим его h(n) . Мы будем использовать этот компонент, чтобы оценить, насколько близок рассматриваемый узел к цели .

Эта оценка является сердцем и душой A*, и она сделает или сломает любую конкретную ее реализацию, но теоретически вы можете использовать любую функцию, какую захотите. Если бы мы знали точное расстояние в терминах узлов, у нас уже было бы оптимальное решение.

Хотя, если мы знаем положение целевого узла, мы можем, например, рассчитать евклидово расстояние между целевым узлом и нашим текущим узлом. Чем он короче, тем ближе мы к целевому узлу – примерно .

Примечание: Вы просто получите лучшие результаты, если тщательно разработаете свою эвристику.

Расчет Ходов A*

Таким образом, конечная формула, которую мы получаем, f(n)=g(n)+h(n) . Мы начинаем с узла start , добавляем его в список открытых узлов. Мы оцениваем всех соседей открытых узлов и добавляем их в список открытых узлов. Мы выбираем тот, у которого наименьшее значение для f(n) , и если это не цель , мы повторяем процесс.

Чем меньше шагов мы делаем от начальной точки в сочетании с тем, насколько близко мы подходим к цели, тем ниже значение f(n) , если мы идем по кратчайшему пути к цели. Уход от цели и выполнение большего количества шагов, чем необходимо для ее достижения, увеличивает функцию f(n) .

Если вас немного смущает разница между g(n) и h(n) , посмотрите на это так:

  • g – это то, что мы можем (и делаем) рассчитать на любом заданном шаге, и это расстояние между началом и n .
  • h – это то, чего мы не знаем, и нам нужно оценить-расстояние от n до целевого узла.
  • f является суммой двух

A* Псевдокод

Мы поддерживаем два списка узлов: открытый список и закрытый список .

Открытый список содержит узлы, с которыми мы столкнулись, но еще не проанализировали. Изначально он содержит только начальный узел.

Закрытый список содержит узлы, все соседи которых были добавлены в открытый список. Закрытые узлы рассчитывают свой кратчайший путь, а их соседние узлы “планируются” для анализа путем добавления в открытый список.

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

Мы просматриваем открытые заметки, открываем их соседей, вычисляем их f и g , а затем снова закрываем их.

Обычно вам нужно будет вычислить h один раз, когда вы впервые столкнетесь с узлом. Вам не нужно пересчитывать его несколько раз, потому что он исправлен. Мы опустили это в этом коде, предполагая, что эвристика рассчитана заранее, но вы можете добавить ее в зависимости от вашего приложения:

make an empty list C of closed nodes
make a list O of open nodes and their respective f values containing the start node
while O isn't empty:
    pick a node n from O with the best value for f
    if n is target:
        return solution
    for every m which is a neighbor of n:
        if (m is not in C) and (m is not in O):
            add m to O, set n as m's parent
            calculate g(m) and f(m) and save them
        else:
            if f(m) from last iteration is better than g(m) from this iteration:
                set n as m's parent
                update g(m) and f(m)
                if m is in C:
                    move m to O
    move n from O to C

return that there's no solution

A* Реализация на Java

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Мы реализуем алгоритм для графика, показанного в начале статьи. Наша эвристика будет рассматривать каждый “слой” как шаг к целевому узлу. Номера внутри узлов-это их ID s, которые мы будем использовать для вывода результирующего пути:

Примечание: Это не очень хорошая эвристика на практике.

Каждая задача будет иметь свою собственную эвристику подгонки, потому что график может быть нарисован многими способами – узлы могут казаться ближе или дальше от цели, чем они есть на самом деле, если учитывать вес ребер

Мы использовали этот подход в иллюстративных целях, и в следующем разделе мы углубимся в то, как сделать полезную эвристику на практике.

Давайте создадим класс Node для представления узла в нашем графике:

public class Node implements Comparable {
      // Id for readability of result purposes
      private static int idCounter = 0;
      public int id;

      // Parent in the path
      public Node parent = null;

      public List neighbors;

      // Evaluation functions
      public double f = Double.MAX_VALUE;
      public double g = Double.MAX_VALUE;
      // Hardcoded heuristic
      public double h; 

      Node(double h){
            this.h = h;
            this.id = idCounter++;
            this.neighbors = new ArrayList<>();
      }

      @Override
      public int compareTo(Node n) {
            return Double.compare(this.f, n.f);
      }

      public static class Edge {
            Edge(int weight, Node node){
                  this.weight = weight;
                  this.node = node;
            }

            public int weight;
            public Node node;
      }

      public void addBranch(int weight, Node node){
            Edge newEdge = new Edge(weight, node);
            neighbors.add(newEdge);
      }

      public double calculateHeuristic(Node target){
            return this.h;
      }
}

А вот и сам алгоритм:

public static Node aStar(Node start, Node target){
    PriorityQueue closedList = new PriorityQueue<>();
    PriorityQueue openList = new PriorityQueue<>();

    start.f = start.g + start.calculateHeuristic(target);
    openList.add(start);

    while(!openList.isEmpty()){
        Node n = openList.peek();
        if(n == target){
            return n;
        }

        for(Node.Edge edge : n.neighbors){
            Node m = edge.node;
            double totalWeight = n.g + edge.weight;

            if(!openList.contains(m) && !closedList.contains(m)){
                m.parent = n;
                m.g = totalWeight;
                m.f = m.g + m.calculateHeuristic(target);
                openList.add(m);
            } else {
                if(totalWeight < m.g){
                    m.parent = n;
                    m.g = totalWeight;
                    m.f = m.g + m.calculateHeuristic(target);

                    if(closedList.contains(m)){
                        closedList.remove(m);
                        openList.add(m);
                    }
                }
            }
        }

        openList.remove(n);
        closedList.add(n);
    }
    return null;
}

public static void printPath(Node target){
    Node n = target;

    if(n==null)
        return;

    List ids = new ArrayList<>();

    while(n.parent != null){
        ids.add(n.id);
        n = n.parent;
    }
    ids.add(n.id);
    Collections.reverse(ids);

    for(int id : ids){
        System.out.print(id + " ");
    }
    System.out.println("");
}

А теперь давайте построим график и вызовем этот метод:

public static void main(String[] args) {
    Node head = new Node(3);
    head.g = 0;

    Node n1 = new Node(2);
    Node n2 = new Node(2);
    Node n3 = new Node(2);

    head.addBranch(1, n1);
    head.addBranch(5, n2);
    head.addBranch(2, n3);
    n3.addBranch(1, n2);

    Node n4 = new Node(1);
    Node n5 = new Node(1);
    Node target = new Node(0);

    n1.addBranch(7, n4);
    n2.addBranch(4, n5);
    n3.addBranch(6, n4);

    n4.addBranch(3, target);
    n5.addBranch(1, n4);
    n5.addBranch(3, target);

    Node res = aStar(head, target);
    printPath(res);
}

Когда мы запустим это, мы распечатаем результат:

0 3 2 5 6

Создание хорошей эвристической функции

Приемлемость и последовательность

Производительность A* зависит от использования хорошей эвристики. Сам алгоритм может обладать некоторыми очень полезными свойствами, если мы убедимся, что эвристика следует определенным правилам. Давайте взглянем.

Функция h(n) является допустимой , если она никогда не переоценивает реальное расстояние между текущим узлом и целью. Это означает, что следующее неравенство справедливо для каждого узла n :

$$ h(n)\leq h\ ⃰(n) $$

Где h ⃰ – идеальная эвристика, точно измеряющая кратчайший путь.

Если h допустимо, A* всегда будет возвращать оптимальный путь.

Если h недопустимо, но оно не завышает реальное расстояние более чем на некоторое значение d , то длина пути, найденного A*, не будет отличаться от оптимального пути более чем на d .

Функция h(n) является согласованной , если она равна 0 для целевого узла и если для каждых двух соседних узлов верно, что:

$$ c(n,m)+h(m)\geq h(n) $$

Где c(n,m) – вес ребра (n,m) .

Теорема: Если эвристическая функция непротиворечива, то она также допустима.

Доказательство этой теоремы выполняется с помощью полной индукции.

Сложность

За исключением особых случаев, сложность A* может быть аппроксимирована на основе числа соседей каждого узла и длины кратчайшего пути. Предположим, что у каждого узла есть не более b соседей, а кратчайший путь имеет расстояние d . Сложность A* тогда:

$$ O(b^d) $$

Экспоненциальная сложность была бы не лучше грубой силы, так что это может показаться плохим. Дело в том, что мы можем снизить эту сложность до полиномиальной, если наша эвристика удовлетворяет следующему уравнению:

$$ |h(x)-h\ ⃰(x)| \leq O(\log h\ ⃰(x)) $$

A* также оптимально эффективен , что означает, что было доказано, что ни один полный алгоритм не является более эффективным, чем A* для решения одной и той же проблемы.

Пример – 2D Местность С Препятствиями

Допустим, у нас есть 2D-сетка с препятствиями. Каждый квадрат соответствует одному узлу, и мы можем двигаться, как король в шахматах, – один квадрат по горизонтали, вертикали или диагонали. Мы хотим найти кратчайший путь от начала до цели.

Представление

В этом случае мы можем представить наш график в виде матрицы узлов, а не использовать списки смежности. Каждый узел может иметь индикатор того, является ли он проходимым или препятствием. Мы можем использовать матричные индексы для определения соседних узлов, а также использовать их как координаты при расчете наших эвристических расстояний.

Эвристический

Вашей первой мыслью может быть использование Евклидова расстояния . Однако в больших проблемах этого следует избегать, так как вычисление квадратного корня часто может привести к неэффективности. Это хорошая метрика, если ничто другое не соответствует проблеме, но если вам сойдет с рук использование упрощенного расстояния, вы должны попытаться.

Второй идеей может быть Расстояние до Манхэттена (также называемое расстоянием до такси или городского квартала). Манхэттенское расстояние сумма горизонтальных и вертикальных различий:

$$ D_{Манхэттен}(p,q)=|q_x-p_x|+|q_y-p_y| $$

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

Хорошим выбором, в данном случае, является так называемое Расстояние Чебышева :

$$ (|q_x-p_x|,|q_y-p_y|) $$

Этот показатель допустим и, таким образом, гарантирует оптимальное решение. Он также быстр в вычислениях, поэтому не требует больших затрат ресурсов на каждой итерации.

Вывод

Мы рассмотрели алгоритм поиска* и его свойства. Мы узнали, как это работает и почему это очень хорошо на практике, при условии, что мы можем обеспечить определенные свойства эвристики, направляющей его.

Применение этого к реальным проблемам требует практики и опыта, но эта статья должна была дать читателю хорошую основу для их начала.

Читайте ещё по теме: