下载文档原格式
实验四 A*算法实验II
一、实验目的：
熟悉和掌握A*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。
二、实验原理：
A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。
如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
三、实验内容：
1、参考实验系统给出的迷宫求解核心代码，观察求解过程与思路。
2、画出用A*算法求解迷宫最短路径的流程图。
3、尝试改变启发式算法提高迷宫搜索速度。
4、分析不同启发式函数对迷宫寻路速度的提升效果。
四、实验报告要求：
1、画出A*算法求解迷宫最短路径问题的流程图。
2、试分析不同启发式函数对迷宫寻路求解的速度提升效果。
3、分析启发式函数中g(n)和h(n)求解方法不同对A*算法的影响。
ai关于迷宫问题求解的文献迷宫求解是人工智能领域最基本的搜索算法，用于解决复杂状况下的最优化问题，可以应用于机器人路径求解，自然语言处理，控制理论，智能推理等。
随着人工智能的发展，求解迷宫的方法也越来越多样化，其中一种最广泛应用的是AI技术。
AI迷宫求解方法主要通过深度学习和机器学习的技术来解决迷宫的问题，深度学习是一种利用多层非线性神经网络来实现计算机对数据进行可靠性解释的技术。
它可以快速分析迷宫图形，找到最优路径，并最终解决迷宫问题。
机器学习是一种探索数据不断提高神经网络性能的技术，它可以分析迷宫图形，并从中学习规律。
有关AI迷宫求解的文献已有不少，其中比较具有代表性的是Rosenblatt“机器网络学习的一种技术”（1959年），Hammer“机器学习迷宫求解”（1973年），Ward“利用机器学习解决迷宫问题”（1986年），Ushimaya“深度学习迷宫求解”（1996年），Gray“人工智能算法与迷宫求解”（1997年）。
Rosenblatt的研究是最早的，他研究了如何使用机器学习方法来求解迷宫问题，他提出了一种简单的机器学习算法。
Hammer的研究通过分析迷宫轨迹，从而构建一个有效的解决迷宫的机器学习模型，他还研究了可以用来搜索最佳路径的坐标系统。
Ward在此基础上提出了一种机器学习算法，主要通过学习识别迷宫模型，从而解决迷宫问题。
Ushimaya开发了一种深度神经网络，它可以分析大量迷宫图形，帮助机器学习解决迷宫问题。
Gray提出了一种用于解决迷宫问题的人工智能算法，它可以实现自主导航，搜索最优解，并在多种场景环境中解决迷宫问题。
AI对迷宫求解的应用不仅解决了传统的解决迷宫的方法的局限性，而且具有较高的灵活性和可扩展性，可以为人工智能在多个领域的应用提供帮助。
AI迷宫求解的研究和发展不断在深化，新的算法也在不断发展和完善，以更好地适应不断变化的迷宫难题。
相比于传统的AI算法，AI强化学习技术更加适合复杂迷宫问题，可以提高机器学习算法的性能，解决各种复杂的状况。
第1篇一、实验背景迷宫探路系统是一个经典的计算机科学问题，它涉及到算法设计、数据结构以及问题求解等多个方面。
本实验旨在通过设计和实现一个迷宫探路系统，让学生熟悉并掌握迷宫问题的求解方法，提高算法实现能力。
二、实验目的1. 理解迷宫问题的基本概念和求解方法。
2. 掌握深度优先搜索（DFS）和广度优先搜索（BFS）算法的原理和实现。
3. 了解A搜索算法的基本原理，并能够实现该算法解决迷宫问题。
4. 学会使用数据结构如栈、队列等来辅助迷宫问题的求解。
三、实验原理迷宫问题可以通过多种算法来解决，以下为三种常用的算法：1. 深度优先搜索（DFS）：DFS算法通过递归的方式，沿着一条路径深入搜索，直到遇到死胡同，然后回溯并尝试新的路径。
DFS算法适用于迷宫的深度较深，宽度较窄的情况。
2. 广度优先搜索（BFS）：BFS算法通过队列实现，每次从队列中取出一个节点，然后将其所有未访问过的邻接节点加入队列。
BFS算法适用于迷宫的宽度较宽，深度较浅的情况。
3. A搜索算法：A算法结合了DFS和BFS的优点，通过估价函数f(n) = g(n) +h(n)来评估每个节点的优先级，其中g(n)是从起始点到当前节点的实际代价，h(n)是从当前节点到目标节点的预估代价。
A算法通常能够找到最短路径。
四、实验内容1. 迷宫表示：使用二维数组表示迷宫，其中0表示通路，1表示障碍。
2. DFS算法实现：- 使用栈来存储路径。
- 访问每个节点，将其标记为已访问。
- 如果访问到出口，输出路径。
- 如果未访问到出口，回溯到上一个节点，并尝试新的路径。
3. BFS算法实现：- 使用队列来存储待访问的节点。
- 按顺序访问队列中的节点，将其标记为已访问。
- 将其所有未访问过的邻接节点加入队列。
- 如果访问到出口，输出路径。
4. A算法实现：- 使用优先队列来存储待访问的节点，按照f(n)的值进行排序。
- 访问优先队列中的节点，将其标记为已访问。
北京科技大学实验报告学院：自动化学院专业：智能科学学技术班级：姓名：学号：实验日期：2017年11月6日实验名称：人工智能电脑鼠搜迷宫实验实验目的：掌握电脑鼠的基本操作及智能搜索算法操作。
实验仪器：KEIL MDK、电脑鼠、J-Link、VS实验原理：所谓“电脑鼠”，英文名叫做Micromouse，是一种具有人工智能的轮式机器人，是由嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称。
当电脑鼠放入起点，按下启动键之后，他就必须自行决定搜索法则并且在迷宫中前进，转弯，记忆迷宫墙壁资料，计算最短路径，搜索终点等功能。
电脑鼠更结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。
本实验中，通过红外传感器检测电脑鼠所处位置状态，通过智能算法保存地图并实现地图的搜索，通过pid等控制算法控制电机，达到电脑鼠搜索迷宫并计算最短路径等功能。
实验内容与步骤：实验内容1）KEIL MDK的安装2）电脑鼠硬件的检查及调整3）智能搜索算法的编写4）算法的调试与优化5）实验结果实验步骤（一）KEIL MDK的安装1双击运行Ke i l MDK 4.12 安装程序，出现软件安装界面，如图所示：2点击Next，勾选安装协议；3选择安装路径，建议安装在C 盘，运行速度快些4 填入用户信息，个人用户随意填入即可；点击Next 就进入实质的安装过程了，Wait for a Whle…5点击Finish，Keil MDK 就完成安装了，可以发现桌面上生成了名为“Keil uVis ion4”的可执行文件快捷方式。
（二）检查和调整电脑鼠的硬件1.电机检查：在电脑鼠程序文件中找到Motor.c文件，直接为两侧电机赋相同的速度值，用G-link连接电脑鼠和电脑，传入程序，打开电脑鼠放在地面上，如果电脑鼠能正常直线行进，即证明两侧电机正常工作。
如果有电机有问题，拆下原来的电机换新的再次进行电机检查即可。
2.传感器检查：用G-link连接电脑鼠和电脑，打开传感器查询模式，用手逐渐靠近每一个传感器，如果相应的传感器值由小变大，那么此传感器工作正常。
机器人路径规划算法机器人路径规划算法是指通过特定的计算方法，使机器人能够在给定的环境中找到最佳的路径，并实现有效的移动。
这是机器人技术中非常关键的一部分，对于保证机器人的安全和高效执行任务具有重要意义。
本文将介绍几种常见的机器人路径规划算法，并对其原理和应用进行探讨。
一、迷宫走迷宫算法迷宫走迷宫算法是一种基本的路径规划算法，它常被用于处理简单的二维迷宫问题。
该算法通过在迷宫中搜索，寻找到从起点到终点的最短路径。
其基本思想是采用图的遍历算法，如深度优先搜索（DFS）或广度优先搜索（BFS）等。
通过递归或队列等数据结构的应用，寻找到路径的同时保证了搜索的效率。
二、A*算法A*算法是一种启发式搜索算法，广泛应用于机器人路径规划中。
该算法通过评估每个节点的代价函数来寻找最佳路径，其中包括从起点到当前节点的实际代价（表示为g(n)）和从当前节点到目标节点的估计代价（表示为h(n)）。
在搜索过程中，A*算法综合考虑了这两个代价，选择总代价最小的节点进行扩展搜索，直到找到终点。
三、Dijkstra算法Dijkstra算法是一种最短路径算法，常用于有向或无向加权图的路径规划。
在机器人路径规划中，该算法可以用来解决从起点到目标点的最短路径问题。
Dijkstra算法的基本思想是，通过计算起点到每个节点的实际代价，并逐步扩展搜索，直到找到目标节点，同时记录下到达每个节点的最佳路径。
四、RRT算法RRT（Rapidly-exploring Random Tree）是一种适用于高维空间下的快速探索算法，常用于机器人路径规划中的避障问题。
RRT算法通过随机生成节点，并根据一定的规则连接节点，逐步生成一棵树结构，直到完成路径搜索。
该算法具有较强的鲁棒性和快速性，适用于复杂环境下的路径规划。
以上介绍了几种常见的机器人路径规划算法，它们在不同的场景和问题中具有广泛的应用。
在实际应用中，需要根据具体的环境和需求选择合适的算法，并对其进行适当的改进和优化，以实现更好的路径规划效果。
一、问题描述迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。
图1.1 迷宫示意图二、设计原理图1.1为一简单迷宫示意图的平面坐标表示。
以平面坐标图来表示迷宫的通路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为｛(x, y) | 1≤x, y ≤ 4 ｝，则迷宫问题归结为求解从(1, 1) 到 (4, 4)的最短路径。
迷宫走法规定为向东、南、西、北前进一步，由此可得规则集简化形式如下。
右移 R1：if(x, y) then (x+1, y) 如果当前在(x, y)点，则向右移动一步下移 R2：if(x, y) then (x,y -1) 如果当前在(x, y)点，则向下移动一步左移 R1: if(x, y) then (x -1,y) 如果当前在(x, y)点，则向左移动一步上移 R2：if(x, y) then (x, y+1) 如果当前在(x, y)点，则向上移动一步给出其状态空间如图2.1所示为求得最佳路径，可使用A*算法。
A*算法f 函数定义 f(n) ＝ g(n) ＋h(n)设：每一步的耗散值为1（单位耗散值）定义：g(n) ＝d(n) 从初始节点s到当前节点n的搜索深度h(n) ＝| Xg －Xn| ＋ | Yg－Yn| 当前节点n与目标节点间的坐标距离其中：( Xg , Yg) 目标节点g坐标( Xn, Yn)当前节点n坐标显然满足：h(n) ≤h*(n)OPEN表节点排序⑴ 按照f 值升序排列⑵ 如果f 值相同，则深度优先A*算法的搜索过程如下：1、OPEN＝(s)， f(s)=g(s)+h(s)2、LOOP：if OPEN＝( ) then EXIT(FAIL)3、n ← FIRST(OPEN)4、if GOAL(n) THEN EXIT(SUCCESS)5、REMOVE(n,OPEN)，ADD(n,CLOSED)6、{mi﹜← EXPAND(n)①计算f(n,mi )=g(n,mi)+h(mi)，(自s过n，mi到目标节点的耗散值)② ADD(mj ,OPEN)，标记mj到n的指针(mj不在OPEN和CLOSED中)③ if f(n,mk ) ＜ f(mk) then f(mk) ← f(n,mk)，标记mk到n的指针(mk在 OPEN中)④ if f(n,ml ) ＜ f(ml) then f(ml) ← f(n,ml)，标记ml到n的指针(ml在CLOSED中)ADD(ml ,OPEN)，把ml放回到OPEN中7、OPEN中的节点按照f值升序排列8、GO LOOPA*算法的搜索图示如图2.2所示。
则其搜索结果如图2.3所示。
图2.3 迷宫搜索结果示意图三、详细设计（1）数据结构设计①为了在程序中表示迷宫图，定义了一个6*6的二维整型数组int Maze[7][7]={{3,1,3,1,3,0,3},{0,4,1,4,1,4,1},{3,1,3,0,3,1,3},{1,4,1,4,1,4,1},{3,0,3,1,3,0,3},{1,4,1,4,1,4,1},{3,0,3,1,3,1,3}};其中数字3代表坐标点，1代表两个坐标点之间存在路径，0代表两个坐标点之间不存在路径，数字4没有意义。
从这个二维整型数组抽象出来的迷宫如下所示：②每个坐标点的数据结构如下:struct Data{int x;int y;int g;int f;struct Data *parent;};其中x代表数组的第几行对应实际坐标的y值，y代表数组的第几列对应实际坐标的x值，g代表从入口到该坐标点的耗散值，f代表代表评价函数值，parent代表路径上的该坐标点的前一个坐标点。
③程序中对应入口坐标为（6，0）也就是实际中的入口（1,1），实际中每走一步对应程序中是x+2或x-2或y+2或y-2。
程序中对应的出口坐标为（0,6）实际对应着出口（4,4）。
④实际中的h函数对应程序中的h(n) ＝|x－0|/2＋| y－6 |/2。
⑤因为实际坐标与程序中坐标不对应，所以需要一个转换公式，如下:实际坐标的x值等于程序中坐标点的y值除以2再加1实际坐标的y值等于5减去程序中坐标点的x值除以2再减1⑥判断两个坐标点a,b之间是否存在路径：p=(a->x+b->x)/2;q=(a->y+b->y)/2;如果Maze[p][q]==1,则说明a，b之间存在路径，Maze[p][q]==0，则说明不存在路径。
为了将搜索结果图形输出，则又设置了Maze[p][q]==5，代表“←”, Maze[p][q]==6，代表“→”，Maze[p][q]==7，代表“↑”，Maze[p][q]==8，代表“↓”。
⑦为了满足open表中节点如果f 值相同，则深度优先，使用一个栈来表示open表，closed表也是用一个栈来表示。
（2）函数说明bool bound(Data *a)函数功能:判断一个坐标点是否越过边界，返回值bool值int h(Data *a)函数功能:h函数Data* Nopen(Data *a)函数功能:在open表中搜索结点a.若找到则返回结点a的地址，否则返回0Data* Nclosed(Data *a)函数功能:在closed表中搜索结点a.若找到则返回结点a的地址，否则返回0void sort()函数功能:对open表中节点按照f值升序排列void Expand(Data *a)函数功能:扩展当前结点avoidprintmaze()函数功能:输出迷宫void printpath(Data *a)函数功能:输出搜索结果int A()函数功能: A*算法void main()函数功能:主函数（3）详细程序设计#include<iostream>#include<stack>using namespace std;int Maze[7][7]={{3,1,3,1,3,0,3},{0,4,1,4,1,4,1},{3,1,3,0,3,1,3},{1,4,1,4,1,4,1},{3,0,3,1,3,0,3},{1,4,1,4,1,4,1},{3,0,3,1,3,1,3}};//3代表节点，1代表两个节点之间有线，0代表两个节点之间没有线，4无意义struct Data{int x;int y;int g;int f;struct Data *parent;};//坐标点结构体stack<Data *> open; //open表stack<Data *> closed; //close表bool bound(Data *a) //边界函数{return (a->x<=6)&&(a->x>=0)&&(a->y<=6)&&(a->y>=0);}int h(Data *a) //h函数{return abs((a->x-0)/2)+abs((a->y-6)/2);}Data* Nopen(Data *a)//在open表搜索a坐标点{Data *b,*d;stack<Data *> c;while(!open.empty()){b=open.top();if(b->x==a->x&&b->y==a->y){while(!c.empty()){d=c.top();c.pop();open.push(d);}return b;}open.pop();c.push(b);}while(!c.empty()){d=c.top();c.pop();open.push(d);}return 0;}Data* Nclosed(Data *a)在closed表搜索a坐标点{Data *b,*d;stack<Data *> c;while(!closed.empty()){b=closed.top();if(b->x==a->x&&b->y==a->y){while(!c.empty()){d=c.top();c.pop();closed.push(d);}return b;}closed.pop();c.push(b);}while(!c.empty()){d=c.top();c.pop();closed.push(d);}return 0;}void sort() 对open表中坐标点排序{Data *p,*q,*r;stack<Data *> c;int b=open.size();for(inti=0;i<b;i++){p=open.top();open.pop();for(int j=i+1;j<b;j++){q=open.top();open.pop();if(q->f<p->f){r=p;p=q;q=r;}open.push(q);}c.push(p);}while(!c.empty()){q=c.top();c.pop();open.push(q);}}void Expand(Data *a)//扩展a坐标点{intp,q;Data *d;struct Data *b[4];for(inti=0;i<4;i++)b[i]=(struct Data*)malloc(sizeof(Data));b[0]->x=a->x+2;b[0]->y=a->y;b[1]->x=a->x;b[1]->y=a->y-2;b[2]->x=a->x-2;b[2]->y=a->y;b[3]->x=a->x;b[3]->y=a->y+2;for(i=0;i<4;i++){if(bound(b[i])){p=(b[i]->x+a->x)/2;q=(b[i]->y+a->y)/2;if(Maze[p][q]==1){if(Nopen(b[i])==0&&Nclosed(b[i])==0){b[i]->g=a->g+1;b[i]->f=b[i]->g+h(b[i]);b[i]->parent=a;open.push(b[i]);}else if(Nopen(b[i])){d=Nopen(b[i]);if(a->g+1<d->g){d->g=a->g+1;d->f=b[i]->g+h(b[i]);d->parent=a;}}else if(Nclosed(b[i])){if(a->g+1<b[i]->g){b[i]->g=a->g+1;b[i]->f=b[i]->g+h(b[i]);b[i]->parent=a;open.push(b[i]);}}}}}}void printmaze() //输出迷宫{cout<<" (4,4) "<<endl; for(inti=0;i<7;i++){if(i==6)cout<<"入口→";elsecout<<" ";if(i%2==0){for(int j=0;j<7;j++){if(Maze[i][j]==3)cout<<"●";else if(Maze[i][j]==1)cout<<"─";else if(Maze[i][j]==5)cout<<"←";else if(Maze[i][j]==6)cout<<"→";elsecout<<" ";}if(i==0)cout<<"→出口";cout<<endl;}else{for(int j=0;j<7;j++){if(Maze[i][j]==1)cout<<"│";else if(Maze[i][j]==7)cout<<"↑";else if(Maze[i][j]==8)cout<<"↓";elsecout<<" ";}cout<<endl;}}cout<<" (1,1)"<<endl<<endl;}void printpath(Data *a)//输出搜索结果{intb,c;stack<Data *> q;while(!a->parent==NULL){q.push(a);b=(a->parent->x+a->x)/2;c=(a->parent->y+a->y)/2;if(a->parent->x==a->x){if(a->parent->y>a->y)Maze[b][c]=5;elseMaze[b][c]=6;}else{if(a->parent->x>a->x)Maze[b][c]=7;elseMaze[b][c]=8;}a=a->parent;}q.push(a);while(!q.empty()){cout<<"("<<q.top()->y/2+1<<","<<5-(q.top()->x/2+1)<<") ";q.pop();}cout<<endl<<endl;printmaze();}int A() //A*算法{Data s={6,0,0,0,NULL};Data *n=&s;open.push(n);while(1){if(open.empty()){cout<<"不存在路径!"<<endl;return 0;}else{n=open.top();if(n->x==0&&n->y==6){cout<<"最短路径长度为:"<<n->f<<endl<<endl;cout<<"最短路径为:";printpath(n);return 1;}else{open.pop();closed.push(n);Expand(n); //扩展n节点sort(); //open中节点按照f值升序排列}}}}void main()//主函数{cout<<"迷宫如下图:"<<endl;printmaze();A();}四、设计结果及分析（1）实验结果（2）实验分析从上面的图中可以看出程序运行结果与分析结果一致，程序运行正确。
