当前位置:   article > 正文

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

路径搜索与遍历算法

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

限制:尽管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
推荐阅读
相关标签
  

闽ICP备14008679号