Рубрики

A * Алгоритм поиска

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

Мы можем рассмотреть 2D-сетку, имеющую несколько препятствий, и мы начинаем с исходной ячейки (красного цвета внизу), чтобы добраться до целевой клетки (зеленого цвета снизу)

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

Почему алгоритм поиска A *?
Неформально говоря, алгоритмы поиска A *, в отличие от других методов обхода, имеют «мозги». Это означает, что это действительно умный алгоритм, который отделяет его от других обычных алгоритмов. Этот факт подробно разъясняется в следующих разделах.
Также стоит упомянуть, что многие игры и веб-карты используют этот алгоритм для очень быстрого поиска кратчайшего пути (приближение).

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

Алгоритм поиска A * делает то, что на каждом шаге он выбирает узел в соответствии со значением — ' f ', которое является параметром, равным сумме двух других параметров — ' g ' и ' h '. На каждом этапе он выбирает узел / ячейку, имеющую наименьшее « f », и обрабатывает этот узел / ячейку.

Мы определяем « g » и « h » как можно проще ниже

g = стоимость перемещения для перемещения из начальной точки в заданный квадрат на сетке, следуя сгенерированному пути, чтобы туда добраться.
h = предполагаемая стоимость перемещения для перемещения от данного квадрата на сетке до конечного пункта назначения. Это часто называют эвристикой, которая представляет собой не что иное, как умное предположение. Мы действительно не знаем фактическое расстояние, пока не найдем путь, потому что на этом пути могут быть все виды вещей (стены, вода и т. Д.). Может быть много способов вычислить это «h», которые обсуждаются в последующих разделах.

Алгоритм
Мы создаем два списка — Открытый список и Закрытый список (так же, как алгоритм Дейкстры)

// A* Search Algorithm
1.  Initialize the open list
2.  Initialize the closed list
    put the starting node on the open 
    list (you can leave its f at zero)

3.  while the open list is not empty
    a) find the node with the least f on 
       the open list, call it "q"

    b) pop q off the open list
  
    c) generate q's 8 successors and set their 
       parents to q
   
    d) for each successor
        i) if successor is the goal, stop search
          successor.g = q.g + distance between 
                              successor and q
          successor.h = distance from goal to 
          successor (This can be done using many 
          ways, we will discuss three heuristics- 
          Manhattan, Diagonal and Euclidean 
          Heuristics)
          
          successor.f = successor.g + successor.h

        ii) if a node with the same position as 
            successor is in the OPEN list which has a 
           lower f than successor, skip this successor

        iii) if a node with the same position as 
            successor  is in the CLOSED list which has
            a lower f than successor, skip this successor
            otherwise, add  the node to the open list
     end (for loop)
  
    e) push q on the closed list
    end (while loop) 

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

Эвристика
Мы можем вычислить г, но как рассчитать ч?

Мы можем делать вещи.
A) Либо рассчитать точное значение h (что, безусловно, занимает много времени).
ИЛИ
Б) Приблизительное значение h с использованием некоторой эвристики (меньше времени).

Мы обсудим оба метода.

А) Точная эвристика

Мы можем найти точные значения h, но это, как правило, очень много времени.

Ниже приведены некоторые методы для вычисления точного значения h.

1) Предварительно вычислите расстояние между каждой парой ячеек перед запуском алгоритма поиска A *.

2) Если нет заблокированных ячеек / препятствий, то мы можем просто найти точное значение h без предварительного вычисления, используя формулу расстояния / евклидово расстояние

Б) Аппроксимация эвристики —

Как правило, существует три приближенных эвристики для расчета h —

1) Манхэттен Расстояние —

  • Это не что иное, как сумма абсолютных значений разностей в координатах x и y цели и координатах x и y текущей ячейки соответственно, т.е.
     h = abs (current_cell.x – goal.x) + 
         abs (current_cell.y – goal.y) 
  • Когда использовать эту эвристику? — Когда нам разрешено двигаться только в четырех направлениях (справа, слева, сверху, снизу)

Эвристика Манхэттенского расстояния показана на рисунке ниже (предполагается, что красное пятно является исходной ячейкой, а зеленое пятно — целевой ячейкой).

2) Диагональное расстояние

  • Это не что иное, как максимум абсолютных значений разностей в координатах x и y цели и координатах x и y текущей ячейки соответственно, т.е.
     h = max { abs(current_cell.x – goal.x),
               abs(current_cell.y – goal.y) } 
  • Когда использовать эту эвристику? — Когда нам разрешено двигаться только в восьми направлениях (похоже на ход короля в шахматах)

