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

《人工智能实验一一致代价搜索算法实现》由会员分享，可在线阅读，更多相关《人工智能实验一一致代价搜索算法实现（10页珍藏版）》请在装配图网上搜索。

1、实验一：搜索算法问题求解智能 1402 201408070221 李帅玲目录实验一：搜索算法问题求解 1一、实验目的 2二、实验的硬件、软件平台 2三、实验内容及步骤 2四、思考题 2五实验报告 3（一）算法的基本原理 3（二）算法的实验结果 5（三）实验分析和思考题 6（四）实验源代码 7Aisd radeawarm87SlbiuFagarBBiTimisoaraHlmnlcu VlkieaaaMertsdiaUrzleenE75J 38ob hbW120sue rarestCraiovaGIULIOSTciiifhr-liiie disr-iwccEl Hue bu IE StAradBw

2、linvest0Crai&ii aEUobrelfi2-2EforieL61Fagsras176Giurgiu77Hirwl4isn226l?oj244hfluadLa241Nmnl234OradtaXSOPiiKtiJRioinku V ikeaLQ3SibtuTimiwiraUr/keni30X 巫uiwZeirind574ETQdle口 hkrawfi实验目的1. 了解一致代价搜索算法的基本原理；2. 能够运用计算机语言实现一致代价搜索算法3. 应用搜索算法解决罗马尼亚问题；4. 能够通过实验分析了解算法性能的优劣；、实验的硬件、软件平台硬件：计算机软件：操作系统；WINDOWS 200

3、0应用软件：C,Java或者MATLAB三、实验内容及步骤图一：罗马尼亚地图1、根据图一创建搜索树，以Arad为初始状态，Bucharest为目标状态;2、实现一致代价搜索的图搜索算法并记录搜索路径。四、思考题1、根据实验结果分析一致代价搜索的完备性，最优性，时间和空间复杂度。2、指出无信息搜索策略和有信息搜索策略的不同。3、分析一致代价搜索如何保证算法的最优性五实验报告（一）算法的基本原理1.基本原理一致代价搜索总是扩展路径消耗最小的结点nn点的路径消耗等于前一 结点n-1的路径消耗加上n-1到n的路径消耗。2.算法实现流程a.相关函数：地图初始化函数void initMap()Bstrin

