logo资料库

基于A*算法的最优路径规划系统.doc

发布时间：2022-06-06 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：doc 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    基于A*算法的最优路径规划系统
    人工智能课程大作业 基于 A*算法的最优路径规划系统 XXXXXXXXX 摘要：人工智能(Artificial Intelligence)是当前科学技术发展的一门前沿学科，同时也是一门新思想， 新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。本文将主要介绍人工智能在搜 索方法上的应用，即基于A*算法的最优路径规划问题的解决方法。A*算法是一种求解最短路径的有 效方法，也是人工智能算法中一种简单的启发式搜索方法。本文介绍了A* 算法的原理及实现机制， 以及在搜索出的结点解空间集中，用A* 算法如何选择最优结点，最终求解出最短路径的过程。 关键词：人工智能；研究报告；模板 本组成员：xxxxxxx 本人分工：A*算法设计及实现 1 引言 人工智能是在计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基 础发展起来的，因此又可把它看作是一门综合性的边缘学科[1]。它的出现及所取得的成就引起了人 们的高度重视,并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为 20 世纪的三 大科学技术成就。人工智能学科研究的主要内容包括：知识表示、自动推理和搜索方法、机器学习 和知识获取、知识处理系统、自然语言理计算机视觉、智能机器人、自动程序设计等方面。 本文主要介绍在路径规划问题上使用 A*搜索算法来找到最优路径的设计与实现。 路径规划是指在旅行前或旅行中为驾驶员提供参考行驶路线的过程，是车辆定位与导航系统的 基本功能之一针对陆地车辆导航的不同要求，在路径规划中可采取多种优化标准，如最短距离、最 少行驶时间或收费。本实验中将使用最短距离来寻找最优路径。 2 算法原理与系统设计 2.1 A*算法的基本思想 A*算法在人工智能中是一种典型的启发式搜索算法，通过选择合适的估价函数，指导搜索朝着 最有希望的方向前进, 以求得最优解[2]。A*算法中，关键是求估价函数：f(n)=g(n)+h(n).其中，g(n) 是从起点 u 到当前节点 n 己付出的代价，h(n)是从当前节点 n 到目标节点 v 的代价估计函数，必 须保证h(n) <=h’(n)，其中h’(n)是从当前点到目标点的实际最小代价。 2.2 A*算法的步骤 A*算法的搜索步骤如下： （1）给起始节点标记，对它的没有标记过的子节点进行扩展； （2）对每一个子节点计算评价函数值，按评价值的大小进行排列，找出评价值最小的节点，并 给它作标记，如果当前节点就是目标节点，则停止搜索。 （3）否则，对最新被标记的节点进行第（2）步处理，并记录最短路径。 2.3 算法分析 A*算法是利用对问题的了解和对问题求解过程和解的了解，寻求某种有利于问题求解的启发信 息，从而利用这些启发信息去搜索最优路径它不用遍历整个地图，而是每一步搜索都根据启发函数 朝着某个方向搜索当地图很大很复杂时，它的计算复杂度大大优于算法，是一种搜索速度非常快、 效率非常高的算法。但是，相应的A*算法也有它的缺点，启发性信息是人为加入的，有很大的主观 1
    人工智能课程大作业 性，直接取决于操作者的经验，对于不同的情形要用不同的启发信息和启发函数，且他们的选取难 度比较大，很大程度上找不到最优路径。 2.4 系统设计 系统的实现流程图如图2.1所示。 图2.1 系统的实现流程图 首先判断初始结点的周围8个结点是否有障碍点，从除障碍点以外的结点中求解出代价最小的结 点，并加入到结果列表中。 求解结点代价是根据A*算法的估价函数f(n)=g(n)+h(n)。其中g(n)是从起始结点到当前节点 n 己 付出的代价，h(n)是从当前节点 n 到目标节点的代价估计。 2
    人工智能课程大作业 对于本实验中，设计的g(n)=10（当前结点与起始结点在同一水平线或者竖直线上。如图2.2中， 初始结点，即蓝结点与1、3、5、7结点之间的代价即为10。）g(n)=14（当前结点与起始结点在同一 对角线上时。如图2.2中，初始结点，即蓝结点与0、2、4、6结点之间的代价即为14。） 对于本实验中，h(n) = (当前结点与目标结点之间横坐标格数 + 当前结点与目标结点之间纵坐标 格数) * 10。如图2.2中，当前结点依次为0、1、2、3、4、5、6、7，分别与红色目标结点求解h(n)。 图2.2 搜索图 每次求解出的8个h(n)，比较大小，选出最小的结点作为起始节点继续搜索。直到遇到目标结点 便结束搜索，画出求解出的最优路径。 3 系统实现 void CAxingTestDlg::ExecuteCalculate(RectIndex RI[], RectIndex * resultRI, bool * find) { //判断 8 个相邻点里是否有障碍点 for (int i = 0; i < 8; i++) { for (int j = 0; j < blockPointNum; j++) { if (RI[i].m == blockIndexM[j]&&RI[i].n == blockIndexN[j])//有障碍点 { RI[i].weight = 10000; } } } //得到权值最小的点 int minWeight=10000, minweightIndexM,minweightIndexN; for(int i = 0; i < 8; i++) 3
    人工智能课程大作业 { minWeight = min(minWeight,RI[i].weight); } resultRI->weight = minWeight; for(int i = 0; i < 8; i++)//获得权值最小点的坐标 { if (RI[i].weight == minWeight) { minweightIndexM = RI[i].m; minweightIndexN = RI[i].n; } } resultRI->m = minweightIndexM; resultRI->n = minweightIndexN; pathPointIndex[pathPointIndexSub].m = resultRI->m;//存储路径 pathPointIndex[pathPointIndexSub].n = resultRI->n; pathPointIndex[pathPointIndexSub].weight = resultRI->weight;//存储当前遍历点的权值 totalWeigeht += pathPointIndex[pathPointIndexSub].weight; pathPointIndexSub++; //判断 8 个相邻点是否有目标点 for (int i = 0; i < 8; i++) { if (RI[i].m == endRectIndex.m&&RI[i].n == endRectIndex.n) { *find = true; break; } } } void CAxingTestDlg:: GetAroundPoint(RectIndex RI0, RectIndex RI[])//获得邻接点坐标，同 时计算权值 { int i = RI0.m; int j = RI0.n; int postM,postN; RI[0].m = i-1; RI[0].n = j-1; postM = (i-1)>endRectIndex.m?(i-1-endRectIndex.m):(endRectIndex.m-(i-1)); postN = (j-1)>endRectIndex.n?(j-1-endRectIndex.n):(endRectIndex.n-(j-1)); 4
    人工智能课程大作业 RI[0].weight = (postM+postN)*10 + 14; RI[1].m = i-1; RI[1].n = j; postM = (i-1)>endRectIndex.m?(i-1-endRectIndex.m):(endRectIndex.m-(i-1)); postN = j>endRectIndex.n?(j-endRectIndex.n):(endRectIndex.n-j); RI[1].weight = (postM+postN)*10 + 10; RI[2].m = i-1; RI[2].n = j+1; postM = (i-1)>endRectIndex.m?(i-1-endRectIndex.m):(endRectIndex.m-(i-1)); postN = (j+1)>endRectIndex.n?(j+1-endRectIndex.n):(endRectIndex.n-(j+1)); RI[2].weight = (postM+postN)*10 + 14; RI[3].m = i; RI[3].n = j-1; postM = i>endRectIndex.m?(i-endRectIndex.m):(endRectIndex.m-i); postN = (j-1)>endRectIndex.n?(j-1-endRectIndex.n):(endRectIndex.n-(j-1)); RI[3].weight = (postM+postN)*10 + 10; RI[4].m = i; RI[4].n = j+1; postM = i>endRectIndex.m?(i-endRectIndex.m):(endRectIndex.m-i); postN = (j+1)>endRectIndex.n?(j+1-endRectIndex.n):(endRectIndex.n-(j+1)); RI[4].weight = (postM+postN)*10 + 10; RI[5].m = i+1; RI[5].n = j-1; postM = (i+1)>endRectIndex.m?(i+1-endRectIndex.m):(endRectIndex.m-(i+1)); postN = (j-1)>endRectIndex.n?(j-1-endRectIndex.n):(endRectIndex.n-(j-1)); RI[5].weight = (postM+postN)*10 + 14; RI[6].m = i+1; RI[6].n = j; postM = (i+1)>endRectIndex.m?(i+1-endRectIndex.m):(endRectIndex.m-(i+1)); postN = j>endRectIndex.n?(j-endRectIndex.n):(endRectIndex.n-j); RI[6].weight = (postM+postN)*10 + 10; RI[7].m = i+1; RI[7].n = j+1; postM = (i+1)>endRectIndex.m?(i+1-endRectIndex.m):(endRectIndex.m-(i+1)); postN = (j+1)>endRectIndex.n?(j+1-endRectIndex.n):(endRectIndex.n-(j+1)); RI[7].weight = (postM+postN)*10 + 14; 5
    人工智能课程大作业 if (i-1 < 0) { RI[0].weight = 10000; RI[1].weight = 10000; RI[2].weight = 10000; } if (j-1 < 0) { RI[0].weight = 10000; RI[3].weight = 10000; RI[5].weight = 10000; } if (i+1 > nRows-1) { RI[5].weight = 10000; RI[6].weight = 10000; RI[7].weight = 10000; } if (j+1 > nCols-1) { RI[2].weight = 10000; RI[4].weight = 10000; RI[7].weight = 10000; } } 4 实验或测试结果 在界面上设置初始节点（初始结点只能设置一个），设置若干障碍结点，设置终止结点（终止结 点只能设置一个）。点击“开始执行”，程序执行。 程序运行后出现如图 4.1 和图 4.2 所示。 5 结论 此最优路径规划系统完成了用位图背景加栅格的坐标数据来模拟地图、用户设置起点和终点、 用可视化的界面演示算法执行过程且能连续执行 、最终画出最优路径 等实验要求。 参考文献 [1] 吴胜，王书芹.人工智能基础与应用[M].电子工业出版社,2007.1. [2] 樊莉，孙继银，王勇.人工智能中的A*算法应用及编程.微机及发展，2003,23(3):16 6
    人工智能课程大作业 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    信息化

    共收录1827份资料，累计6个分类，关注成员有19位，主要包括：管理软件,企业管理,电子商务,其它,IT管理,项目管理

    热门标签

    管理软件 企业管理 电子商务 其它 IT管理 项目管理

    最新资料