人工智能实验一一致代价搜索算法实现

实验一：搜索算法问题求解智能1402201408070221李帅玲目录实验一：搜索算法问题求解..................................................................1一、实验目的...................................................................................2二、实验的硬件、软件平台............................................................2三、实验内容及步骤........................................................................2四、思考题.......................................................................................2五．实验报告...................................................................................3（一）算法的基本原理..............................................................3（二）算法的实验结果..............................................................5（三）实验分析和思考题..........................................................6（四）实验源代码......................................................................7一、实验目的1.了解一致代价搜索算法的基本原理；2.能够运用计算机语言实现一致代价搜索算法；3.应用搜索算法解决罗马尼亚问题；4.能够通过实验分析了解算法性能的优劣；二、实验的硬件、软件平台硬件：计算机软件：操作系统；WINDOWS2000应用软件：C,Java或者MATLAB三、实验内容及步骤图一：罗马尼亚地图1、根据图一创建搜索树，以Arad为初始状态，Bucharest为目标状态；2、实现一致代价搜索的图搜索算法并记录搜索路径。四、思考题1、根据实验结果分析一致代价搜索的完备性，最优性，时间和空间复杂度。2、指出无信息搜索策略和有信息搜索策略的不同。3、分析一致代价搜索如何保证算法的最优性五．实验报告（一）算法的基本原理1.基本原理一致代价搜索总是扩展路径消耗最小的结点n。n点的路径消耗等于前一结点n-1的路径消耗加上n-1到n的路径消耗。2.算法实现流程a.相关函数：地图初始化函数：其中map.txt为图搜索树信息：路径数目23条，路径起始点s，结束点t，路径消耗cost:下标获取函数：ｂ．主函数实现流程：首先初始化地图，创建优先队列ｑ，输入起始城市和目标城市并获取城市的下标，将起始结点入队列。一致搜索过程：将优先队列中当前路径消耗最小的头结点弹出，（因为结点在优先队列中，其头结点必然为队列中路径消耗最小的才会弹出。）对其进行扩展标记，判断当前结点是否为目标结点，如果不是，将该结点的后继结点入队列，并记录其前继结点，后继结点的路径消耗值等于当前结点的路径消耗加上当前结点到它的路径消耗；如果当前结点为目标结点，则将路线及路径总耗散输出，即把记录的前继结点结点输出。一致搜索结束后，若还没有找到路径，则说明目标结点可能不在地图中。（二）算法的实验结果1．实验结果2.结果说明起点Arad，终点Bucharest:结点扩展遍历过程:Arad-Zerind-Timisoara-Sibiu-Oradea-Rimnicu_Vilcea-Lugoj-Fagaras-Oradea-Mehadia-Pitesti-Craiova-Drobeta-Bucharest最终路线：Arad-Sibiu-Rimnicu_Vilcea-Pitesti-Bucharest路径总耗散值：418（三）实验分析和思考题1、根据实验结果分析一致代价搜索的完备性，最优性，时间和空间复杂度。完备性：一致代价搜索对解路径的步数并不关心，只关心路径总代价。所以，如果存在零代价行动就可能陷入死循环。如果每一步的代价都大于等于某个小的正常数，那么一致代价搜索是完备的。从算法中也可以看到，一致搜索将地图中相关联的路径都入了队列，不存在遗漏的点线，所以如果目标结点在图中，最终总会找到一条路径到达目标结点。最优性：一致代价搜索是最优的。一致代价搜索目标检测应用于结点被选择扩展时，而不是在结点生成的时候，因为第一个生成的目标结点可能在次优路径上。而且如果边缘中的结点有更好的路径到达该结点那么会引入一个测试。简单来说，优先队列保证了每一个出队扩展的结点都是最优的，如此得到了一个最优的路径。时间和空间复杂度：一致代价搜索由路径代价而不是深度来导引。引入Ｃ表示最优解的代价，假设每个行动的代价至少为ｅ，那么最坏情况下，算法的时间和空间复杂度为Ｏ（ｂ（１＋［Ｃ／ｅ］））。2、指出无信息搜索策略和有信息搜索策略的不同。无信息搜索指的是除了问题定义中提供的状态信息外没有任何附加信息。搜索算法要做的是生成后继并区分目标状态与非目标状态。这些搜索是以结点扩展的次序来分类的。而有信息搜索策略知道一个非目标状态是否比其他状态更有希望接近目标。而它这种判断希望的想法可能会让它错失最优解。3、分析一致代价搜索如何保证算法的最优性首先一致代价搜索选择结点ｎ去扩展时就已经找到到达结点ｎ的最优路径；接着由于每一步的代价是非负的，随着结点的增加路径绝不会变短。这两点说明了一致代价搜索按结点的最优路径顺序扩展结点。所以第一个被选择扩展的目标结点一定是最优解。（四）实验源代码#includeiostream#includefstream#includestring#includequeueusingnamespacestd;#defineINF0x7FFFFFstringCityName[]={Oradea,Zerind,Arad,Sibiu,Fagaras,Timisoara,Lugoj,Rimnicu_Vilcea,Pitesti,Mehadia,Drobeta,Craiova,Bucharest,Giurgiu,Urziceni,Hirsova,Vaslui,Iasi,Neamt,Eforie};intmap[21][21];//存储地图信息boolvisit[21];//标记是否已遍历intnum;//地图路径数intcost;//路径的耗散值intpre[21];//存储前继结点structnode{intcity;//城市编号intcost;//当前耗散值node(){}node(intmcity,intmcost){city=mcity;cost=mcost;}//优先队列排序定义booloperator(constnode&s)const{returncosts.cost;}booloperator(constnode&s)const{returncosts.cost;}booloperator==(constnode&s)const{returncost==s.cost;}};intgetIndex(stringcity);//对地图进行初始化voidinitMap(){strings,t;inta,b;ifstreamfin(map.txt);for(inti=0;i20;i++)for(intj=0;j20;j++)map[i][j]=INF;for(inti=0;i20;i++){pre[i]=-1;}finnum;while(num--){finstcost;a=getIndex(s);b=getIndex(t);map[a][b]=map[b][a]=cost;}fin.close();}//与CityName比对，获取城市下标intgetIndex(stringcity){for(inti=0;i20;i++){if(CityName[i]==city)returni;}return-1;}//主函数intmain(){initMap();//初始化地图priority_queuenodeq;//优先队列stringsource,target;//起始城市和目标城市cout请输入起始城市和目标城市：endl;cinsourcetarget;//获取城市对应编号ints=getIndex(source);intgoal=getIndex(target);q.push(node(s,0));cout结点生成:CityName[s]路径耗散：0endl;nodeCurNode;//一致搜索while(!q.empty()){inttemp;CurNode=q.top();q.pop();//通过优先队列，出来的结点必然是路径耗散最小的cout结点扩展：CityName[CurNode.city]路径耗散：CurNode.costendl;visit[CurNode.city]=true;//访问标记if(CurNode.city==goal){//找到目标结点intk=goal;cout路线：CityName[goal]--;while(pre[k]!=s){coutCityName[pre[k]]--;k=pre[k];}coutCityName[s]endl;cout路径总耗散：CurNode.costendl;return0;}//没有到达目标结点，生成后继结点for(inti=0;i20;i++){if(map[CurNode.city][i]!=INF&&visit[i]==false){pre[i]=CurNode.city;//保存i点的前继结点temp=CurNode.cost+map[CurNode.city][i];q.push(node(i,temp));//入优先队列cout结点生成:CityName[i]路径耗散：costendl;}}}printf(没找到目标结点！);return0;}