下载文档原格式
使⽤AStar算法实现⾃动寻路详解@⽬录前些⽇⼦我有兄弟给我打电话，问我会不会⼈⼯智能，来实现⼀个机器⼈在仓库⾃动寻路的功能。
因为没有接触过这样的场景，但是⾃⼰⼜⽐较对此兴趣，所以就看了⼀些⾃动寻路的算法，⽐如：基于⼆叉树的深度优先遍历、D Star、A Star算法，其中我感觉A Star算法最好。
下⾯我给⼤家介绍⼀下，⾸次实现的语⾔是Java，但是Java不太直观，⼜不想使⽤Java的图形界⾯，所以就使⽤JS+HTML来实现的，⾸先展⽰⼀下效果图。
效果图如下：1、什么是A Start算法A*搜索算法是求出在⼀个⼆维平⾯中从起点到终点最低运算代价的算法，它可以算出A点到B点的最短距离，也就是最优路径。
常见的应有主要是在游戏中，⼈物的⾃动寻路；机器⼈探路；交通路线导航等。
2、A Star算法的原理和流程2.1 前提在讲述A Star算法之前，需要声明下列这些属性：（1）从起点开始扩散的节点；（2）最短距离计算公式：F = G + H；（3）欧⼏⾥得距离计算公式：p = $\sqrt (x_2 - x_1)^2+(y_2 - y_1)^2$（其实就是勾股定理）；（4）OPENLIST 和 CLOSELIST；上⾯的属性和公式不懂没关系，下⾯我会对他们⼀⼀进⾏详细介绍。
⾮常简单！2.1.1 从起点开始扩散的节点我们在HTML页⾯上使⽤横和竖画出来的格⼦。
所谓扩散就是以起点为基点向上、下、左、右四个放向进⾏扩散，这些扩展的节点就是可以⾛的“路”。
如下图所⽰黄⾊的⽅格就是扩散的点：PS:A Star有四个⽅向和⼋个⽅向的扩散。
扩展四个⽅向的节点就是⽬前我们所说的；⼋个⽅向是还包含了，上左、上右、下左、下右四个⽅向的节点。
我们通篇使⽤的是四个⽅向的扩展。
2.1.2 最短距离计算公式：F = G + H如何在扩散的节点中找到最优也就是最短的⼀条路呢？就需要⽤到这个公式：F=G+H。
那么这个公式⾥⾯的属性都代表什么意识呢？下⾯我们就说明⼀下：（1）G:表⽰从起点到扩散的四个节点的距离，换句话说就是从起点到扩散的四个节点需要移动的格⼦。
一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
例如：图1 八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或A* 算法）编程求解八数码问题（初始状态任选）。
选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。
二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验算法A*算法是一种常用的启发式搜索算法。
在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。
A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。
由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) = g(n) + h(n)其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。
在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。
用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。
这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。
（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。
A*算法原理简介A*（A-Star)算法是一种静态路网中求解最短路最有A star算法在静态路网中的应用效的方法。
公式表示为： f(n)=g(n)+h(n),其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。
但能得到最优解。
如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近估价函数取得就越好例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。
明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristicOptimistic (must be less than or equal to the real cost)As close to the real cost as possible详细内容主要搜索过程伪代码如下：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;将起点放入OPEN表;while(OPEN!=NULL){从OPEN表中取估价值f最小的节点n;if(n节点==目标节点){break;}for(当前节点n 的每个子节点X){算X的估价值;if(X in OPEN){if( X的估价值小于OPEN表的估价值 ){把n设置为X的父亲;更新OPEN表中的估价值; //取最小路径的估价值}}if(X inCLOSE) {if( X的估价值小于CLOSE表的估价值 ){把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN //取最小路径的估价值}}if(X not inboth){把n设置为X的父亲;求X的估价值;并将X插入OPEN表中; //还没有排序}}//end for将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
二、程序运行测试A*算法求解八数码问题一、详细设计说明1.评价函数以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。
距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值 + 列下标与目标位置列下标之差的绝对值”。
距离越小，该节点的效果越好。
某个状态所有将牌到目标位置的距离之和用“h值”表示。
2.主要函数2.1countH（state & st）;countH函数功能是计算st状态的h值。
计算过程中将会用到rightPos数组，数组里记录的是目标状态下，0~9每个将牌在九宫格里的位置（位置 = 行下标 * 3 + 列下标）。
2.2f（state * p）;f()=h()+level2.3look_up_dup(vector<state*> & vec, state * p);在open表或close表中，是否存在指定状态p，当找到与p完全相等的节点时，退出函数。
2.4search(state & start)；在open表不为空时，按f值由小到大对open表中元素进行排序。
调用findZero()函数找到0值元素的位置。
空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。
确定某方向可走后，空格移动一步，生成状态p’。
此时，检查open表中是否已有p’，若有，更新p’数据；检查close表中是否已有p’，若有，将p’从close表中删除，添加到open表中。
重复的执行这个过程，直到某状态的h值为零。
2.5dump_solution(state * q)；在终端输出解路径。
// A*算法八数码问题#include"stdafx.h"#include<iostream>#include<vector>#include<time.h>#include<algorithm>using namespace std;const int GRID = 3; //Grid表示表格的行数(列数)，这是3*3的九宫格int rightPos[9] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 };//目标状态时，若p[i][j]=OMG,那么3*i+j = rightPos[OMG]struct state{int panel[GRID][GRID];int level; //记录深度int h;state * parent;state(int level) :level(level){}bool operator == (state & q){//判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回falsefor (int i = 0; i<GRID; i++){for (int j = 0; j<GRID; j++){if (panel[i][j] != q.panel[i][j])return false;}}return true;}state & operator = (state & p){ //以状态p为当前状态赋值，对应位置元素相同for (int i = 0; i<GRID; i++){for (int j = 0; j<GRID; j++){panel[i][j] = p.panel[i][j];}}return *this;}};void dump_panel(state * p){ //将八数码按3*3矩阵形式输出for (int i = 0; i<GRID; i++){for (int j = 0; j<GRID; j++)cout << p->panel[i][j] << " ";cout << endl;}}int countH(state & st){ //给定状态st，计算它的h值。
江南大学物联网工程学院实验报告课程名称人工智能实验名称A*算法解决8数码问题实验日期2018.3.20班级计科1501 姓名周启航学号1030415127一、实验目的：修改A*算法，使之能解决N*N矩阵八数码问题问题描述：八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0可自己随机设定，使用的操作有:空格上移，空格左移，空格右移，空格下移。
二、算法描述：1.状态描述八数码的任何一种摆法就是一个状态，所有摆法即为状态集S，他们构成了一个状态空间，其大小为9包括8个数码和一个空格，每个数码就是一个分离的独立的子空间，其所在位置为x：i/3，y：i%3.相应的操作算子就是数码的移动即：将空格向上移UP、将空格向下移DOWN、将空格向左移LEFT、将空格向右移RIGHT，经过一些操作算子后达到目标状态。
2.启发函数设计启发函数为现在的状态中各位置与目标状态各位置数码值不同的个数，例如：现在状态：w=123456780,目标状态为：t=123456708，则h（n）=2.3.规则的判断条件把未扩展的状态存入open表，排序后取出优先状态扩展搜索，将扩展后的存入closed表，循环执行直到扩展出目标状态。
4.算法流程图5.核心代码操作算子：int solve() //搜索过程{P cur;P p;while(!open.empty()){cur=open.top(); //open表open.pop();if(cur.s==t) return cur.id; //达到目标状态，返回当前节点的idint x,y;int ops=0;while(cur.s[ops]!='0') ops++;x=ops/N,y=ops%N; //空格所在位置int r=cur.id;if(x>0){ //空格向上移p.s=cur.s;swap(p.s[ops],p.s[ops-3]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}if(x<N-1){ //空格向下移p.s=cur.s;swap(p.s[ops],p.s[ops+3]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}if(y>0){ //空格向左移p.s=cur.s;swap(p.s[ops],p.s[ops-1]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}if(y<N-1){ //空格向右移p.s=cur.s;swap(p.s[ops],p.s[ops+1]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}}return -1; //搜索失败}int main(){cout<<"请输入棋盘大小N*N\nN:";cin>>N;cout<<"请输入测试的组数:\n";int tt; //测试的组数cin>>tt;for(int k=1;k<=tt;k++){cout<<"Case "<<k<<":\n";int i,j;char a;cout<<"请输入目的状态：\n";cin>>t;p.s="";cout<<"请输入初始状态:\n";for(i=0;i<N;i++){for(j=0;j<N;j++){cin>>a; //输入0～8数码p.s+=a;}}p.d=0,p.w=calw(p.s),p.id=0;father[0]=-1;mp[p.s]=1;stack[0]=p.s;open.push(p); //往open表中加入初始状态节点int id=solve();//调用搜索过程if(id==-1){cout<<"无解！\n";}else{int c=-1;while(id>=0){ //把stack中存的节点按次序放入到record中record[++c]=stack[id];id=father[id];}cout<<"原图："<<endl;print(c); //输出初始节点cout<<"移动过程: \n\n";for(i=c-1;i>=0;i--){cout<<"Step "<<c-i<<":\n";//输出当前搜索步骤print(i);//输出当前搜索的节点}cout<<"移动结束！\n";mp.clear();while(!open.empty()) open.pop();top=0;cout<<endl;}system("pause\n");return 0;}三、实验结果：四、实验心得：只是做了简单修改，只能解决些简单的问题，过于复杂的还不能实现，不过还是体会到了A*算法的厉害，也见识到了人工智能的神奇，会继续努力学习。
基于A星算法的8数码问题求解⽅案设计（1）⼀、问题描述8数码问题⼜称9宫问题，与游戏“华容道”类似。
意在给定的33棋格的8个格⼦内分别放⼀个符号，符号之间互不相同，余下的⼀格为空格。
并且通常把8个符号在棋格上的排列顺序称作8数码的状态。
开始时，规则给定⼀个初始状态和⼀个⽬标状态，并要求被试者对棋格内的符号经过若⼲次移动由初始状态达到⽬标状态，这个过程中只有空格附近的符号可以朝空格的⽅向移动，且每次只能移动⼀个符号。
为⽅便编程和表⽰，本⽂中8个格⼦内的符号分别取1—8的8个数字表⽰，空格⽤0表⽰。
并给定8数码的初始状态和⽬标状态分别如图1、2所⽰。
图1 初始状态图2 ⽬标状态则要求以图1为初始状态，通过交换0和0的上、下、左、右四个⽅位的数字（每次只能和其中⼀个交换），达到图2所⽰⽬标状态。
⼆、实验⽬的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利⽤A*算法求解N数码难题，理解求解流程和搜索顺序。
三、实验任务1）实现类似于如图所⽰N数码难题演⽰程序。
2）⽤你所熟悉的程序语⾔实现，可以B/S实现，也可以C/S实现四、算法设计根据任务要求，本⽂采⽤A*搜索算法。
但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表⽰的⽅式，并设计合适的启发函数，以提⾼搜索效率。
①状态的表⽰在A*算法中，需要⽤到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。
因此在表⽰当前状态的变量中，必须要有能指向下⼀个扩展节点的指针，以完成对open表中元素的索引。
从这⼀点上看，open表中的元素相互间即构成了⼀个线性表，因此初步选定使⽤结构体表⽰问题的状态。
如图3所⽰，表⽰问题的结构体包括表⽰当前节点状态的DATA和指向open 表中下⼀个待扩展节点的指针NEXT。
图3 结构体现在进⼀步考虑DATA中包括的内容：如图1、2所⽰，8数码问题的提出是以⼀个33数表表⽰的，因此本⽂中采⽤⼀个33的⼆维数组s[3][3]表⽰当前状态的具体信息。
astar寻路算法原理
A（A星）寻路算法是一种常用的启发式搜索算法，用于在图中
找到从起点到终点的最短路径。
它结合了Dijkstra算法和启发式搜
索的优点，具有较高的搜索效率。
A算法基于图的搜索，其中每个节点表示一个状态，边表示从
一个状态到另一个状态的转移。
算法使用两个函数来评估每个节点
的重要性，g(n)表示从起点到节点n的实际代价，h(n)表示从节点
n到终点的估计代价。
A算法通过综合考虑这两个函数来选择下一个
要扩展的节点。
具体来说，A算法通过维护一个开放列表和一个关闭列表来进
行搜索。
它首先将起点加入开放列表，然后重复以下步骤直到找到
终点或者开放列表为空：
1. 从开放列表中选择f(n)=g(n)+h(n)最小的节点n进行扩展。
2. 将节点n从开放列表中移入关闭列表。
3. 对节点n的相邻节点进行检查，更新它们的g值和f值，并
将它们加入开放列表中。
A算法的关键在于如何选择合适的启发函数h(n)以及如何高效地维护开放列表和关闭列表。
合适的启发函数可以大大提高搜索效率，而高效的列表维护可以减少搜索时间。
总的来说，A算法是一种高效的寻路算法，能够在图中找到最短路径，并且可以通过调整启发函数来适应不同的问题。
scratch编程算法题一、题目描述Scratch编程算法题是一个基于Scratch编程平台的趣味算法题目。
题目包括各种不同类型的算法问题，旨在锻炼学生的编程思维和解决问题的能力。
二、题目列表1.斐波那契数列求和：给定一个整数n，编写一个算法，使用递归或循环计算前n个斐波那契数的和。
2.寻找最长回文串：给定一个字符串，编写一个算法，找出其中的最长回文串。
3.快速排序：编写一个算法实现快速排序，并检查其性能。
4.八皇后问题：在一个8x8的棋盘上放置8个皇后，使得它们不能互相攻击（即在同一行、同一列或同一对角线上不能有两个皇后）。
编写一个算法找出所有解决方案。
5.汉明码校验：给定一组二进制数据和一个汉明码位数，编写一个算法验证数据的正确性。
三、解题思路1.斐波那契数列求和：可以使用递归或循环来计算斐波那契数列的和。
递归方法简单易懂，但效率较低；循环方法更常见，效率更高。
2.寻找最长回文串：可以使用双指针法，一左一右向中间移动，比较字符是否相同，当遇到不相同时就向后移动指针，直到指针相遇为止。
3.快速排序：快速排序是一种常用的排序算法，其核心思想是分而治之。
首先选取一个基准值，将数组分成两部分，一部分小于基准值，一部分大于基准值。
然后对这两部分继续进行快速排序，直到整个数组有序。
性能可以通过优化选择基准值的方式进行提高。
4.八皇后问题：这是一个经典的回溯算法问题。
首先在棋盘上放置一个皇后，检查是否会与其它皇后发生冲突。
如果不冲突，就将皇后向右下方移动一格。
如果冲突，则回溯到上一次放置的位置，并尝试另一种放置方式。
重复这个过程直到找到所有解决方案。
5.汉明码校验：汉明码是一种具有较强检错和纠错能力的编码方式。
首先根据给定的位数和二进制数据生成校验位，然后将数据和校验位一起传输。
在接收端，通过计算校验位是否正确来判断数据的正确性。
四、代码实现由于Scratch编程平台主要面向初学者，因此代码实现部分将主要以伪代码形式呈现，具体实现可以参考Scratch编程平台的官方文档和示例代码。
A*算法求解8数码问题实验一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。
二、实验内容1、八数码问题描述所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8，其中一个单元格是空的。
将任意摆放的数码盘（城初始状态）逐步摆成某个指定的数码盘的排列（目标状态），如图1所示图1 八数码问题的某个初始状态和目标状态对于以上问题，我们可以把数码的移动等效城空格的移动。
如图1的初始排列，数码7右移等于空格左移。
那么对于每一个排列，可能的一次数码移动最多只有3中，即空格左移、空格右移、空格上移、空格下移。
最少有两种（当空格位于方阵的3个角时）。
所以，问题就转换成如何从初始状态开始，使空格经过最小的移动次数最后排列成目标状态。
2、八数码问题的求解算法2.1 盲目搜索宽度优先搜索算法、深度优先搜索算法2.2 启发式搜索启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。
先定义下面几个函数的含义：f*(n)=g*(n)+h*(n) (1)式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。
评价函数的形式可定义如(2)式所示：f(n)=g(n)+h(n) (2)其中n是被评价的当前节点。
f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。
利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。
在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。
采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。
