• A* 算法实现与解析

    【算法分析】
    A*算法适用于    结点特别多的场景，常借助于优先队列 priority_queue 实现。
    在A*算法的实现中，形如下方的代码，为“    结构体内嵌比较函数”。之所以这样写，是因为其执行速度快。
    bool operator<(const NODE &a) const {
        return F==a.F?G>a.G:F>a.F;
    }

    下面算法代码执行后，将输出一条如下图所示的绿色最短路径。


     

    A*算法的经典解析可参见：
    https://cloud.tencent.com/developer/article/2040931
    https://blog.csdn.net/m0_46304383/article/details/113457800
    https://blog.csdn.net/dujuancao11/article/details/109749219
    https://www.acwing.com/blog/content/352/
    https://blog.csdn.net/qq_43827595/article/details/99546055


    【算法代码】
    下面代码改编自：https://blog.csdn.net/m0_46304383/article/details/113457800

    1. #include 
    2. using namespace std;
    3.  
    4. const int N=10; //Map order
    5. bool close[N][N]; //Access records, close lists
    6. int valueF[N][N]; //Record the F value of each node
    7. int pre[N][N][2]; //Stores the parent node of each node
    8.  
    9. int env[N][N]= { //Scene Map
    10. 	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    11. 	{0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
    12. 	{0, 0, 1, 1, 0, 0, 0, 1, 0, 0},
    13. 	{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
    14. 	{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
    15. 	{0, 0, 1, 1, 0, 1, 0, 0, 0, 0},
    16. 	{0, 0, 1, 0, 1, 0, 1, 0, 0, 0},
    17. 	{0, 0, 1, 0, 0, 0, 0, 1, 0, 0},
    18. 	{0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
    19. 	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    20. };
    21.  
    22. struct NODE {
    23. 	int x,y;   //Node location
    24. 	int F,G,H; //F=G+H
    25. 	NODE(int a, int b) { //constructor function
    26. 		x=a,y=b;
    27. 	}
    28. 	//struct's nested comparison function,speed is faster.
    29. 	bool operator<(const NODE &a) const {
    30. 		return F==a.F?G>a.G:F>a.F;
    31. 	}
    32. };
    33.  
    34. //define the direction
    35. //const int ne_pos[8][2]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
    36. const int ne_pos[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
    37. priority_queue open;
    38.  
    39. int Manhattan(int x0,int y0,int x1,int y1) {
    40. 	return (abs(x0-x1)+abs(y0-y1));
    41. }
    42.  
    43. bool isValidNode(int x,int y,int u,int v) {
    44. 	if(x<0||x>=N||y<0||y>=N) return false; //Judge boundary
    45. 	if(env[x][y]==1) return false; //Judge obstacle
    46. 	/*When two nodes are diagonal and
    47. 	their common adjacent nodes have obstacles, return false.
    48. 	The rule is used when the scene map has 8 directions.*/
    49. 	if(x!=u && y!=v && (env[x][v]==1 || env[u][y]==1)) return false;
    50. 	return true;
    51. }
    52.  
    53. void Astar(int x0,int y0,int x1,int y1) {
    54. 	NODE node(x0,y0); //Starting point is added into the open list.
    55. 	node.G=0;
    56. 	node.H=Manhattan(x0,y0,x1,y1);
    57. 	node.F=node.G+node.H;
    58. 	valueF[x0][y0]=node.F;
    59. 	open.push(node);
    60.  
    61. 	while(!open.empty()) {
    62. 		/*Take the head element of priority queue,
    63. 		which is the point with the least cost in the surrounding cells*/
    64. 		NODE cur_node=open.top();
    65. 		open.pop(); //Remove from the open list
    66. 		//Access this point and add it to the close list
    67. 		close[cur_node.x][cur_node.y]=true;
    68. 		if(cur_node.x==x1 && cur_node.y==y1) break; //Reach the finish line
    69.  
    70. 		/*Traverse the four directions around the top_node,
    71. 		or if the array ne_pos has eight values,
    72. 		then you need to traverse the eight directions around the top_node.
    73. 		*/
    74. 		for(int i=0; i<4; i++) {
    75. 			//Create a point around top_node
    76. 			NODE ne_node(cur_node.x+ne_pos[i][0],cur_node.y+ne_pos[i][1]);
    77. 			//The node coordinate is valid and has not been accessed
    78. 			if(isValidNode(ne_node.x,ne_node.y,cur_node.x,cur_node.y) && !close[ne_node.x][ne_node.y]) {
    79. 				/*Calculate the cost to reach the node
    80. 				from the starting point and through the top_node node*/
    81. 				ne_node.G=cur_node.G+int(sqrt(pow(ne_pos[i][0],2)+pow(ne_pos[i][1],2)));
    82. 				//Calculate the Manhattan distance from the node to the destination
    83. 				ne_node.H=Manhattan(ne_node.x,ne_node.y,x1,y1);
    84. 				/*The estimated cost to reach the destination
    85. 				 from the starting point through the top_node
    86. 				 and the current node*/
    87. 				ne_node.F=ne_node.G+ne_node.H;
    88.  
    89. 				/*ne_node.F
    90. 				  When the condition is met, a better path is found and updated.
    91. 				  valueF[ne_node.x][ne_node.y]==0,
    92. 				  When the condition is met, the node is not added to the OPEN table,
    93. 				  it is needed to be added to the open table*/
    94. 				if(ne_node.F0) {
    95. 					//Save the parent node of the node
    96. 					pre[ne_node.x][ne_node.y][0]=cur_node.x;
    97. 					pre[ne_node.x][ne_node.y][1]=cur_node.y;
    98. 					//Modify the valueF value of the node
    99. 					valueF[ne_node.x][ne_node.y]=ne_node.F;
    100. 					open.push(ne_node);
    101. 				}
    102. 			}
    103. 		}
    104. 	}
    105. }
    106.  
    107. void PrintPath(int x1,int y1) {
    108. 	if(pre[x1][y1][0]==-1 || pre[x1][y1][1]==-1) {
    109. 		printf("No path to get.\n");
    110. 		return;
    111. 	}
    112. 	int x=x1,y=y1;
    113. 	int a,b;
    114. 	while(x!=-1 || y!=-1) {
    115. 		env[x][y]=2; //Assign a value of 2 to the node on the feasible path
    116. 		a=pre[x][y][0];
    117. 		b=pre[x][y][1];
    118. 		x=a;
    119. 		y=b;
    120. 	}
    121.  
    122. 	/*
    123. 	"  " represents an unpassed node,
    124. 	" #" represents an obstacle,
    125. 	" @" represents a feasible node.
    126. 	*/
    127. 	string s[3]= {"  "," #", " @"};
    128. 	for(int i=0; i
    129. 		for(int j=0; j
    130. 			cout<//s[] is string, must use cout to output
    131. 		}
    132. 		cout<
    133. 	}
    134. }
    135.  
    136. int main(){
    137. 	memset(close,false,sizeof close); //Initialize close array to false
    138. 	memset(valueF,0,sizeof valueF); //Initialize F to 0
    139. 	memset(pre,-1,sizeof pre); //Initialize pre array to -1
    140.  
    141. 	int x0=2,y0=4; //start point
    142. 	int x1=8,y1=6; //end point
    143.  
    144. 	if(!isValidNode(x0,y0,x0,y0)){
    145. 		printf("Invalid input.\n");
    146. 		return 0;
    147. 	}
    148.  
    149. 	Astar(x0,y0,x1,y1); //A* algorithm
    150. 	PrintPath(x1,y1); //Print the path
    151.  
    152. 	return 0;
    153. }
    154.  
    155.  
    156. /*
    157. output:
    158.              @ @ @
    159.    #         @ # @
    160.      # # @ @ @ # @
    161.        #       # @
    162.              #   @
    163.      # #   #     @
    164.      #   #   #   @
    165.      #         # @
    166.    #   #     @ @ @
    167. */


    【未加注释的算法代码】
    鉴于上面代码注释过多，为方便大家快速阅读代码，下面给出的是未加注释版本的算法代码。

    1. #include 
    2. using namespace std;
    3.  
    4. const int N=10;
    5. bool close[N][N];
    6. int valueF[N][N];
    7. int pre[N][N][2];
    8.  
    9. int env[N][N]= {
    10. 	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    11. 	{0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
    12. 	{0, 0, 1, 1, 0, 0, 0, 1, 0, 0},
    13. 	{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
    14. 	{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
    15. 	{0, 0, 1, 1, 0, 1, 0, 0, 0, 0},
    16. 	{0, 0, 1, 0, 1, 0, 1, 0, 0, 0},
    17. 	{0, 0, 1, 0, 0, 0, 0, 1, 0, 0},
    18. 	{0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
    19. 	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    20. };
    21.  
    22. struct NODE {
    23. 	int x,y;
    24. 	int F,G,H;
    25. 	NODE(int a, int b) {
    26. 		x=a,y=b;
    27. 	}
    28. 	bool operator<(const NODE &a) const {
    29. 		return F==a.F?G>a.G:F>a.F;
    30. 	}
    31. };
    32.  
    33. const int ne_pos[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
    34. priority_queue open;
    35.  
    36. int Manhattan(int x0,int y0,int x1,int y1) {
    37. 	return (abs(x0-x1)+abs(y0-y1));
    38. }
    39.  
    40. bool isValidNode(int x,int y,int u,int v) {
    41. 	if(x<0||x>=N||y<0||y>=N) return false;
    42. 	if(env[x][y]==1) return false;
    43. 	if(x!=u && y!=v && (env[x][v]==1 || env[u][y]==1)) return false;
    44. 	return true;
    45. }
    46.  
    47. void Astar(int x0,int y0,int x1,int y1) {
    48. 	NODE node(x0,y0);
    49. 	node.G=0;
    50. 	node.H=Manhattan(x0,y0,x1,y1);
    51. 	node.F=node.G+node.H;
    52. 	valueF[x0][y0]=node.F;
    53. 	open.push(node);
    54.  
    55. 	while(!open.empty()) {
    56. 		NODE cur_node=open.top();
    57. 		open.pop();
    58. 		close[cur_node.x][cur_node.y]=true;
    59. 		if(cur_node.x==x1 && cur_node.y==y1) break;
    60.  
    61. 		for(int i=0; i<4; i++) {
    62. 			NODE ne_node(cur_node.x+ne_pos[i][0],cur_node.y+ne_pos[i][1]);
    63. 			if(isValidNode(ne_node.x,ne_node.y,cur_node.x,cur_node.y) && !close[ne_node.x][ne_node.y]) {
    64. 				ne_node.G=cur_node.G+int(sqrt(pow(ne_pos[i][0],2)+pow(ne_pos[i][1],2)));
    65. 				ne_node.H=Manhattan(ne_node.x,ne_node.y,x1,y1);
    66. 				ne_node.F=ne_node.G+ne_node.H;
    67. 				if(ne_node.F0) {
    68. 					pre[ne_node.x][ne_node.y][0]=cur_node.x;
    69. 					pre[ne_node.x][ne_node.y][1]=cur_node.y;
    70. 					valueF[ne_node.x][ne_node.y]=ne_node.F;
    71. 					open.push(ne_node);
    72. 				}
    73. 			}
    74. 		}
    75. 	}
    76. }
    77.  
    78. void PrintPath(int x1,int y1) {
    79. 	if(pre[x1][y1][0]==-1 || pre[x1][y1][1]==-1) {
    80. 		printf("No path to get.\n");
    81. 		return;
    82. 	}
    83. 	int x=x1,y=y1;
    84. 	int a,b;
    85. 	while(x!=-1 || y!=-1) {
    86. 		env[x][y]=2;
    87. 		a=pre[x][y][0];
    88. 		b=pre[x][y][1];
    89. 		x=a;
    90. 		y=b;
    91. 	}
    92.  
    93. 	string s[3]= {"  "," #", " @"};
    94. 	for(int i=0; i
    95. 		for(int j=0; j
    96. 			cout<
    97. 		}
    98. 		cout<
    99. 	}
    100. }
    101.  
    102. int main() {
    103. 	memset(close,false,sizeof close);
    104. 	memset(valueF,0,sizeof valueF);
    105. 	memset(pre,-1,sizeof pre);
    106.  
    107. 	int x0=2,y0=4;
    108. 	int x1=8,y1=6;
    109. 	if(!isValidNode(x0,y0,x0,y0)) {
    110. 		printf("Invalid input.\n");
    111. 		return 0;
    112. 	}
    113.  
    114. 	Astar(x0,y0,x1,y1);
    115. 	PrintPath(x1,y1);
    116.  
    117. 	return 0;
    118. }
    119.  
    120.  
    121. /*
    122. output:
    123.              @ @ @
    124.    #         @ # @
    125.      # # @ @ @ # @
    126.        #       # @
    127.              #   @
    128.      # #   #     @
    129.      #   #   #   @
    130.      #         # @
    131.    #   #     @ @ @
    132. */



    【参考文献】
    https://cloud.tencent.com/developer/article/2040931
    https://blog.csdn.net/m0_46304383/article/details/113457800
    https://blog.csdn.net/dujuancao11/article/details/109749219
    https://www.acwing.com/blog/content/352/
    https://blog.csdn.net/qq_43827595/article/details/99546055

  • 相关阅读:
    java-php-python-ssm一起组局校园交友平台计算机毕业设计
    【泛微ecology】控制文本框输入汉字数量
    易点易动设备管理系统：提升企业备件管理和维修效率的智能解决方案
    Dubbo源码理解
    2024环境，资源与绿色能源国际会议(ICERGE2024)
    ffmpeg视频编码原理和实战-（4）H264原始码流分析
    BERT深度学习基准模型特点与应用
    顶象无感验证为十八数藏“加固城墙”
    双十一购物指南：电视盒子哪个牌子好？口碑电视盒子品牌排行榜
    【红日靶场】vulnstack1-完整渗透过程
  • 原文地址：https://blog.csdn.net/hnjzsyjyj/article/details/126693357