A * Алгоритм поиска
Мотивация
Чтобы приблизиться к кратчайшему пути в реальных ситуациях, например, на картах, в играх, где может быть много препятствий.
Мы можем рассматривать 2D-сетку с несколькими препятствиями, и мы начинаем с исходной ячейки (окрашенной красным цветом ниже), чтобы достичь целевой ячейки (окрашенной зеленым цветом ниже).
Что такое алгоритм поиска A *?
Алгоритм поиска A * - один из лучших и популярных методов, используемых при поиске путей и обходов графов.
Почему алгоритм поиска A *?
Неформально говоря, у алгоритмов A * Search, в отличие от других методов обхода, есть «мозги». Это означает, что это действительно умный алгоритм, который отделяет его от других обычных алгоритмов. Этот факт подробно разъясняется в следующих разделах.
И также стоит упомянуть, что многие игры и веб-карты используют этот алгоритм для очень эффективного поиска кратчайшего пути (приближение).
Объяснение
Рассмотрим квадратную сетку с множеством препятствий, и нам даны начальная и целевая ячейки. Мы хотим достичь целевой ячейки (если возможно) из начальной ячейки как можно быстрее. Здесь на помощь приходит алгоритм поиска A *.
Что делает алгоритм поиска A *, так это то, что на каждом шаге он выбирает узел в соответствии со значением - « f », которое является параметром, равным сумме двух других параметров - « g » и « h ». На каждом этапе он выбирает узел / ячейку, имеющую наименьшее значение « f », и обрабатывает этот узел / ячейку.
Мы определяем ' g ' и ' h ' как можно проще ниже.
g = стоимость перемещения для перехода от начальной точки к заданному квадрату сетки по пути, сгенерированному для этого.
h = оценочная стоимость перемещения для перехода от данного квадрата на сетке к конечному пункту назначения. Это часто называют эвристикой, которая представляет собой не что иное, как своего рода умное предположение. Мы действительно не знаем фактического расстояния, пока не найдем путь, потому что на пути могут быть самые разные вещи (стены, вода и т. Д.). Есть много способов вычислить это «h», которые обсуждаются в следующих разделах.
Алгоритм
Мы создаем два списка - Открытый список и Закрытый список (точно так же, как алгоритм Дейкстры)
// Алгоритм поиска A *
1. Инициализируйте открытый список.
2. Инициализировать закрытый список.
положить стартовый узел на открытый
список (вы можете оставить его f равным нулю)
3. пока открытый список не пуст
а) найти узел с наименьшим f на
открытый список, назовите его "q"
б) вытащить q из открытого списка
c) сгенерировать 8 преемников q и установить их
родители q
г) для каждого преемника
i) если целью является преемник, прекратить поиск
преемник. г = д. g + расстояние между
преемник и q
преемник. h = расстояние от цели до
преемник (это можно сделать, используя множество
пути, мы обсудим три эвристики -
Манхэттен, диагональ и евклидов
Эвристика)
преемник. f = преемник. g + преемник. час
ii) если узел с той же позицией, что и
преемник находится в ОТКРЫТОМ списке, который имеет
ниже f, чем преемник, пропустить этого преемника
iii) если узел с той же позицией, что и
преемник находится в ЗАКРЫТОМ списке, в котором
ниже f, чем преемник, пропустить этого преемника
в противном случае добавьте узел в открытый список
конец (для цикла)
д) нажмите q в закрытом списке
конец (пока цикл)Итак, предположим, что, как показано на рисунке ниже, если мы хотим достичь целевой ячейки из исходной ячейки, тогда алгоритм поиска A * будет следовать по пути, как показано ниже. Обратите внимание, что рисунок ниже сделан с учетом эвклидова расстояния в качестве эвристики.
Эвристика
Мы можем вычислить g, но как вычислить h?
Мы можем делать что угодно.
A) Либо рассчитайте точное значение h (что, безусловно, отнимает много времени).
ИЛИ
Б) Приблизить значение h с помощью эвристики (меньше затрат времени).
Мы обсудим оба метода.
А) Точная эвристика -
Мы можем найти точные значения h, но обычно это занимает очень много времени.
Ниже приведены некоторые методы расчета точного значения h.
1) Предварительно вычислите расстояние между каждой парой ячеек перед запуском алгоритма поиска A *.
2) Если нет заблокированных ячеек / препятствий, мы можем просто найти точное значение h без каких-либо предварительных вычислений, используя формулу расстояния / Евклидово расстояние
Б) Эвристика приближения -
Обычно есть три эвристики приближения для вычисления h -
1) Манхэттенское расстояние -
- Это не что иное, как сумма абсолютных значений разностей координат x и y цели и координат x и y текущей ячейки соответственно, т. Е.
h = abs (current_cell.x - goal.x) +
абс (current_cell.y - цель.y)- Когда использовать эту эвристику? - Когда нам разрешено двигаться только в четырех направлениях (вправо, влево, вверх, вниз)
Манхэттенская эвристика расстояния показана на рисунке ниже (предположим, что красная точка является исходной ячейкой, а зеленая точка - целевой ячейкой).
2) Диагональное расстояние
- Это не что иное, как максимум абсолютных значений разницы в координатах x и y цели и координатах x и y текущей ячейки соответственно, т. Е.
dx = abs (current_cell.x - goal.x) dy = abs (current_cell.y - цель.y) h = D * (dx + dy) + (D2 - 2 * D) * min (dx, dy) где D - длина каждого узла (обычно = 1), а D2 - диагностическое расстояние между каждым узлом (обычно = sqrt (2)).
- Когда использовать эту эвристику? - Когда нам разрешено двигаться только в восьми направлениях (аналогично ходу короля в шахматах)
Эвристика диагонального расстояния показана на рисунке ниже (предположим, что красная точка является исходной ячейкой, а зеленая точка - целевой ячейкой).
3) Евклидово расстояние
- Как видно из названия, это не что иное, как расстояние между текущей ячейкой и целевой ячейкой по формуле расстояния
h = sqrt ( (current_cell.x – goal.x)2 +
(current_cell.y – goal.y)2 )- Когда использовать эту эвристику? - Когда нам разрешено двигаться в любых направлениях.
Евклидова эвристика расстояния показана на рисунке ниже (предположим, что красная точка является исходной ячейкой, а зеленая точка - целевой ячейкой).
Связь (сходство и различия) с другими алгоритмами-
Дейкстра - это частный случай алгоритма поиска A *, где h = 0 для всех узлов.
Реализация
Мы можем использовать любую структуру данных для реализации открытого списка и закрытого списка, но для лучшей производительности мы используем заданную структуру данных C ++ STL (реализованную как красно-черное дерево) и логическую хеш-таблицу для закрытого списка.
Реализации аналогичны алгоритму Дийсктры. Если мы используем кучу Фибоначчи для реализации открытого списка вместо двоичной кучи / дерева самобалансировки, тогда производительность станет лучше (поскольку куча Фибоначчи занимает O (1) среднее время для вставки в открытый список и уменьшения ключа)
Также, чтобы сократить время, затрачиваемое на вычисление g, мы будем использовать динамическое программирование.
CPP
// A C++ Program to implement A* Search Algorithm#include <bits/stdc++.h>using namespace std;#define ROW 9#define COL 10// Creating a shortcut for int, int pair typetypedef pair<int, int> Pair;// Creating a shortcut for pair<int, pair<int, int>> typetypedef pair<double, pair<int, int> > pPair;// A structure to hold the necessary parametersstruct cell { // Row and Column index of its parent // Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1 int parent_i, parent_j; // f = g + h double f, g, h;};// A Utility Function to check whether given cell (row, col)// is a valid cell or not.bool isValid(int row, int col){ // Returns true if row number and column number // is in range return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL);}// A Utility Function to check whether the given cell is// blocked or notbool isUnBlocked(int grid[][COL], int row, int col){ // Returns true if the cell is not blocked else false if (grid[row][col] == 1) return (true); else return (false);}// A Utility Function to check whether destination cell has// been reached or notbool isDestination(int row, int col, Pair dest){ if (row == dest.first && col == dest.second) return (true); else return (false);}// A Utility Function to calculate the "h" heuristics.double calculateHValue(int row, int col, Pair dest){ // Return using the distance formula return ((double)sqrt( (row - dest.first) * (row - dest.first) + (col - dest.second) * (col - dest.second)));}// A Utility Function to trace the path from the source// to destinationvoid tracePath(cell cellDetails[][COL], Pair dest){ printf("
The Path is "); int row = dest.first; int col = dest.second; stack<Pair> Path; while (!(cellDetails[row][col].parent_i == row && cellDetails[row][col].parent_j == col)) { Path.push(make_pair(row, col)); int temp_row = cellDetails[row][col].parent_i; int temp_col = cellDetails[row][col].parent_j; row = temp_row; col = temp_col; } Path.push(make_pair(row, col)); while (!Path.empty()) { pair<int, int> p = Path.top(); Path.pop(); printf("-> (%d,%d) ", p.first, p.second); } return;}// A Function to find the shortest path between// a given source cell to a destination cell according// to A* Search Algorithmvoid aStarSearch(int grid[][COL], Pair src, Pair dest){ // If the source is out of range if (isValid(src.first, src.second) == false) { printf("Source is invalid
"); return; } // If the destination is out of range if (isValid(dest.first, dest.second) == false) { printf("Destination is invalid
"); return; } // Either the source or the destination is blocked if (isUnBlocked(grid, src.first, src.second) == false || isUnBlocked(grid, dest.first, dest.second) == false) { printf("Source or the destination is blocked
"); return; } // If the destination cell is the same as source cell if (isDestination(src.first, src.second, dest) == true) { printf("We are already at the destination
"); return; } // Create a closed list and initialise it to false which // means that no cell has been included yet This closed // list is implemented as a boolean 2D array bool closedList[ROW][COL]; memset(closedList, false, sizeof(closedList)); // Declare a 2D array of structure to hold the details // of that cell cell cellDetails[ROW][COL]; int i, j; for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) { cellDetails[i][j].f = FLT_MAX; cellDetails[i][j].g = FLT_MAX; cellDetails[i][j].h = FLT_MAX; cellDetails[i][j].parent_i = -1; cellDetails[i][j].parent_j = -1; } } // Initialising the parameters of the starting node i = src.first, j = src.second; cellDetails[i][j].f = 0.0; cellDetails[i][j].g = 0.0; cellDetails[i][j].h = 0.0; cellDetails[i][j].parent_i = i; cellDetails[i][j].parent_j = j; /* Create an open list having information as- <f, <i, j>> where f = g + h, and i, j are the row and column index of that cell Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1 This open list is implenented as a set of pair of pair.*/ set<pPair> openList; // Put the starting cell on the open list and set its // "f" as 0 openList.insert(make_pair(0.0, make_pair(i, j))); // We set this boolean value as false as initially // the destination is not reached. bool foundDest = false; while (!openList.empty()) { pPair p = *openList.begin(); // Remove this vertex from the open list openList.erase(openList.begin()); // Add this vertex to the closed list i = p.second.first; j = p.second.second; closedList[i][j] = true; /* Generating all the 8 successor of this cell N.W N N.E | / | / W----Cell----E / | / | S.W S S.E Cell-->Popped Cell (i, j) N --> North (i-1, j) S --> South (i+1, j) E --> East (i, j+1) W --> West (i, j-1) N.E--> North-East (i-1, j+1) N.W--> North-West (i-1, j-1) S.E--> South-East (i+1, j+1) S.W--> South-West (i+1, j-1)*/ // To store the "g", "h" and "f" of the 8 successors double gNew, hNew, fNew; //----------- 1st Successor (North) ------------ // Only process this cell if this is a valid one if (isValid(i - 1, j) == true) { // If the destination cell is the same as the // current successor if (isDestination(i - 1, j, dest) == true) { // Set the Parent of the destination cell cellDetails[i - 1][j].parent_i = i; cellDetails[i - 1][j].parent_j = j; printf("The destination cell is found
"); tracePath(cellDetails, dest); foundDest = true; return; } // If the successor is already on the closed // list or if it is blocked, then ignore it. // Else do the following else if (closedList[i - 1][j] == false && isUnBlocked(grid, i - 1, j) == true) { gNew = cellDetails[i][j].g + 1.0; hNew = calculateHValue(i - 1, j, dest); fNew = gNew + hNew; // If it isn’t on the open list, add it to // the open list. Make the current square // the parent of this square. Record the // f, g, and h costs of the square cell // OR // If it is on the open list already, check // to see if this path to that square is // better, using "f" cost as the measure. if (cellDetails[i - 1][j].f == FLT_MAX || cellDetails[i - 1][j].f > fNew) { openList.insert(make_pair( fNew, make_pair(i - 1, j))); // Update the details of this cell cellDetails[i - 1][j].f = fNew; cellDetails[i - 1][j].g = gNew; cellDetails[i - 1][j].h = hNew; cellDetails[i - 1][j].parent_i = i; cellDetails[i - 1][j].parent_j = j; } } } //----------- 2nd Successor (South) ------------ // Only process this cell if this is a valid one if (isValid(i + 1, j) == true) { // If the destination cell is the same as the // current successor if (isDestination(i + 1, j, dest) == true) { // Set the Parent of the destination cell cellDetails[i + 1][j].parent_i = i; cellDetails[i + 1][j].parent_j = j; printf("The destination cell is found
"); tracePath(cellDetails, dest); foundDest = true; return; } // If the successor is already on the closed // list or if it is blocked, then ignore it. // Else do the following else if (closedList[i + 1][j] == false && isUnBlocked(grid, i + 1, j) == true) { gNew = cellDetails[i][j].g + 1.0; hNew = calculateHValue(i + 1, j, dest); fNew = gNew + hNew; // If it isn’t on the open list, add it to // the open list. Make the current square // the parent of this square. Record the &n
РЕКОМЕНДУЕМЫЕ СТАТЬИ |