下载文档原格式
实验四 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算法通过随机生成节点，并根据一定的规则连接节点，逐步生成一棵树结构，直到完成路径搜索。
该算法具有较强的鲁棒性和快速性，适用于复杂环境下的路径规划。
以上介绍了几种常见的机器人路径规划算法，它们在不同的场景和问题中具有广泛的应用。
在实际应用中，需要根据具体的环境和需求选择合适的算法，并对其进行适当的改进和优化，以实现更好的路径规划效果。
A*算法解决迷宫问题算法思想：迷宫问题可以表述为：一个二维的网格，0表示点可走，1表示点不可以走，点用（x，y）表示，寻找从某一个给定的起始单元格出发，经由行相邻或列相邻的单元格(可以通过的)，最终可以到达目标单元格的、所走过的单元格序列。
在任一个单元格中，都只能看到与它邻近的4个单元格(如果位于底边，则只有3个；位于4个角上，则只有2个是否能通过)。
A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。
它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上的可能性的度量。
A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n）其中：n是搜索中遇到的任意状态。
g(n)是从起始状态到n的代价。
h(n)是对n到目标状态代价的启发式估计。
即评估函数f ( n) 是从初始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和。
这里我们定义n点到目标点的最小实际距离为h（n）*，A*算法要满足的条件为：h（n）<=h（n）*迷宫走的时候只能往上下左右走，每走一步，代价为1，这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离，即：h（n）=|end.x –n.x|+ |end.y –n.y|这里end表示迷宫的目标点，n表示当前点，很明显这里h（n）<=h（n）*。
g（n）容易表示，即每走一步的代价是1，所以利用f（n）=g（n）+h（n）这种策略，我们可以不断地逼近目标点，从而找到问题的解。
时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为O(m*n).结果演示：源码：#include <queue>#include <vector>#include <iostream>using namespace std;int direc[4][2]={{0,1},{-1,0},{0,-1},{1,0}};enum Flag{SEAL,OPEN,UNVISITED};typedef struct node{int _x,_y; //节点坐标(x,y)int _G; //实际已开销Gint _H; //探测将开销Hint _F; //优先级_F=_G+_H struct node *pre; //前驱顶点}Queue_Node;typedef struct{Flag flag;Queue_Node *point;}Seal;class A_Star{public://构造函数A_Star(){input();}~A_Star(){for(int i=1;i<=_len;++i){for(int j=1;j<=_wid;++j){if(_seal[i][j].point!=NULL){delete _seal[i][j].point;}}}for(i=0;i<=_len;++i){delete []_seal[i];delete []_maze[i];}delete []_seal;delete []_maze;}void input(){cout<<"输入: 迷宫左边长,上边宽! 例如：30 20"<<endl;cin>>_len>>_wid;_seal=new Seal*[_len+1];_maze=new unsigned char*[_len+1];for(int i=0;i<=_len;++i){_seal[i]=new Seal[_wid+1];_maze[i]=new unsigned char[_wid+1];}cout<<"从下一行开始输入迷宫信息："<<endl;for( i=1;i<=_len;++i){for(int j=1;j<=_wid;++j){cin>>_maze[i][j];_seal[i][j].flag=UNVISITED;_seal[i][j].point=NULL;}}cout<<"输入起点坐标,目标点坐标,例如:1 1 30 20"<<endl;cin>>_sx>>_sy>>_ex>>_ey;if(_maze[_sx][_sy]=='1'||_maze[_ex][_ey]=='1'||bound(_sx,_sy)==false||bound(_ex,_ey)==fal se){cout<<"不可能存在这样的情况！"<<endl;return;}cout<<"调用A*算法打印结果如下："<<endl;A();}//A*核心算法void A(){//源点放入开放列表Queue_Node *p_node=new Queue_Node;p_node->pre=NULL;p_node->_H=get_H(_sx,_sy);p_node->_G=0;p_node->_x=_sx;p_node->_y=_sy;p_node->_F=p_node->_H+p_node->_G;_open.push(p_node);_seal[_sx][_sy].flag=OPEN;_seal[_sx][_sy].point=p_node;while(!_open.empty()){p_node=_open.top();_open.pop();int x=p_node->_x;int y=p_node->_y;_seal[x][y].flag=SEAL;for(int i=0;i<4;++i){int tx=x+direc[i][0];int ty=y+direc[i][1];if(bound(tx,ty)==false||_maze[tx][ty]=='1'||_seal[tx][ty].flag==SEAL){continue;}if(_seal[tx][ty].flag==UNVISITED){if(tx==_ex&&ty==_ey){print(p_node);cout<<"("<<tx<<","<<ty<<")"<<endl;cout<<"总共走了:"<<p_node->_F<<"步"<<endl;return;}Queue_Node *temp=new Queue_Node;_seal[tx][ty].flag=OPEN;_seal[tx][ty].point=temp;temp->pre=p_node;temp->_G=p_node->_G+1;temp->_x=tx;temp->_y=ty;temp->_H=get_H(tx,ty);temp->_F=temp->_G+temp->_H;_open.push(temp);}else{Queue_Node *temp=_seal[tx][ty].point;if(p_node->_G+1<temp->_G){temp->_G=p_node->_G+1;temp->pre=p_node;temp->_F=temp->_G+temp->_H;}}}}cout<<"没有从("<<_sx<<","<<_sy<<")--->"<<"("<<_ex<<","<<_ey<<")的路径"<<endl;}//打印路径void print(Queue_Node *p){if(p==NULL){return;}print(p->pre);cout<<"("<<p->_x<<","<<p->_y<<"),";}bool bound(int x,int y){return (x<=_len)&&(x>=1)&&(y<=_wid)&&(y>=1);}int get_H(int x,int y){return ab(x-_ex)+ab(y-_ey);}int ab(int i){return i<0 ? -i:i;}private:struct cmp{bool operator()(Queue_Node *n1,Queue_Node *n2){return n1->_F>n2->_F;}};priority_queue<Queue_Node *,vector<Queue_Node *>,cmp> _open;//最小堆(开放列表) int _len,_wid;//迷宫左边长,上边宽int _sx,_sy,_ex,_ey;Seal **_seal;//动态开辟封闭列表unsigned char **_maze;//迷宫地图};int main(){A_Star test;return 0;}。
摘要人类科技的进步促使机器人技术的智能化水平越来越高。
可移动机器人的路径规划是机器人研究中的一个重要领域，得到越来越多研究者的关注，并取得了丰厚的成果。
行进方向选择问题是智能机器人控制的关键技术之一，可移动机器人如何在复杂和未知的环境中自主选择路线到达目标地点，并躲避障碍物，是其重要的判断条件之一，也是功能实现的基础。
迷宫机器人是一种基于ARM1138的具备人工智能的小型机器人，可在没有人工干预的情况下，在16×16未知的迷宫中自行完成一系列动作。
看似简单的小型机器人，其中却包含了光学、力学、信息科学等多种学科的综合应用，是对机器智能化的实现。
本设计从软件设计的角度对迷宫机器人的智能控制做了较有深度的探讨。
通过软件编程，实现迷宫机器人的智能控制，完成在16×16的迷宫中，由起点自动探索到终点并探测返回，随后完成冲刺的功能。
论文中讲述的重点是迷宫机器人在路径选择中逻辑方面的判断，以及墙壁信息的获取和车身的控制。
关键词:人工智能；迷宫机器人；软件目录1绪论 (1)课题的研究背景和发展历程 (1)课题研究的目的和意义 (1)课题研究的主要内容 (1)本章小结 (1)2系统的总体设计 (2)计 (2)单片机和开发工具的选择 (3)单片机的选择 (3)开发工具的选择 (4)本章小结 (5)3迷宫机器人的软件设计 (6)迷宫介绍 (6)构 (6)起点坐标确实立 (6)主要外设的软件设计 (7)红外传感器的软件控制 (7)步进电机的软件控制 (8)迷宫机器人的姿势矫正 (9)双板的身姿矫正 (10)单侧板的身姿矫正 (10)直角拐弯 (11)车身后转 (13)本章小结 (13)4控制方式的实现 (14)等高图的制作与偏移量的判断 (14)探索法则 (15)基本法则 (15)中心法则的改进 (17)4.3本章小结 (19)5总结与展望 (20)参考文献 (21)附录 (22)1绪论进入21世纪，伴随着电子、信息技术的发展与迅速普及，人们对电子技术的要求也越来越高，智能化、信息化的高尖技术逐步融入人们的日常生活。
自动走迷宫的机器人设计与课程总结报告一、引言随着人工智能和机器人技术的快速发展，自动走迷宫的机器人成为了研究的热点之一。
本课程旨在通过理论与实践相结合的方式，让学生掌握机器人设计的基本方法，并能够独立完成一个自动走迷宫机器人的设计和实现。
二、课程目标理解机器人设计的基本原理和方法。
学习迷宫问题的解决策略。
掌握传感器、控制器等机器人硬件的使用。
熟悉编程语言在机器人控制中的应用。
培养团队合作和项目管理的能力。
三、迷宫问题概述迷宫问题是一个经典的搜索问题，目标是在有限的空间内找到从起点到终点的路径。
在机器人领域，迷宫问题通常涉及到路径规划、障碍物避让等技术。
四、机器人设计硬件设计：包括传感器（如红外传感器、超声波传感器）、控制器（如Arduino或Raspberry Pi）、驱动器（如电机驱动器）和机械结构等。
软件设计：包括迷宫问题的算法实现（如深度优先搜索、广度优先搜索、A*算法等）和机器人控制程序的编写。
系统集成：将硬件和软件集成到一起，确保机器人能够按照预期工作。
五、课程实施理论学习：通过课堂讲授和阅读教材，学生学习机器人设计的理论知识。
实践操作：学生在实验室中进行机器人的组装和编程实践。
团队合作：学生分组进行项目开发，培养团队协作能力。
项目管理：学生需要制定项目计划，管理项目进度，确保按时完成任务。
六、项目实施需求分析：明确机器人的功能需求和性能指标。
方案设计：设计机器人的硬件架构和软件架构。
硬件组装：根据设计方案，选择合适的硬件组件进行组装。
软件开发：编写控制算法和机器人控制程序。
测试与调试：在迷宫环境中测试机器人的性能，进行必要的调试。
性能优化：根据测试结果，优化机器人的设计，提高其性能。
七、课程成果机器人原型：学生成功设计并实现了一个能够自动走迷宫的机器人原型。
技术报告：学生撰写了详细的技术报告，包括设计思路、实现过程和测试结果。
展示与交流：学生在课程结束时进行了项目展示，并与其他团队进行了交流。
人工智能趣味题
以下是一个关于人工智能的趣味题：
题目描述：
你被困在了一个迷宫里，这个迷宫有两个出口，一个出口是安全的，另一个出口则有危险。
你有一台人工智能助手，这台助手只能回答"是"或"否"，而且这台助手不会说谎，但只会基于你提供的信息来做出判断。
你可以向这台助手提出一个问题，通过这个问题的答案来判断哪个出口是安全的。
思考：
为了确保安全通过迷宫，你应该向人工智能助手提出什么问题？提示：
为了得到有用的答案，你需要提出一个巧妙设计的问题，这个问
题需要考虑到人工智能助手只能回答"是"或"否"，并且不能提
供超过问题范围的信息。
解决迷宫问题的算法
迷宫问题是一个经典的计算机科学问题，它在很多领域中都有广泛的应用，包括搜索、路径规划、人工智能等等。
解决迷宫问题的算法有很多种，其中最常见的是深度优先搜索和广度优先搜索。
深度优先搜索算法是一种递归的算法，通过不断地向下探索路径，直到找到终点或者到达死胡同为止。
该算法在实现上比较简单，但是可能会陷入死循环，因此需要特判。
广度优先搜索算法则是一种迭代的算法，通过按照层次逐步扩展搜索范围，最终找到终点。
该算法的实现较为复杂，但是能够找到最短路径。
除了深度优先搜索和广度优先搜索，还有其他一些算法可以用来解决迷宫问题，例如A*算法、IDA*算法等等。
这些算法都有各自的
优缺点和适用范围，需要根据具体情况进行选择。
总之，解决迷宫问题的算法有很多种，每一种都有其特点和适用范围。
在实际应用中，我们需要根据具体情况来选择合适的算法，以便更好地解决问题。
- 1 -。
人工智能大作业班级：13111学号：13111姓名：一、问题描述在如图所示的迷宫，找出从起点（1,1）到终点（4,4），要求步数最小.1：初始状态，入口处。
2：目标状态，出口处3：操作方式下上右左二、解题步骤：1：设估价函数：f(n)=g(n)+h(n);g(n)=d(n);h(n)=|Yg-xn|+|Yg-yn|;:2：将迷宫问题转化为格子问题3：按照操作步骤得到状态空间树如下：g=0,h=7,f=7g=1,h=6,f=7g=2,h=5,f=7g=3,h=4,f=7g=4,h=5,f=9 g=4,h=3,f=7g=5,h=2,f=7g=5,h=6,f=11 g=5,h=4,f=9 g=6,h=1,f=7g=6,h=3,f=9 g=7,h=0,f=7g=7,h=2,f=9g=8,h=1，f=9g=9,h=2,f=11,1,11,22,23,23,12,13,33,44,45,416543 287109 4,1 4,2 4,3 5,2 5,15,3 15 1413 121116g=10,h=3,f=134 根据状态空间树得到open表，close表如下：节点父节点f(n)1 无72 1 73 2 74 3 79 4 95 4 76 5 77 6 78 7 716 9 1110 9 911 10 912 11 913 12 914 13 1115 14 13编号节点父节点f(n)8 8 7 77 7 6 76 6 5 75 5 4 74 4 3 73 3 2 72 2 1 71 1 无7根据上表得出路径为s1->s2->s3->s4->s5->s6->s7->s8->sgtracedomainsstate=symboldatabase-mydatabaseopen(state,integer)closed(integer,state,integer)res(state)mark(state)fail_predicatessolvesearch(state,state)resultsearchingstep4(integer,state)step56(integer,state)equal(state,state)repeatresulting(integer)rule(state,state)road(state,state)goalsolve.clausessolve:-search(s0,sg),result.search(Begin,End):-retractall(_,mydatabase),assert(closed(0,Begin,0)),assert(open(Begin,0)),assert(mark(End)),repeat,searching,!.result:-not(fail_),retract(closed(0,_,0)),closed(M,_,_),resulting(M),!.result:-beep,write("sorry don't find a road!").searching:-open(State,Pointer),retract(open(State,Pointer)),closed(No,_,_),No2=No+1,asserta(closed(No2,State,Pointer)),!,step4(No2,State).searching:-assert(fail_).step4(_,State):-mark(End),equal(State,End). step4(No3,State):-step56(No3,State),!,fail.step56(No4,StateX):-rule(StateX,StateY),not(open(StateY,_)),not(closed(_,StateY,_)),assertz(open(StateY,No4)),fail. step56(_,_):-!.equal(X,X).repeat.repeat:-repeat.resulting(N):-closed(N,X,M),asserta(res(X)),resulting(M).resulting(_):-res(X),write(X),nl,fail. resulting(_):-!.rule(X,Y):-road(X,Y).road(s0,s1).road(s1,s2).road(s2,s5).road(s5,s4). road(s4,s7).road(s7,s8).road(s8,s9). road(s9,sg).。
一、问题描述迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。
图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）实验分析从上面的图中可以看出程序运行结果与分析结果一致，程序运行正确。