Эвристика диагонального расстояния показана на рисунке ниже (предполагается, что красное пятно является исходной ячейкой, а зеленое пятно — целевой ячейкой).

3) Евклидово расстояние

  • Как видно из его названия, это не что иное, как расстояние между текущей ячейкой и целевой ячейкой с использованием формулы расстояния
     h = sqrt ( (current_cell.x – goal.x)2 + 
                (current_cell.y – goal.y)2 ) 
  • Когда использовать эту эвристику? — Когда нам разрешено двигаться в любых направлениях.

Эвклидово эвристическое расстояние показано на рисунке ниже (предполагается, что красное пятно является исходной ячейкой, а зеленое пятно — целевой ячейкой).

Связь (сходство и различия) с другими алгоритмами
Дейкстра является частным случаем алгоритма поиска A *, где h = 0 для всех узлов.

Реализация
Мы можем использовать любую структуру данных для реализации открытого списка и закрытого списка, но для лучшей производительности мы используем заданную структуру данных C ++ STL (реализованную как Red-Black Tree) и булеву хеш-таблицу для закрытого списка.

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

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

// Программа на C ++ для реализации алгоритма поиска A *
#include<bits/stdc++.h>

using namespace std;

  
#define ROW 9
#define COL 10

  
// Создание ярлыка для типа пары int, int

typedef pair<int, int> Pair;

  
// Создание ярлыка для типа pair <int, pair <int, int >>

typedef pair<double, pair<int, int>> pPair;

  
// Структура для хранения необходимых параметров

struct cell

{

    // Строка и столбец индекса своего родителя

    // Обратите внимание, что 0 <= i <= ROW-1 & 0 <= j <= COL-1

    int parent_i, parent_j;

    // f = g + h

    double f, g, h;

};

  
// Функция утилиты, чтобы проверить, является ли данная ячейка (строка, столбец)
// является действительной ячейкой или нет.

bool isValid(int row, int col)

{

    // Возвращает true, если номер строки и номер столбца

    // находится в диапазоне

    return (row >= 0) && (row < ROW) &&

           (col >= 0) && (col < COL);

}

  
// Сервисная функция, чтобы проверить, является ли данная ячейка
// заблокирован или нет

bool isUnBlocked(int grid[][COL], int row, int col)

{

    // Возвращает true, если ячейка не заблокирована, иначе false

    if (grid[row][col] == 1)

        return (true);

    else

        return (false);

}

  
// служебная функция для проверки наличия ячейки назначения
// достигнут или нет

bool isDestination(int row, int col, Pair dest)

{

    if (row == dest.first && col == dest.second)

        return (true);

    else

        return (false);

}

  
// Сервисная функция для вычисления эвристики h.

double calculateHValue(int row, int col, Pair dest)

{

    // Возврат по формуле расстояния

    return ((double)sqrt ((row-dest.first)*(row-dest.first)

                          + (col-dest.second)*(col-dest.second)));

}

  
// Сервисная функция для отслеживания пути от источника
// к месту назначения

void tracePath(cell cellDetails[][COL], Pair dest)

