devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

路径规划算法 | A* 搜索算法_路径搜索与遍历算法

作者：菜鸟追梦旅行 | 2024-06-06 23:25:06

赞

踩

路径搜索与遍历算法

作者：Rachit Belwariar

编译：东岸因为@一点人工一点智能

路径规划算法 | A* 搜索算法icon-default.png?t=N7T8https://mp.weixin.qq.com/s/lTVkknLWZ4ERYnv8m0JCGQ

动机：为了在现实生活中近似求解最短路径，例如地图、游戏等存在许多障碍物的情况。我们可以考虑一个含有多个障碍物的二维网格图，我们从起始单元格（下方红色标记）开始，朝着目标单元格（下方绿色标记）前进。

01 什么是A*搜索算法

A*搜索算法是一种用于路径搜索和图遍历的效果很好、主流的技术之一。

1.1 为什么选择A*搜索算法？

简单地说，A*搜索算法与其他遍历技术不同，它具有“智能”。这意味着它是一种非常智能的算法，与其他传统算法有所区别。下面的部分将详细解释这一点。

值得一提的是，许多游戏和基于Web的地图使用这个算法来高效地找到最短路径（近似）。

1.2 解释

考虑一个有许多障碍物的正方形网格，给定一个起始单元格和一个目标单元格。我们希望尽快从起始单元格到达目标单元格（如果可能）。这时A*搜索算法就派上用场了。

A*搜索算法在每一步中选择一个节点，根据一个值f来确定，该值是两个其他参数g和h的函数。在每一步中，它选择具有最低f值的节点/单元格，并处理该节点/单元格。

我们将g和h定义如下：

g：从起点到网格上的某个给定方格的移动成本，沿着生成的路径进行移动。

h：从给定方格到最终目的地的估计移动成本。这通常被称为启发式，它只是一种聪明的猜测。在找到路径之前，我们真的不知道实际距离，因为各种东西可能阻会妨碍规划的路径（墙壁、水等）。有许多计算这个h值的方法，这些方法在后面的部分中进行了讨论。

02 算法

我们创建两个列表 - 开放列表（Open list)和封闭列表(Closed list)（就像Dijkstra算法一样）。

  1. // A* Search Algorithm
  2. 1.  Initialize the open list
  3. 2.  Initialize the closed list
  4.     put the starting node on the open 
  5.     list (you can leave its f at zero)
  6. 3.  while the open list is not empty
  7.     a) find the node with the least f on 
  8.        the open list, call it "q"
  9.     b) pop q off the open list
  10.   
  11.     c) generate q's 8 successors and set their 
  12.        parents to q
  13.    
  14.     d) for each successor
  15.         i) if successor is the goal, stop search
  16.         
  17.         ii) else, compute both g and h for successor
  18.           successor.g = q.g + distance between 
  19.                               successor and q
  20.           successor.h = distance from goal to 
  21.           successor (This can be done using many 
  22.           ways, we will discuss three heuristics- 
  23.           Manhattan, Diagonal and Euclidean 
  24.           Heuristics)
  25.           
  26.           successor.f = successor.g + successor.h
  27.         iii) if a node with the same position as 
  28.             successor is in the OPEN list which has a 
  29.            lower f than successor, skip this successor
  30.         iV) if a node with the same position as 
  31.             successor  is in the CLOSED list which has
  32.             a lower f than successor, skip this successor
  33.             otherwise, add  the node to the open list
  34.      end (for loop)
  35.   
  36.     e) push q on the closed list
  37.     end (while loop)

所以假设如下图所示，如果我们想要从起始单元格到达目标单元格，A*搜索算法将按照下图所示的路径进行搜索。请注意，下图是根据欧几里德距离作为启发式算法生成的。

03 启发式算法

我们可以计算g，但如何计算h呢？

我们可以采取以下方法：A) 要么计算h的精确值（这肯定是耗时的），或者 B) 使用某些启发式方法来近似计算h（时间消耗较少）。

我们将讨论这两种方法。

3.1 精确启发式

我们可以找到h的精确值，但通常这需要很长时间。

以下是一些计算h精确值的方法。

1) 在运行A*搜索算法之前，预先计算每对单元格之间的距离。

