Вступление

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

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

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

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

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

Оглавление:

• Характеристики поиска по графу
• Недостатки других алгоритмов
• Алгоритм A * в Java
• Функция затрат - f (n)
• Функция перемещения - g (n)
• Эвристическая функция - h (n)
• Расчет ходов A *
• Псевдокод
• Выполнение
• Создание хорошей эвристической функции
• Практический пример местности

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

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

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

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

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

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

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

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

Итак, работа сделана?

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

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

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

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

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

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

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

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

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

Условия запуска:

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

Цель:

• Найдите кратчайший путь от start до finish

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{.ezlazyload}

A * Псевдокод

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

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

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

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

Мы проходим открытые узлы, открываем их соседей, вычисляем их 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 
 , 
 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 
 , 
 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 
 , 
 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 
 , 
 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

Реализуем алгоритм для графа, показанного в начале статьи. Наша эвристика будет рассматривать каждый «слой» как шаг к target узлу. Числа внутри узлов - это их ID , которые мы будем использовать для распечатки результирующего пути:

{.ezlazyload}

Примечание. На практике это не лучшая эвристика.

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

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

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

 public class Node implements Comparable<Node> { 
 // Id for readability of result purposes 
 private static int idCounter = 0; 
 public int id; 
 
 // Parent in the path 
 public Node parent = null; 
 
 public List<Edge> 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, nf); 
 } 
 
 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<Node> closedList = new PriorityQueue<>(); 
 PriorityQueue<Node> 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 = ng + edge.weight; 
 
 if(!openList.contains(m) && !closedList.contains(m)){ 
 m.parent = n; 
 mg = totalWeight; 
 mf = mg + m.calculateHeuristic(target); 
 openList.add(m); 
 } else { 
 if(totalWeight < mg){ 
 m.parent = n; 
 mg = totalWeight; 
 mf = mg + 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<Integer> 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 

{.ezlazyload}

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

Допустимость и последовательность

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

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

$$
ч (п) \ leq ч \ ⃠° (п)
$

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

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

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

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

$$
с (п, м) + ч (м) \ geq ч (п)
$

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

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

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

Сложность

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

$$
О (б ^ г)
$

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

$$
| h (x) -h \ ⃠° (x) | \ leq O (\ log h \ ⃠° (x))
$

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

Пример - 2D рельеф с препятствиями

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

{.ezlazyload}

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

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

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

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

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

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

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

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

$$
D_ {Чебышев} (p, q) = max (| q_x-p_x |, | q_y-p_y |)
$

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

Заключение

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

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