{

    printf ("\nThe 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 * Алгоритм поиска

void aStarSearch(int grid[][COL], Pair src, Pair dest)

{

    // Если источник находится вне диапазона

    if (isValid (src.first, src.second) == false)

    {

        printf ("Source is invalid\n");

        return;

    }

  

    // Если пункт назначения находится вне диапазона

    if (isValid (dest.first, dest.second) == false)

    {

        printf ("Destination is invalid\n");

        return;

    }

  

    // Источник или место назначения заблокированы

    if (isUnBlocked(grid, src.first, src.second) == false ||

            isUnBlocked(grid, dest.first, dest.second) == false)

    {

        printf ("Source or the destination is blocked\n");

        return;

    }

  

    // Если ячейка назначения совпадает с ячейкой источника

    if (isDestination(src.first, src.second, dest) == true)

    {

        printf ("We are already at the destination\n");

        return;

    }

  

    // Создать закрытый список и инициализировать его как false, что означает

    // что ни одна ячейка еще не была включена

    // Этот закрытый список реализован как логический 2D массив

    bool closedList[ROW][COL];

    memset(closedList, false, sizeof (closedList));

  

    // Объявляем 2D массив структур для хранения деталей

    // этой ячейки

    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;

        }

    }

  

    // Инициализация параметров начального узла

    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;

  

    / *

     Создайте открытый список с информацией в виде

     <f, <i, j >>

     где f = g + h,

     и я, j являются индексом строки и столбца этой ячейки

     Обратите внимание, что 0 <= i <= ROW-1 & 0 <= j <= COL-1

     Этот открытый список представлен в виде пары пары. * /

    set<pPair> openList;

  

    // Помещаем начальную ячейку в открытый список и устанавливаем ее

    // 'f' как 0

    openList.insert(make_pair (0.0, make_pair (i, j)));

  

    // Мы устанавливаем это логическое значение как ложное как изначально

    // пункт назначения не достигнут

    bool foundDest = false;

  

    while (!openList.empty())

    {

        pPair p = *openList.begin();

  

        // Удалить эту вершину из открытого списка

        openList.erase(openList.begin());

  

        // Добавить эту вершину в закрытый список

        i = p.second.first;

        j = p.second.second;

        closedList[i][j] = true;

       

       / *

        Генерация всех 8 преемников этой клетки

  

            NW N NE

              / | /

               / | /

            W ---- ---- Сотовые Е

                 / | /

               / | /

            SW S SE

  

        Cell -> Popped Cell (i, j)

        N -> Север (i-1, j)

        S -> Юг (i + 1, j)

        E -> Восток (i, j + 1)

        W -> Запад (I, J-1)

        NE -> Северо-Восток (i-1, j + 1)

        СЗ -> Северо-Запад (i-1, j-1)

        SE -> Юго-Восток (i + 1, j + 1)

        SW -> Юго-Запад (i + 1, j-1) * /

  

        // Для хранения «g», «h» и «f» из 8 преемников

        double gNew, hNew, fNew;

  

        // ----------- 1-й преемник (Север) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid(i-1, j) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i-1, j, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i-1][j].parent_i = i;

                cellDetails[i-1][j].parent_j = j;

                printf ("The destination cell is found\n");

                tracePath (cellDetails, dest);

                foundDest = true;

                return;

            }

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            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;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i-1][j].f == FLT_MAX ||

                        cellDetails[i-1][j].f > fNew)

                {

                    openList.insert( make_pair(fNew,

                                               make_pair(i-1, j)));

  

                    // Обновляем детали этой ячейки

                    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;

                }

            }

        }

  

        // ----------- 2-й преемник (юг) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid(i+1, j) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i+1, j, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i+1][j].parent_i = i;

                cellDetails[i+1][j].parent_j = j;

                printf("The destination cell is found\n");

                tracePath(cellDetails, dest);

                foundDest = true;

                return;

            }

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            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;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i+1][j].f == FLT_MAX ||

                        cellDetails[i+1][j].f > fNew)

                {

                    openList.insert( make_pair (fNew, make_pair (i+1, j)));

                    // Обновляем детали этой ячейки

                    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;

                }

            }

        }

  

        // ----------- 3-й Преемник (Восток) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid (i, j+1) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i, j+1, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i][j+1].parent_i = i;

                cellDetails[i][j+1].parent_j = j;

                printf("The destination cell is found\n");

                tracePath(cellDetails, dest);

                foundDest = true;

                return;

            }

  

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            else if (closedList[i][j+1] == false &&

                     isUnBlocked (grid, i, j+1) == true)

            {

                gNew = cellDetails[i][j].g + 1.0;

                hNew = calculateHValue (i, j+1, dest);

                fNew = gNew + hNew;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i][j+1].f == FLT_MAX ||

                        cellDetails[i][j+1].f > fNew)

                {

                    openList.insert( make_pair(fNew,

                                        make_pair (i, j+1)));

  

                    // Обновляем детали этой ячейки

                    cellDetails[i][j+1].f = fNew;

                    cellDetails[i][j+1].g = gNew;

                    cellDetails[i][j+1].h = hNew;

                    cellDetails[i][j+1].parent_i = i;

                    cellDetails[i][j+1].parent_j = j;

                }

            }

        }

  

        // ----------- 4-й Преемник (Запад) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid(i, j-1) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i, j-1, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i][j-1].parent_i = i;

                cellDetails[i][j-1].parent_j = j;

                printf("The destination cell is found\n");

                tracePath(cellDetails, dest);

                foundDest = true;

                return;

            }

  

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            else if (closedList[i][j-1] == false &&

                     isUnBlocked(grid, i, j-1) == true)

            {

                gNew = cellDetails[i][j].g + 1.0;

                hNew = calculateHValue(i, j-1, dest);

                fNew = gNew + hNew;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i][j-1].f == FLT_MAX ||

                        cellDetails[i][j-1].f > fNew)

                {

                    openList.insert( make_pair (fNew,

                                          make_pair (i, j-1)));

  

                    // Обновляем детали этой ячейки

                    cellDetails[i][j-1].f = fNew;

                    cellDetails[i][j-1].g = gNew;

                    cellDetails[i][j-1].h = hNew;

                    cellDetails[i][j-1].parent_i = i;

                    cellDetails[i][j-1].parent_j = j;

                }

            }

        }

  

        // ----------- 5-й преемник (Северо-Восток) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid(i-1, j+1) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i-1, j+1, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i-1][j+1].parent_i = i;

                cellDetails[i-1][j+1].parent_j = j;

                printf ("The destination cell is found\n");

                tracePath (cellDetails, dest);

                foundDest = true;

                return;

            }

  

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            else if (closedList[i-1][j+1] == false &&

                     isUnBlocked(grid, i-1, j+1) == true)

            {

                gNew = cellDetails[i][j].g + 1.414;

                hNew = calculateHValue(i-1, j+1, dest);

                fNew = gNew + hNew;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i-1][j+1].f == FLT_MAX ||

                        cellDetails[i-1][j+1].f > fNew)

                {

                    openList.insert( make_pair (fNew, 

                                    make_pair(i-1, j+1)));

  

                    // Обновляем детали этой ячейки

                    cellDetails[i-1][j+1].f = fNew;

                    cellDetails[i-1][j+1].g = gNew;

                    cellDetails[i-1][j+1].h = hNew;

                    cellDetails[i-1][j+1].parent_i = i;

                    cellDetails[i-1][j+1].parent_j = j;

                }

            }

        }

  

        // ----------- 6-й преемник (Северо-Запад) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid (i-1, j-1) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination (i-1, j-1, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i-1][j-1].parent_i = i;

                cellDetails[i-1][j-1].parent_j = j;

                printf ("The destination cell is found\n");

                tracePath (cellDetails, dest);

                foundDest = true;

                return;

            }

  

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            else if (closedList[i-1][j-1] == false &&

                     isUnBlocked(grid, i-1, j-1) == true)

            {

                gNew = cellDetails[i][j].g + 1.414;

                hNew = calculateHValue(i-1, j-1, dest);

                fNew = gNew + hNew;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i-1][j-1].f == FLT_MAX ||

                        cellDetails[i-1][j-1].f > fNew)

                {

                    openList.insert( make_pair (fNew, make_pair (i-1, j-1)));

                    // Обновляем детали этой ячейки

                    cellDetails[i-1][j-1].f = fNew;

                    cellDetails[i-1][j-1].g = gNew;

                    cellDetails[i-1][j-1].h = hNew;

                    cellDetails[i-1][j-1].parent_i = i;

                    cellDetails[i-1][j-1].parent_j = j;

                }

            }

        }

  

        // ----------- 7-й преемник (Юго-Восток) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid(i+1, j+1) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i+1, j+1, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i+1][j+1].parent_i = i;

                cellDetails[i+1][j+1].parent_j = j;

                printf ("The destination cell is found\n");

                tracePath (cellDetails, dest);

                foundDest = true;

                return;

            }

  

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            else if (closedList[i+1][j+1] == false &&

                     isUnBlocked(grid, i+1, j+1) == true)

            {

                gNew = cellDetails[i][j].g + 1.414;

                hNew = calculateHValue(i+1, j+1, dest);

                fNew = gNew + hNew;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i+1][j+1].f == FLT_MAX ||

                        cellDetails[i+1][j+1].f > fNew)

                {

                    openList.insert(make_pair(fNew, 

                                        make_pair (i+1, j+1)));

  

                    // Обновляем детали этой ячейки

                    cellDetails[i+1][j+1].f = fNew;

                    cellDetails[i+1][j+1].g = gNew;

                    cellDetails[i+1][j+1].h = hNew;

                    cellDetails[i+1][j+1].parent_i = i;

                    cellDetails[i+1][j+1].parent_j = j;

                }

            }

        }

  

        // ----------- 8-й преемник (Юго-Запад) ------------

  

        // Обрабатываем только эту ячейку, если она действительна

        if (isValid (i+1, j-1) == true)

        {

            // Если ячейка назначения совпадает с

            // текущий преемник

            if (isDestination(i+1, j-1, dest) == true)

            {

                // Установить родителя ячейки назначения

                cellDetails[i+1][j-1].parent_i = i;

                cellDetails[i+1][j-1].parent_j = j;

                printf("The destination cell is found\n");

                tracePath(cellDetails, dest);

                foundDest = true;

                return;

            }

  

            // Если преемник уже закрыт

            // список или если он заблокирован, то игнорируйте его.

            // Остальное сделаем следующее

            else if (closedList[i+1][j-1] == false &&

                     isUnBlocked(grid, i+1, j-1) == true)

            {

                gNew = cellDetails[i][j].g + 1.414;

                hNew = calculateHValue(i+1, j-1, dest);

                fNew = gNew + hNew;

  

                // Если его нет в открытом списке, добавьте его в

                // открытый список. Сделать текущий квадрат

                // родитель этого квадрата. Запишите

                // f, g и h затраты квадратной ячейки

                // ИЛИ

                // Если он уже есть в открытом списке, проверьте

                // чтобы увидеть, лучше ли этот путь к этому квадрату,

                // используя стоимость 'f' в качестве меры.

                if (cellDetails[i+1][j-1].f == FLT_MAX ||

                        cellDetails[i+1][j-1].f > fNew)

                {

                    openList.insert(make_pair(fNew, 

                                        make_pair(i+1, j-1)));

  

                    // Обновляем детали этой ячейки

                    cellDetails[i+1][j-1].f = fNew;

                    cellDetails[i+1][j-1].g = gNew;

                    cellDetails[i+1][j-1].h = hNew;

                    cellDetails[i+1][j-1].parent_i = i;

                    cellDetails[i+1][j-1].parent_j = j;

                }

            }

        }

    }

  

    // когда ячейка назначения не найдена и открыт

    // список пуст, тогда мы заключаем, что нам не удалось

    // достичь ячейки опустошения. Это может произойти, когда

    // нет пути к ячейке назначения (из-за блокировки)

    if (foundDest == false)

        printf("Failed to find the Destination Cell\n");

  

    return;

}

  

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    / * Описание сетки

     1 -> Ячейка не заблокирована

     0 -> Ячейка заблокирована * /

    int grid[ROW][COL] =

    {

        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },

        { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },

        { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 },

        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },

        { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },

        { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },

        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

        { 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 }

    };

  

    // Источник - самый левый нижний угол

    Pair src = make_pair(8, 0);

  

    // Пункт назначения - самый левый верхний угол

    Pair dest = make_pair(0, 0);

  

    aStarSearch(grid, src, dest);

  

    return(0);

}

