人工智能实验一

实验一：搜索算法问题求解班级：计科二班姓名：阳芹学号：201308010220一、实验目的1.了解4种无信息搜索策略和2种有信息搜索策略的算法思想以及基本原理；2.能够运用计算机语言实现这几种搜索算法；3.应用搜索算法解决罗马尼亚问题；4.能够通过实验比较分析各种搜索算法的优劣；5.能够设计新的启发式函数并进行性能分析；二、实验的硬件、软件平台硬件：计算机软件：操作系统；WINDOWS2000应用软件：C,Java或者MATLAB三、实验内容及步骤图一：罗马尼亚地图3.1：无信息搜索算法1、根据图一创建搜索树，以Arad为初始状态，Bucharest为目标状态；2、实现深度优先搜索的图搜索算法并记录搜索路径；3、实现一致代价搜索的图搜索算法并记录搜索路径。3.2：有信息搜索算法1、根据图一以Arad为初始状态，Bucharest为目标状态实现A*搜索，其中以各城市到Bucharest的直线距离为启发式函数(见图一右侧)；2、根据图一以Arad为初始状态，Hirsova为目标状态实现A*搜索，其中已知Bucharest为从Arad到Hirsova的必经之路，设计一个启发式函数并分析该函数的可采纳性和优势(与启发式函数定义为“Arad到Hirsova的直线距离”相比较)；四、需求分析分别用深度优先、一致代价、A*搜索算法得到从起始点Arad到目标点Bucharest的一条路径，即为罗马尼亚问题的一个解，在求解的过程中记录每种算法得到的解，即输出每种解得到的条路径。五、详细代码测试类：constintM=10000;ClassMain{//打印各个算法的结果intresult;intxiabiao[]=null;//访问的下标Publicstaticvoidmain(String[]args){Graphgraph=newGraph();System.out.println(----------------罗马尼亚问题---------------);System.out.println(1、深度优先搜索);DFSdfs=newDFS();dfs.DF_Search(graph,0,12);System.out.println(2、迭代加深的搜索);IDSids=newIDS();ids.IDS_Search(graph,0,12,15);//深度设15System.out.println(3、一致代价搜索);UCSucs=newUCS(graph,0,12);System.out.println(4、A*搜索);AXingaXing=newAXing();aXing.A_Search(graph,graph.H,0,15);//0-15即Arad到达Hirsova}Publicvoidshow(Graphg,Stackstack){//打印if(stack.size()==0){System.out.println(路径搜索失败);return;}result=0;System.out.print(访问的下标：);for(inti=0;istack.size();i++){System.out.print(--+stack.get(i));}System.out.print(\n访问过程：);xiabiao=newint[stack.size()];if(stack.isEmpty()){System.out.println(搜索失败);}else{for(inti=0;istack.size();i++){System.out.print(--+g.cities[(Integer)stack.get(i)]);}for(inti=0;istack.size()-1;i++){result+=g.path[(Integer)stack.get(i)][(Integer)stack.get(i+1)];}System.out.println(\n总长度为：+result+\n);g.markInit();//清空访问}}}PublicclassGraph{//数组存储图Publicintpath[][]=newint[][]{{0,75,M,118,140,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M},{75,0,71,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M},{M,71,0,M,151,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M},{118,M,M,0,M,111,M,M,M,M,M,M,M,M,M,M,M,M,M,M},{140,M,151,M,0,M,80,99,M,M,M,M,M,M,M,M,M,M,M,M},{M,M,M,111,M,0,M,M,70,M,M,M,M,M,M,M,M,M,M,M},{M,M,M,M,80,M,M,M,M,146,97,M,M,M,M,M,M,M,M},{M,M,M,M,99,M,M,0,M,M,M,M,211,M,M,M,M,M,M,M},{M,M,M,M,M,70,M,M,0,75,M,M,M,M,M,M,M,M,M,M},{M,M,M,M,M,M,M,M,75,0,120,M,M,M,M,M,M,M,M,M},{M,M,M,M,M,M,146,M,M,120,0,138,M,M,M,M,M,M,M,M},{M,M,M,M,M,M,97,M,M,M,138,0,101,M,M,M,M,M,M,M},{M,M,M,M,M,M,M,211,M,M,M,101,0,90,85,M,M,M,M,M},{M,M,M,M,M,M,M,M,M,M,M,M,90,0,M,M,M,M,M,M},{M,M,M,M,M,M,M,M,M,M,M,M,85,M,0,98,M,142,M,M},{M,M,M,M,M,M,M,M,M,M,M,M,M,M,98,0,86,M,M,M},{M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,86,0,M,M,M},{M,M,M,M,M,M,M,M,M,M,M,M,M,M,142,M,M,0,92,M},{M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,92,0,87},{M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,87,0}};Publicint[]H=newint[]{516,524,530,479,403,394,343,326,391,392,310,160,150,155,100,0};//启发式函数PublicString[]cities=newString[]{Arad,Zerind,Oradea,Timisoara,Sibiu,Lugoj,RimnicuVilcea,Fagaras,Mehadia,Drobeta,Craiova,Pitesti,Bucharest,Giurgiu,Urziceni,Hirsova,Eforie,Vaslui,Isi,Neamt};//城市名Publicint[]mark=newint[20];//访问标记PublicGraph(){//得到数据markInit();//访问标志初始化}PublicvoidmarkInit(){for(inti=0;imark.length;i++){mark[i]=0;}}PublicintgetFirstVex(intstart){//第一个孩子，return-1表示一个孩子都没有if(start=0&&startpath.length){for(intj=0;jpath.length;j++)if(path[start][j]M&&path[start][j]0)//有关系returnj;}return-1;}PublicintgetNextVex(intstart,intw){//下一个孩子if(start=0&&startpath.length&&w=0&&wpath.length){for(inti=w+1;ipath.length;i++)//w表示图G中顶点i的第j个邻接顶点的下一个邻接顶点if(path[start][i]M&&path[start][i]0)returni;}return-1;//返回-1，表示后面没有邻接点了}PublicintgetNumber(){returnpath.length;}}(1)深度优先基本原理：深度优先搜索采用堆栈寻找路径，首先从Arad结点出发，判断是否为目标结点，若否，寻找与该结点的邻接点，先搜索一条分支上的所有节点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。PublicclassDFS{//深度优先搜索类Stackstack=newStackInteger();intx;intw;//v0的第一个邻接点PublicvoidDF_Search(Graphg,intv0,intvg){//深度优先搜索--非递归式//g：图v0：开始节点vg：最终节点stack.push(v0);//入栈g.mark[v0]=1;//v0被访问while(true){x=(Integer)stack.peek();//查看栈顶元素w=g.getFirstVex(x);while(g.mark[w]==1){//被访问，则寻找下一个邻接点w=g.getNextVex(x,w);if(w==-1){break;}}while(w==-1){//没有找到下一个邻接点stack.pop();x=(Integer)stack.peek();w=g.getFirstVex(x);while(g.mark[w]==1){w=g.getNextVex(x,w);if(w==-1){break;}}}stack.push(w);g.mark[w]=1;if(w==vg)break;//到达终点}NewMain().show(g,stack);}}(2)一致代价基本原理：扩展的是路径消耗g(n)最小的节点n,用优先队列来实现，对解的路径步数不关心，只关心路径总代价。即使找到目标节点也不会结束，而是再检查新路径是不是要比老路径好，确实好，则丢弃老路径。PublicclassUCS{//一致代价类publicUCS(Graphg,intstart,intend){int[]pre=newint[20];//保存各个结点的前驱结点int[]dist=newint[20];//用于保存当前结点到起始结点的实际路径长度for(inti=0;ipre.length;i++){pre[i]=-1;dist[i]=M;}//调用一致搜索算法搜索路径UC_search(g,start,end,dist,pre);//打印路径显示函数displayPath(start,end,pre,g);}PublicvoiddisplayPath(intstart,intgoal,int[]prev,Graphg)//prev前驱节点{StackIntegerstack=newStackInteger();stack.push(goal);while(prev[goal]!=start){stack.push(prev[goal]);goal=prev[goal];}stack.push(start);System.out.print(访问的下标:);for(inti=stack.size()-1;i=0;i--){System.out.print(--+stack.get(i));}System.out.print(\n访问过程:);for(inti=stack.size()-1;i=0;i--){System.out.print(--+g.cities[stack