2) 如果没有阻塞单元格（障碍物），我们可以使用距离公式/欧几里德距离，在不进行任何预先计算的情况下找到h的精确值。

3.2 近似启发式

通常有三种近似启发式方法来计算h：

1) 曼哈顿距离：

· 它是目标点的x坐标和y坐标与当前单元格的x坐标和y坐标之间差值的绝对值之和，即：

 h = abs (current_cell.x – goal.x) + abs (current_cell.y – goal.y)

· 当只允许在四个方向上移动（右、左、上、下）时，我们可以使用这个启发式算法。曼哈顿距离启发式算法可以通过下图表示（假设红点为起始单元格，绿点为目标单元格）。

2) 对角线距离：

· 它是目标点的x坐标和y坐标与当前单元格的x坐标和y坐标之间差值的绝对值的最大值，即：

  1. dx = abs(current_cell.x – goal.x)
  2. dy = abs(current_cell.y – goal.y)
  3.  
  4. h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
  5. where D is length of each node(usually = 1) and D2 is diagonal distance between each node (usually = sqrt(2) ).

· 当只允许在八个方向上移动时（类似于国际象棋中的国王移动），我们可以使用这个启发式算法。

对角线距离启发式算法可以通过下图表示（假设红点为起始单元格，绿点为目标单元格）。

3) 欧几里德距离：

· 顾名思义，它就是使用距离公式计算当前单元格与目标单元格之间的距离。

 h = sqrt ( (current_cell.x – goal.x)2 + (current_cell.y – goal.y)2 )

· 这个启发式算法什么时候使用呢？- 当我们被允许在任意方向上移动时。

欧几里德距离启发式算法可以通过下图表示（假设红点为起始单元格，绿点为目标单元格）。

与其他算法的关系（相似性和差异）：Dijkstra算法是A*搜索算法的特例，其中所有节点的h值都为0。

04 实现

我们可以使用任何数据结构来实现开放列表和封闭列表，但为了获得最佳性能，我们使用C++ STL中的集合数据结构（实现为红黑树）和一个布尔哈希表用于封闭列表。

实现与Dijkstra算法类似。如果我们使用斐波那契堆来实现开放列表，而不是使用二叉堆/自平衡树，那么性能将会更好（因为斐波那契堆在平均情况下需要O(1)的时间来插入到开放列表并减小键值）。