Ограничения
Несмотря на то, что алгоритм поиска A * является наилучшим алгоритмом поиска, он не всегда дает кратчайший путь, так как он сильно зависит от эвристики / аппроксимации для расчета — h

Приложения
Это самая интересная часть алгоритма поиска A *. Они используются в играх! Но как?

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

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

Одним из примеров этого является очень популярная игра — Warcraft III

Что, если пространство поиска не является сеткой и графиком?

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

Сложность времени
Рассматривая график, нам может потребоваться пройти весь край, чтобы достичь ячейки назначения от исходной ячейки [Например, рассмотрим график, где узлы источника и назначения связаны рядом ребер, например — 0 (источник) -> 1 -> 2 -> 3 (цель)

Таким образом, сложность времени в худшем случае — O (E), где E — число ребер в графе.

Вспомогательное пространство В худшем случае мы можем иметь все ребра внутри открытого списка, поэтому в худшем случае требуемое вспомогательное пространство — это O (V), где V — общее количество вершин.

Упражнение для читателей
Всегда удивлялся, как сделать игру похожей на Пакмана, где есть много таких препятствий. Можем ли мы использовать алгоритм поиска A *, чтобы найти правильный путь?

Думайте об этом как о веселом упражнении.

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

Резюме
Так, когда использовать DFS над A *, когда использовать Dijkstra над A *, чтобы найти кратчайшие пути?
Мы можем обобщить это как ниже-

1) Один источник и один пункт назначения
→ Использовать алгоритм поиска A * (для взвешенных и взвешенных графиков)

2) Один источник, все предназначение —
→ Использовать BFS (для невзвешенных графиков)
→ Используйте Dijkstra (для взвешенных графиков без отрицательных весов)
→ Используйте Bellman Ford (для взвешенных графиков с отрицательными весами)

3) Между каждой парой узлов
→ Флойд-Варшалл
→ Алгоритм Джонсона

Связанная статья:
Лучший первый поиск (информированный поиск)

Ссылки-
http://theory.stanford.edu/~amitp/GameProgramming/
https://en.wikipedia.org/wiki/A*_search_algorithm

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

A * Алгоритм поиска

0.00 (0%) 0 votes