4、g jIrlrtifstream fin(map.txt)jfarfint i=0ji2ji+j fonfint jiSjj29jj+)for(nt i=0:ii+ preij=-f irnum while(num-) finstCDt; a=getlndex(s)j b=getlnde:(t) j mapfaj bsr*apbfin.clase()j其中 map.txt 为图搜索树信息：路径数目23条，路径起始点s,结束点t,路径消耗cost:23Oradea Zerind 71Zerlnd Aradl 75OradlEa 筋 bin 151Arad Sibiu 14HArad Timis口

5、呂工乳 11STimisDara Lugoj 111Lugoj Hehaiiia 70I(吕hmcHsi Brobsta 75Droljsta CraioTa 120Craiova Riimicu_Vi 1 tea 14&Rismiicu_Vilc9a Sibiu 80Sibiu Fagaras 牺Kiieu_Vileea Pi testi 勺丁Pi test! Craiaa 13SFagarsE； Bucharest 211Pitesti Bucharest 101Bucharest Giuriu 90Bucharest Ctrziceni S5Urzicerd Hirsoa 98HirsD

6、va EforiEs BtiUrzLGBni 甲剥slid 142Taclui Iasi 92Tigl Noaimt 87下标获取函数：/ 4?萱tyNarne比旳,获取城京下标in+ gelTndex(string city)far(int =0i20i+)if(Cntyh3Mei=city)raturn i;return -1;b主函数实现流程：首先初始化地图，创建优先队列q,输入起始城市和目标城市并获取 城市的下标，将起始结点入队列。i n itMap() ; /觀;H 艺:WPriori:y_queue nodo q:7：. /string source , + argetj 打琶U/

7、声定 E亍我韦LOutsource target /获蚩城亡减应镰Slnt 5=getlndex(5ource)int goal = getIn des(target)jq.pushCnodetBjS)j匚outWS点生： ,sCityNames路径耗散t 0Biendl.jnode CurNodej一致搜索过程：将优先队列中当前路径消耗最小的头结点弹出，(因为结点在优先队列中，其头结点必然为队列中路径消耗最小的才会弹出。) 对其进行扩展标记，判断当前结点是否为目标结点，如果不是，将该结 点的后继结点入队列，并记录其前继结点，后继结点的路径消耗值等于 当前结点的路径消耗加上当前结点到它的路径消

8、耗；如果当前结点为目 标结点，则将路线及路径总耗散输出，即把记录的前继结点结点输出。irfhs.l I q - mptylrtt tcinipCurH 口 idcrq j 七中MCKh谊用堆芜畝禺出来的蛙点必議是踣径耗戦垂枣的cowt 站点扩展百cCityNane Curtode - cityHrSftflJl f hcCu rNode + cost epdl ivisit CurNkMie a cit .tnu* / 访问 7己lf( OurHcde * c ityugMl)( / .厂叮吕纭近Int knfOciljcont”碗疫w %：ityfJaiiegoa wtiil(prekr-s

9、Hcwttit/NeprekU料 kaprelklj；cowtCi tyl脂rfiE s edl j u締径融锂flir Cur-Node, cost*endl；j riturn G;揺苕垂烟耳曲.点 空磁丘避竝点If(KipCurniode,citvri I=INF M v 1 sit I =fsit)ot= 317 路瑕瓠俨 爨霸366f籬R耗散:416萨输m 哉!|；：九三折或uIflrod BumclitLrcstF-nF.tbl,： rirod FiM#巧卷 0 占启：And璋控耗散:0 b：,= Zcrind 产了” 成=Sibiu路径 ilimiso wa. 8i寤；crind山

10、pctua 严屮宀.Tinisoara 賂檯耗散;US 上吹,i賂每嚴为? 展;Stbin ,M Oradea Bjx Fagaras UiH 工丰Rimr icul_Uilcea 十，T F广展；Oracle a各逢歹T/T展；BimnicLJi_U1cbaLpji： Pite?ti JiiEji-匚ziaua 炳口展;戍二 MeliAdlia 密、览T展；FaSfaraD戌二 HunliiaFest不展：0眄dz 宅T展：HehflriiR 成;Draheta 出 宅T展！ Pili i 成;Oaiaua 脚戊二岂广”展：d,5 丄成;Droheta 路住 结点茁展 Drcbrtaj结点扩

11、展i BucharestBuchares t -Pits 31 iR inn icu_L i Ice a -S ih iuZerind-Timisoara-Sibiu-Oradea-Rimnicu_Vilcea-Lugoj-Fagaras-Oradea-Mehadia-Pitesti-Craiova-Drobeta-Bucharest最终路线：Arad- Sibiu- Rimnicu_Vilcea- Pitesti- Bucharest 路径总耗散值：418(三)实验分析和思考题1、根据实验结果分析一致代价搜索的完备性，最优性，时间和空间复杂度。完备性：一致代价搜索对解路径的步数并不关心，只关

12、心路径总代价。 所以，如果存在零代价行动就可能陷入死循环。如果每一步的代价都大于等于某 个小的正常数，那么一致代价搜索是完备的。从算法中也可以看到，一致搜索将 地图中相关联的路径都入了队列，不存在遗漏的点线，所以如果目标结点在图中， 最终总会找到一条路径到达目标结点。最优性：一致代价搜索是最优的。一致代价搜索目标检测应用于结点被 选择扩展时，而不是在结点生成的时候，因为第一个生成的目标结点可能在次优 路径上。而且如果边缘中的结点有更好的路径到达该结点那么会引入一个测试。 简单来说，优先队列保证了每一个出队扩展的结点都是最优的，如此得到了一个 最优的路径。时间和空间复杂度：一致代价搜索由路径代价

13、而不是深度来导引。引入C 表示最优解的代价，假设每个行动的代价至少为e,那么最坏情况下，算法的时 间和空间复杂度为O (b(l+C/e)。2、指出无信息搜索策略和有信息搜索策略的不同。 无信息搜索指的是除了问题定义中提供的状态信息外没有任何附加信息。搜索算法要做的是生成后继并区分目标状态与非目标状态。这些搜索是以结点扩 展的次序来分类的。而有信息搜索策略知道一个非目标状态是否比其他状态更有 希望接近目标。而它这种判断希望的想法可能会让它错失最优解。3、分析一致代价搜索如何保证算法的最优性首先一致代价搜索选择结点n去扩展时就已经找到到达结点n的最优路 径；接着由于每一步的代价是非负的，随着结点的

14、增加路径绝不会变短。这两点 说明了一致代价搜索按结点的最优路径顺序扩展结点。所以第一个被选择扩展的 目标结点一定是最优解。(四)实验源代码#include#include#include #includeusing namespace std;#define INF 0x7FFFFFstringCityName=Oradea,Zerind,Arad,Sibiu,Fagaras,Timisoara,Lugoj,Rimnicu_Vilcea,P itesti,Mehadia,Drobeta,Craiova,Bucharest,Giurgiu,Urziceni,Hirsova,Vaslui,Iasi

15、,Neamt,Efor ie;int map2121;存储地图信息bool visit21;标记是否已遍历int num; /地图路径数int cost; /路径的耗散值int pre21; /存储前继结点struct nodeint city; /城市编号int cost; /当前耗散值node()node(int mcity,int mcost)city=mcity;cost=mcost; /优先队列排序定义bool operator (const node &s) constreturn costs.cost;bool operator s.cost;bool operator = (c

16、onst node &s) constreturn cost=s.cost;int getIndex(string city);/对地图进行初始化void initMap()string s,t;int a,b;ifstream fin(map.txt);for(int i=0;i20;i+)for(int j=0;j20;j+) mapij=INF;for(int i=0;inum;while(num-)finstcost;a=getIndex(s);b=getIndex(t); mapab=mapba=cost;fin.close();/与 CityName 比对，获取城市下标int ge

17、tIndex(string city)for(int i=0;i20;i+)if(CityNamei=city)return i;return -1;/主函数int main()initMap(); /初始化地图priority_queue q; /优先队列string source,target; /起始城市和目标城市cout请输入起始城市和目标城市：sourcetarget;/获取城市对应编号int s=getIndex(source);int goal=getIndex(target);q.push(node(s,0);cout结点生成:CityNames路径耗散：0endl;node

18、CurNode;/一致搜索while(!q.empty()int temp;CurNode=q.top();q.pop();通过优先队列，出来的结点必然是路径耗散最小的cout 结 点 扩 展 ： CityNameCurNode.city路 径 耗 散CurNode.costendl;visitCurNode.city=true;访问标记if(CurNode.city=goal) /找到目标结点int k=goal;cout路线：CityNamegoal-;while(prek!=s)coutCityNameprek-;k=prek;coutCityNamesendl;cout路径总耗散：CurNode.costendl;return 0;/没有到达目标结点，生成后继结点for(int i=0;i20;i+)if(mapCurNode.cityi!=INF & visiti=false) prei=CurNode.city;保存i点的前继结点 temp = CurNode.cost+mapCurNode.cityi; q.push(node(i,temp);入优先队列 cout结点生成:CityNamei路径耗散：costendl;printf（没找到目标结点！）; return 0;