A算法ppt课件
- 格式:ppt
- 大小:330.00 KB
- 文档页数:44
只是用一个二维状态数组,结果迂回搜索导致超时./showproblem.php?pid=4198Quick out of the HarbourProblem Description题目原文是英文的,而且比较繁琐。
我修饰转述如下:小强被海盗抓到了,海盗把他和他的船“小强号”关在一个水狱里。
小强拿到了小红给他的一张水狱地图,地图由h行w列字符组成(3 <= h;w <= 500), ,字符共有四种:S:小强和他的“小强号”的起始位置,他要从这里逃跑。
#:不能逾越的石墙. :水道,小强号可以直接通过@:栅栏水道已知:小强打开栅栏需要d分钟 (0 <= d <= 50);小强号通过单位水道的时间为1分钟;水狱一定有出口。
输入:t (一共有t组测试数据)h w d 以及水狱地图 (每组测试数据输入一次)输出:小强出狱的最短时间(和路线)。
Sample Input26 5 7######S..##@#.##...##@####.###4 5 3######S#.##@..####@#Sample Output1611分析:从S点开始,广度优先搜索,寻找出口。
由于有栅栏,不能保证搜索的当前结点是“耗时最少”的优先搜索,对当前结点耗时v取权重,采用优先队列。
code:(普通广度搜索,超时)#include<iostream>#include<queue>using namespace std;#define N 501#define big 999999999int h,w,d,sx,sy,t,i,j;int tv[N][N];char maze[N][N];int offset[4][2]={{-1,0},{0,-1},{1,0},{0,1}};struct pos{int x;int y;};int bfs(){int mymin=big;pos start,temp,temp1;start.x=sx,start.y=sy;tv[sx][sy]=0;queue<pos> q;q.push(start);while(!q.empty()){temp=q.front();q.pop();if(temp.x==0||temp.x==h-1||temp.y==0||temp.y==w-1)if(mymin>tv[temp.x][temp.y]+1)mymin=tv[temp.x][temp.y]+1;printf("path: %d %d %c\n",temp.x,temp.y,maze[temp.x][temp.y]);for(i=0;i<4;i++){pos temp1;temp1.x=temp.x+offset[i][0];temp1.y=temp.y+offset[i][1];if(temp1.x<0||temp1.x>=h||temp1.y<0||temp1.y>=w)continue;if(maze[temp1.x][temp1.y]=='.')if(tv[temp1.x][temp1.y]>tv[temp.x][temp.y]+1){tv[temp1.x][temp1.y]=tv[temp.x][temp.y]+1;q.push(temp1);}if(maze[temp1.x][temp1.y]=='@')if(tv[temp1.x][temp1.y]>tv[temp.x][temp.y]+d+1){tv[temp1.x][temp1.y]=tv[temp.x][temp.y]+1+d;q.push(tem p1);}}}return mymin;}int main(){cin>>t;while(t--){cin>>h>>w>>d;getchar();for(i=0;i<h;i++){for(j=0;j<w;j++){scanf("%c",&maze[i][j]);//cin>>maze[i][j];tv[i][j]=big;if(maze[i][j]=='S'){sx=i;sy=j;}}getchar();}printf("%d\n",bfs());//cout<<bfs()<<endl;}}code:改用优先队列,以到达该结点的时间v为权重,每次使v最小的结点出队,即所谓“A算法”#include<iostream>#include<queue>using namespace std;#define N 501int h,w,d,sx,sy,t,i,j;bool used[N][N];char maze[N][N];int offset[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//方向数组struct pos{int x;int y;int v;};struct cmp//这样之后出队序列就是由小到大,搜索结点时优先搜索v(从S到当前结点耗费的时间)小的结点。
a星算法原理1. 基本思路A* 算法是基于图模型的搜索算法,其中图由若干个节点和连接这些节点的边组成。
搜索的目标是在图上寻找一条从起点到终点的最优路径。
A* 算法的基本思路如下:(1)首先将起点加入open列表(即待搜索的节点列表),定义一个空的close列表(即已搜索的节点列表)。
(2)从open列表中取出F值最小的节点,将其加入close列表。
(3)若该节点为终点,则搜索完成,否则将它的相邻节点加入open列表。
(4)对于所有加入open列表的节点,计算它们的F值,并更新它们的父节点。
(5)重复步骤2-4,直到open列表为空或者找到终点。
F值由G值和H值组成:F =G + HG值表示从起点到该节点的实际代价,H值表示从该节点到终点的启发式估价(即一个估计值,不一定是实际值,但必须保证不小于实际值)。
1.启发式估价函数必须保证不小于实际代价。
2.启发式估价函数应该尽量接近实际代价,否则会影响搜索效率。
3.启发式估价函数不能产生死循环或者走回头路的情况。
2. 估价函数的选取(1)曼哈顿距离曼哈顿距离指两点之间横纵坐标差的绝对值之和。
曼哈顿距离是一种比较简单的启发式估价函数,它适用于只能沿水平或竖直方向移动的情况。
曼哈顿距离在斜着走的时候有一定的误差,不够精确。
(2)欧几里得距离欧几里得距离指两点之间的直线距离。
欧几里得距离是一种比较精确的启发式估价函数,它适用于可以在任何方向上移动的情况。
欧几里得距离会导致算法不够稳定,容易出现死循环的情况。
(3)切比雪夫距离(4)自定义估价函数如果以上的估价函数不能满足需要,还可以根据具体需求自定义估价函数。
自定义估价函数要满足启发式估价函数的基本要求,并且尽量简单易实现。
3. A*算法的优缺点(1)A*算法具有较高的搜索效率,并且能够找到最优解。
(2)A*算法能够通过启发式估价函数优化搜索路径,从而减少搜索量。
(1)A*算法的搜索效率和搜索结果非常依赖于所选择的估价函数,不同的估价函数可能产生完全不同的搜索结果。