此外，为了减少计算g所需的时间，我们将使用动态规划。

  1. // A C++ Program to implement A* Search Algorithm
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ROW 9
  6. #define COL 10
  7.  
  8. // Creating a shortcut for int, int pair type
  9. typedef pair<int, int> Pair;
  10.  
  11. // Creating a shortcut for pair<int, pair<int, int>> type
  12. typedef pair<double, pair<int, int> > pPair;
  13.  
  14. // A structure to hold the necessary parameters
  15. struct cell {
  16.   // Row and Column index of its parent
  17.   // Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
  18.   int parent_i, parent_j;
  19.   // f = g + h
  20.   double f, g, h;
  21. };
  22.  
  23. // A Utility Function to check whether given cell (row, col)
  24. // is a valid cell or not.
  25. bool isValid(int row, int col)
  26. {
  27.   // Returns true if row number and column number
  28.   // is in range
  29.   return (row >= 0) && (row < ROW) && (col >= 0)
  30.     && (col < COL);
  31. }
  32.  
  33. // A Utility Function to check whether the given cell is
  34. // blocked or not
  35. bool isUnBlocked(int grid[][COL], int row, int col)
  36. {
  37.   // Returns true if the cell is not blocked else false
  38.   if (grid[row][col] == 1)
  39.     return (true);
  40.   else
  41.     return (false);
  42. }
  43.  
  44. // A Utility Function to check whether destination cell has
  45. // been reached or not
  46. bool isDestination(int row, int col, Pair dest)
  47. {
  48.   if (row == dest.first && col == dest.second)
  49.     return (true);
  50.   else
  51.     return (false);
  52. }
  53.  
  54. // A Utility Function to calculate the 'h' heuristics.
  55. double calculateHValue(int row, int col, Pair dest)
  56. {
  57.   // Return using the distance formula
  58.   return ((double)sqrt(
  59.     (row - dest.first) * (row - dest.first)
  60.     + (col - dest.second) * (col - dest.second)));
  61. }
  62.  
  63. // A Utility Function to trace the path from the source
  64. // to destination
  65. void tracePath(cell cellDetails[][COL], Pair dest)
  66. {
  67.   printf("\nThe Path is ");
  68.   int row = dest.first;
  69.   int col = dest.second;
  70.  
  71.   stack<Pair> Path;
  72.  
  73.   while (!(cellDetails[row][col].parent_i == row
  74.       && cellDetails[row][col].parent_j == col)) {
  75.     Path.push(make_pair(row, col));
  76.     int temp_row = cellDetails[row][col].parent_i;
  77.     int temp_col = cellDetails[row][col].parent_j;
  78.     row = temp_row;
  79.     col = temp_col;
  80.   }
  81.  
  82.   Path.push(make_pair(row, col));
  83.   while (!Path.empty()) {
  84.     pair<int, int> p = Path.top();
  85.     Path.pop();
  86.     printf("-> (%d,%d) ", p.first, p.second);
  87.   }
  88.  
  89.   return;
  90. }
  91.  
  92. // A Function to find the shortest path between
  93. // a given source cell to a destination cell according
  94. // to A* Search Algorithm
  95. void aStarSearch(int grid[][COL], Pair src, Pair dest)
  96. {
  97.   // If the source is out of range
  98.   if (isValid(src.first, src.second) == false) {
  99.     printf("Source is invalid\n");
  100.     return;
  101.   }
  102.  
  103.   // If the destination is out of range
  104.   if (isValid(dest.first, dest.second) == false) {
  105.     printf("Destination is invalid\n");
  106.     return;
  107.   }
  108.  
  109.   // Either the source or the destination is blocked
  110.   if (isUnBlocked(grid, src.first, src.second) == false
  111.     || isUnBlocked(grid, dest.first, dest.second)
  112.       == false) {
  113.     printf("Source or the destination is blocked\n");
  114.     return;
  115.   }
  116.  
  117.   // If the destination cell is the same as source cell
  118.   if (isDestination(src.first, src.second, dest)
  119.     == true) {
  120.     printf("We are already at the destination\n");
  121.     return;
  122.   }
  123.  
  124.   // Create a closed list and initialise it to false which
  125.   // means that no cell has been included yet This closed
  126.   // list is implemented as a boolean 2D array
  127.   bool closedList[ROW][COL];
  128.   memset(closedList, false, sizeof(closedList));
  129.  
  130.   // Declare a 2D array of structure to hold the details
  131.   // of that cell
  132.   cell cellDetails[ROW][COL];
  133.  
  134.   int i, j;
  135.  
  136.   for (i = 0; i < ROW; i++) {
  137.     for (j = 0; j < COL; j++) {
  138.       cellDetails[i][j].f = FLT_MAX;
  139.       cellDetails[i][j].g = FLT_MAX;
  140.       cellDetails[i][j].h = FLT_MAX;
  141.       cellDetails[i][j].parent_i = -1;
  142.       cellDetails[i][j].parent_j = -1;
  143.     }
  144.   }
  145.  
  146.   // Initialising the parameters of the starting node
  147.   i = src.first, j = src.second;
  148.   cellDetails[i][j].f = 0.0;
  149.   cellDetails[i][j].g = 0.0;
  150.   cellDetails[i][j].h = 0.0;
  151.   cellDetails[i][j].parent_i = i;
  152.   cellDetails[i][j].parent_j = j;
  153.  
  154.   /*
  155.   Create an open list having information as-
  156.   <f, <i, j>>
  157.   where f = g + h,
  158.   and i, j are the row and column index of that cell
  159.   Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
  160.   This open list is implemented as a set of pair of
  161.   pair.*/
  162.   set<pPair> openList;
  163.  
  164.   // Put the starting cell on the open list and set its
  165.   // 'f' as 0
  166.   openList.insert(make_pair(0.0, make_pair(i, j)));
  167.  
  168.   // We set this boolean value as false as initially
  169.   // the destination is not reached.
  170.   bool foundDest = false;
  171.  
  172.   while (!openList.empty()) {
  173.     pPair p = *openList.begin();
  174.  
  175.     // Remove this vertex from the open list
  176.     openList.erase(openList.begin());
  177.  
  178.     // Add this vertex to the closed list
  179.     i = p.second.first;
  180.     j = p.second.second;
  181.     closedList[i][j] = true;
  182.  
  183.     /*
  184.     Generating all the 8 successor of this cell
  185.  
  186.       N.W N N.E
  187.       \ | /
  188.         \ | /
  189.       W----Cell----E
  190.         / | \
  191.         / | \
  192.       S.W S S.E
  193.  
  194.     Cell-->Popped Cell (i, j)
  195.     N --> North   (i-1, j)
  196.     S --> South   (i+1, j)
  197.     E --> East   (i, j+1)
  198.     W --> West     (i, j-1)
  199.     N.E--> North-East (i-1, j+1)
  200.     N.W--> North-West (i-1, j-1)
  201.     S.E--> South-East (i+1, j+1)
  202.     S.W--> South-West (i+1, j-1)*/
  203.  
  204.     // To store the 'g', 'h' and 'f' of the 8 successors
  205.     double gNew, hNew, fNew;
  206.  
  207.     //----------- 1st Successor (North) ------------
  208.  
  209.     // Only process this cell if this is a valid one
  210.     if (isValid(i - 1, j) == true) {
  211.       // If the destination cell is the same as the
  212.       // current successor
  213.       if (isDestination(i - 1, j, dest) == true) {
  214.         // Set the Parent of the destination cell
  215.         cellDetails[i - 1][j].parent_i = i;
  216.         cellDetails[i - 1][j].parent_j = j;
  217.         printf("The destination cell is found\n");
  218.         tracePath(cellDetails, dest);
  219.         foundDest = true;
  220.         return;
  221.       }
  222.       // If the successor is already on the closed
  223.       // list or if it is blocked, then ignore it.
  224.       // Else do the following
  225.       else if (closedList[i - 1][j] == false
  226.           && isUnBlocked(grid, i - 1, j)
  227.               == true) {
  228.         gNew = cellDetails[i][j].g + 1.0;
  229.         hNew = calculateHValue(i - 1, j, dest);
  230.         fNew = gNew + hNew;
  231.  
  232.         // If it isn’t on the open list, add it to
  233.         // the open list. Make the current square
  234.         // the parent of this square. Record the
  235.         // f, g, and h costs of the square cell
  236.         //       OR
  237.         // If it is on the open list already, check
  238.         // to see if this path to that square is
  239.         // better, using 'f' cost as the measure.
  240.         if (cellDetails[i - 1][j].f == FLT_MAX
  241.           || cellDetails[i - 1][j].f > fNew) {
  242.           openList.insert(make_pair(
  243.             fNew, make_pair(i - 1, j)));
  244.  
  245.           // Update the details of this cell
  246.           cellDetails[i - 1][j].f = fNew;
  247.           cellDetails[i - 1][j].g = gNew;
  248.           cellDetails[i - 1][j].h = hNew;
  249.           cellDetails[i - 1][j].parent_i = i;
  250.           cellDetails[i - 1][j].parent_j = j;
  251.         }
  252.       }
  253.     }
  254.  
  255.     //----------- 2nd Successor (South) ------------
  256.  
  257.     // Only process this cell if this is a valid one
  258.     if (isValid(i + 1, j) == true) {
  259.       // If the destination cell is the same as the
  260.       // current successor
  261.       if (isDestination(i + 1, j, dest) == true) {
  262.         // Set the Parent of the destination cell
  263.         cellDetails[i + 1][j].parent_i = i;
  264.         cellDetails[i + 1][j].parent_j = j;
  265.         printf("The destination cell is found\n");
  266.         tracePath(cellDetails, dest);
  267.         foundDest = true;
  268.         return;
  269.       }
  270.       // If the successor is already on the closed
  271.       // list or if it is blocked, then ignore it.
  272.       // Else do the following
  273.       else if (closedList[i + 1][j] == false
  274.           && isUnBlocked(grid, i + 1, j)
  275.               == true) {
  276.         gNew = cellDetails[i][j].g + 1.0;
  277.         hNew = calculateHValue(i + 1, j, dest);
  278.         fNew = gNew + hNew;
  279.  
  280.         // If it isn’t on the open list, add it to
  281.         // the open list. Make the current square
  282.         // the parent of this square. Record the
  283.         // f, g, and h costs of the square cell
  284.         //       OR
  285.         // If it is on the open list already, check
  286.         // to see if this path to that square is
  287.         // better, using 'f' cost as the measure.
  288.         if (cellDetails[i + 1][j].f == FLT_MAX
  289.           || cellDetails[i + 1][j].f > fNew) {
  290.           openList.insert(make_pair(
  291.             fNew, make_pair(i + 1, j)));
  292.           // Update the details of this cell
  293.           cellDetails[i + 1][j].f = fNew;
  294.           cellDetails[i + 1][j].g = gNew;
  295.           cellDetails[i + 1][j].h = hNew;
  296.           cellDetails[i + 1][j].parent_i = i;
  297.           cellDetails[i + 1][j].parent_j = j;
  298.         }
  299.       }
  300.     }
  301.  
  302.     //----------- 3rd Successor (East) ------------
  303.  
  304.     // Only process this cell if this is a valid one
  305.     if (isValid(i, j + 1) == true) {
  306.       // If the destination cell is the same as the
  307.       // current successor
  308.       if (isDestination(i, j + 1, dest) == true) {
  309.         // Set the Parent of the destination cell
  310.         cellDetails[i][j + 1].parent_i = i;
  311.         cellDetails[i][j + 1].parent_j = j;
  312.         printf("The destination cell is found\n");
  313.         tracePath(cellDetails, dest);
  314.         foundDest = true;
  315.         return;
  316.       }
  317.  
  318.       // If the successor is already on the closed
  319.       // list or if it is blocked, then ignore it.
  320.       // Else do the following
  321.       else if (closedList[i][j + 1] == false
  322.           && isUnBlocked(grid, i, j + 1)
  323.               == true) {
  324.         gNew = cellDetails[i][j].g + 1.0;
  325.         hNew = calculateHValue(i, j + 1, dest);
  326.         fNew = gNew + hNew;
  327.  
  328.         // If it isn’t on the open list, add it to
  329.         // the open list. Make the current square
  330.         // the parent of this square. Record the
  331.         // f, g, and h costs of the square cell
  332.         //       OR
  333.         // If it is on the open list already, check
  334.         // to see if this path to that square is
  335.         // better, using 'f' cost as the measure.
  336.         if (cellDetails[i][j + 1].f == FLT_MAX
  337.           || cellDetails[i][j + 1].f > fNew) {
  338.           openList.insert(make_pair(
  339.             fNew, make_pair(i, j + 1)));
  340.  
  341.           // Update the details of this cell
  342.           cellDetails[i][j + 1].f = fNew;
  343.           cellDetails[i][j + 1].g = gNew;
  344.           cellDetails[i][j + 1].h = hNew;
  345.           cellDetails[i][j + 1].parent_i = i;
  346.           cellDetails[i][j + 1].parent_j = j;
  347.         }
  348.       }
  349.     }
  350.  
  351.     //----------- 4th Successor (West) ------------
  352.  
  353.     // Only process this cell if this is a valid one
  354.     if (isValid(i, j - 1) == true) {
  355.       // If the destination cell is the same as the
  356.       // current successor
  357.       if (isDestination(i, j - 1, dest) == true) {
  358.         // Set the Parent of the destination cell
  359.         cellDetails[i][j - 1].parent_i = i;
  360.         cellDetails[i][j - 1].parent_j = j;
  361.         printf("The destination cell is found\n");
  362.         tracePath(cellDetails, dest);
  363.         foundDest = true;
  364.         return;
  365.       }
  366.  
  367.       // If the successor is already on the closed
  368.       // list or if it is blocked, then ignore it.
  369.       // Else do the following
  370.       else if (closedList[i][j - 1] == false
  371.           && isUnBlocked(grid, i, j - 1)
  372.               == true) {
  373.         gNew = cellDetails[i][j].g + 1.0;
  374.         hNew = calculateHValue(i, j - 1, dest);
  375.         fNew = gNew + hNew;
  376.  
  377.         // If it isn’t on the open list, add it to
  378.         // the open list. Make the current square
  379.         // the parent of this square. Record the
  380.         // f, g, and h costs of the square cell
  381.         //       OR
  382.         // If it is on the open list already, check
  383.         // to see if this path to that square is
  384.         // better, using 'f' cost as the measure.
  385.         if (cellDetails[i][j - 1].f == FLT_MAX
  386.           || cellDetails[i][j - 1].f > fNew) {
  387.           openList.insert(make_pair(
  388.             fNew, make_pair(i, j - 1)));
  389.  
  390.           // Update the details of this cell
  391.           cellDetails[i][j - 1].f = fNew;
  392.           cellDetails[i][j - 1].g = gNew;
  393.           cellDetails[i][j - 1].h = hNew;
  394.           cellDetails[i][j - 1].parent_i = i;
  395.           cellDetails[i][j - 1].parent_j = j;
  396.         }
  397.       }
  398.     }
  399.  
  400.     //----------- 5th Successor (North-East)
  401.     //------------
  402.  
  403.     // Only process this cell if this is a valid one
  404.     if (isValid(i - 1, j + 1) == true) {
  405.       // If the destination cell is the same as the
  406.       // current successor
  407.       if (isDestination(i - 1, j + 1, dest) == true) {
  408.         // Set the Parent of the destination cell
  409.         cellDetails[i - 1][j + 1].parent_i = i;
  410.         cellDetails[i - 1][j + 1].parent_j = j;
  411.         printf("The destination cell is found\n");
  412.         tracePath(cellDetails, dest);
  413.         foundDest = true;
  414.         return;
  415.       }
  416.  
  417.       // If the successor is already on the closed
  418.       // list or if it is blocked, then ignore it.
  419.       // Else do the following
  420.       else if (closedList[i - 1][j + 1] == false
  421.           && isUnBlocked(grid, i - 1, j + 1)
  422.               == true) {
  423.         gNew = cellDetails[i][j].g + 1.414;
  424.         hNew = calculateHValue(i - 1, j + 1, dest);
  425.         fNew = gNew + hNew;
  426.  
  427.         // If it isn’t on the open list, add it to
  428.         // the open list. Make the current square
  429.         // the parent of this square. Record the
  430.         // f, g, and h costs of the square cell
  431.         //       OR
  432.         // If it is on the open list already, check
  433.         // to see if this path to that square is
  434.         // better, using 'f' cost as the measure.
  435.         if (cellDetails[i - 1][j + 1].f == FLT_MAX
  436.           || cellDetails[i - 1][j + 1].f > fNew) {
  437.           openList.insert(make_pair(
  438.             fNew, make_pair(i - 1, j + 1)));
  439.  
  440.           // Update the details of this cell
  441.           cellDetails[i - 1][j + 1].f = fNew;
  442.           cellDetails[i - 1][j + 1].g = gNew;
  443.           cellDetails[i - 1][j + 1].h = hNew;
  444.           cellDetails[i - 1][j + 1].parent_i = i;
  445.           cellDetails[i - 1][j + 1].parent_j = j;
  446.         }
  447.       }
  448.     }
  449.  
  450.     //----------- 6th Successor (North-West)
  451.     //------------
  452.  
  453.     // Only process this cell if this is a valid one
  454.     if (isValid(i - 1, j - 1) == true) {
  455.       // If the destination cell is the same as the
  456.       // current successor
  457.       if (isDestination(i - 1, j - 1, dest) == true) {
  458.         // Set the Parent of the destination cell
  459.         cellDetails[i - 1][j - 1].parent_i = i;
  460.         cellDetails[i - 1][j - 1].parent_j = j;
  461.         printf("The destination cell is found\n");
  462.         tracePath(cellDetails, dest);
  463.         foundDest = true;
  464.         return;
  465.       }
  466.  
  467.       // If the successor is already on the closed
  468.       // list or if it is blocked, then ignore it.
  469.       // Else do the following
  470.       else if (closedList[i - 1][j - 1] == false
  471.           && isUnBlocked(grid, i - 1, j - 1)
  472.               == true) {
  473.         gNew = cellDetails[i][j].g + 1.414;
  474.         hNew = calculateHValue(i - 1, j - 1, dest);
  475.         fNew = gNew + hNew;
  476.  
  477.         // If it isn’t on the open list, add it to
  478.         // the open list. Make the current square
  479.         // the parent of this square. Record the
  480.         // f, g, and h costs of the square cell
  481.         //       OR
  482.         // If it is on the open list already, check
  483.         // to see if this path to that square is
  484.         // better, using 'f' cost as the measure.
  485.         if (cellDetails[i - 1][j - 1].f == FLT_MAX
  486.           || cellDetails[i - 1][j - 1].f > fNew) {
  487.           openList.insert(make_pair(
  488.             fNew, make_pair(i - 1, j - 1)));
  489.           // Update the details of this cell
  490.           cellDetails[i - 1][j - 1].f = fNew;
  491.           cellDetails[i - 1][j - 1].g = gNew;
  492.           cellDetails[i - 1][j - 1].h = hNew;
  493.           cellDetails[i - 1][j - 1].parent_i = i;
  494.           cellDetails[i - 1][j - 1].parent_j = j;
  495.         }
  496.       }
  497.     }
  498.  
  499.     //----------- 7th Successor (South-East)
  500.     //------------
  501.  
  502.     // Only process this cell if this is a valid one
  503.     if (isValid(i + 1, j + 1) == true) {
  504.       // If the destination cell is the same as the
  505.       // current successor
  506.       if (isDestination(i + 1, j + 1, dest) == true) {
  507.         // Set the Parent of the destination cell
  508.         cellDetails[i + 1][j + 1].parent_i = i;
  509.         cellDetails[i + 1][j + 1].parent_j = j;
  510.         printf("The destination cell is found\n");
  511.         tracePath(cellDetails, dest);
  512.         foundDest = true;
  513.         return;
  514.       }
  515.  
  516.       // If the successor is already on the closed
  517.       // list or if it is blocked, then ignore it.
  518.       // Else do the following
  519.       else if (closedList[i + 1][j + 1] == false
  520.           && isUnBlocked(grid, i + 1, j + 1)
  521.               == true) {
  522.         gNew = cellDetails[i][j].g + 1.414;
  523.         hNew = calculateHValue(i + 1, j + 1, dest);
  524.         fNew = gNew + hNew;
  525.  
  526.         // If it isn’t on the open list, add it to
  527.         // the open list. Make the current square
  528.         // the parent of this square. Record the
  529.         // f, g, and h costs of the square cell
  530.         //       OR
  531.         // If it is on the open list already, check
  532.         // to see if this path to that square is
  533.         // better, using 'f' cost as the measure.
  534.         if (cellDetails[i + 1][j + 1].f == FLT_MAX
  535.           || cellDetails[i + 1][j + 1].f > fNew) {
  536.           openList.insert(make_pair(
  537.             fNew, make_pair(i + 1, j + 1)));
  538.  
  539.           // Update the details of this cell
  540.           cellDetails[i + 1][j + 1].f = fNew;
  541.           cellDetails[i + 1][j + 1].g = gNew;
  542.           cellDetails[i + 1][j + 1].h = hNew;
  543.           cellDetails[i + 1][j + 1].parent_i = i;
  544.           cellDetails[i + 1][j + 1].parent_j = j;
  545.         }
  546.       }
  547.     }
  548.  
  549.     //----------- 8th Successor (South-West)
  550.     //------------
  551.  
  552.     // Only process this cell if this is a valid one
  553.     if (isValid(i + 1, j - 1) == true) {
  554.       // If the destination cell is the same as the
  555.       // current successor
  556.       if (isDestination(i + 1, j - 1, dest) == true) {
  557.         // Set the Parent of the destination cell
  558.         cellDetails[i + 1][j - 1].parent_i = i;
  559.         cellDetails[i + 1][j - 1].parent_j = j;
  560.         printf("The destination cell is found\n");
  561.         tracePath(cellDetails, dest);
  562.         foundDest = true;
  563.         return;
  564.       }
  565.  
  566.       // If the successor is already on the closed
  567.       // list or if it is blocked, then ignore it.
  568.       // Else do the following
  569.       else if (closedList[i + 1][j - 1] == false
  570.           && isUnBlocked(grid, i + 1, j - 1)
  571.               == true) {
  572.         gNew = cellDetails[i][j].g + 1.414;
  573.         hNew = calculateHValue(i + 1, j - 1, dest);
  574.         fNew = gNew + hNew;
  575.  
  576.         // If it isn’t on the open list, add it to
  577.         // the open list. Make the current square
  578.         // the parent of this square. Record the
  579.         // f, g, and h costs of the square cell
  580.         //       OR
  581.         // If it is on the open list already, check
  582.         // to see if this path to that square is
  583.         // better, using 'f' cost as the measure.
  584.         if (cellDetails[i + 1][j - 1].f == FLT_MAX
  585.           || cellDetails[i + 1][j - 1].f > fNew) {
  586.           openList.insert(make_pair(
  587.             fNew, make_pair(i + 1, j - 1)));
  588.  
  589.           // Update the details of this cell
  590.           cellDetails[i + 1][j - 1].f = fNew;
  591.           cellDetails[i + 1][j - 1].g = gNew;
  592.           cellDetails[i + 1][j - 1].h = hNew;
  593.           cellDetails[i + 1][j - 1].parent_i = i;
  594.           cellDetails[i + 1][j - 1].parent_j = j;
  595.         }
  596.       }
  597.     }
  598.   }
  599.  
  600.   // When the destination cell is not found and the open
  601.   // list is empty, then we conclude that we failed to
  602.   // reach the destination cell. This may happen when the
  603.   // there is no way to destination cell (due to
  604.   // blockages)
  605.   if (foundDest == false)
  606.     printf("Failed to find the Destination Cell\n");
  607.  
  608.   return;
  609. }
  610.  
  611. // Driver program to test above function
  612. int main()
  613. {
  614.   /* Description of the Grid-
  615.   1--> The cell is not blocked
  616.   0--> The cell is blocked */
  617.   int grid[ROW][COL]
  618.     = { { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
  619.       { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
  620.       { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
  621.       { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
  622.       { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
  623.       { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
  624.       { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
  625.       { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
  626.       { 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 } };
  627.  
  628.   // Source is the left-most bottom-most corner
  629.   Pair src = make_pair(8, 0);
  630.  
  631.   // Destination is the left-most top-most corner
  632.   Pair dest = make_pair(0, 0);
  633.  
  634.   aStarSearch(grid, src, dest);
  635.  
  636.   return (0);
  637. }

限制：尽管A*搜索算法是目前最好的路径搜索算法，但它并不总是能够产生最短路径，因为它在计算h值时严重依赖启发式/近似方法。

05 应用

这是A*搜索算法最有趣的部分。它们被用在游戏中！但是如何使用呢？

你玩过塔防游戏吗？

塔防是一种策略类视频游戏，目标是通过阻挡敌人的攻击来保卫玩家的领土或财产，通常是通过在敌人的攻击路径上或沿着其攻击路径上放置防御结构来实现的。

A*搜索算法经常用于找到从一个点到另一个点的最短路径。你可以为每个敌人使用它来找到通向目标的路径。

其中一个例子是非常流行的游戏《魔兽争霸III》。

5.1 如果搜索空间不是一个网格而是一个图，该怎么办？

相同的规则也适用于图。选择网格作为例子是为了简单理解。因此，我们可以使用A*搜索算法在图中找到源节点和目标节点之间的最短路径，就像我们在二维网格中做的那样。

5.2 时间复杂度

考虑到图，我们可能需要遍历所有的边才能从源节点到达目标节点（例如，考虑一个图，源节点和目标节点之间通过一系列边连接，如0（源）->1->2->3（目标））。

因此，最坏情况下的时间复杂度是O(E)，其中E是图中的边数。

辅助空间 在最坏的情况下，我们可能需要将所有的边存储在开放列表中，因此最坏情况下所需的辅助空间是O(V)，其中V是顶点的总数。

06 总结

那么何时使用广度优先搜索（BFS）而不是A*算法，何时使用Dijkstra算法而不是A*算法来寻找最短路径呢？

我们可以总结如下：

1）一个起点和一个目的地：

· 使用A*搜索算法（适用于无权图和加权图）。

2）一个起点，多个目的地：

· 对于无权图：使用广度优先搜索（BFS）。

· 对于非负权值的加权图：使用Dijkstra算法。

· 对于带有负权值的加权图：使用Bellman Ford算法。

3）任意两个节点之间的最短路径：

· 使用Floyd-Warshall算法。

· 使用Johnson算法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/683030
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号