人工智能实验一

实验一：搜索算法问题求解

班级：计科二班 姓名：阳芹 学号：201308010220

一、实验目的

1. 了解4种无信息搜索策略和2种有信息搜索策略的算法思想以及基本原理； 2. 能够运用计算机语言实现这几种搜索算法； 3. 应用搜索算法解决罗马尼亚问题；

4. 能够通过实验比较分析各种搜索算法的优劣； 5. 能够设计新的启发式函数并进行性能分析；

二、实验的硬件、软件平台 硬件：计算机

软件：操作系统；WINDOWS 2000 应用软件：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的一条路径，即为罗马尼亚问题的一个解，在求解的过程中记录每种算法得到的解，即输出每种解得到的条路径。

五、详细代码 测试类：

const int M=10000;

ClassMain{ //打印各个算法的结果 int result;

int xiabiao[]=null;//访问的下标 Publicstaticvoid main(String[] args){ Graph graph=newGraph();

System.out.println(\罗马尼亚问题---------------\System.out.println(\、深度优先搜索\ DFS dfs=new DFS(); dfs.DF_Search(graph,0,12);

System.out.println(\、迭代加深的搜索\ IDS ids=new IDS(); ids.IDS_Search(graph,0,12,15);//深度设15 System.out.println(\、一致代价搜索\ UCS ucs=new UCS(graph,0,12); System.out.println(\、A*搜索\AXing aXing=newAXing(); aXing.A_Search(graph, graph.H,0,15);//0-15即Arad到达Hirsova }

Publicvoid show(Graph g,Stack stack){ //打印 if(stack.size()==0){

System.out.println(\路径搜索失败\

return; } result=0;

System.out.print(\访问的下标： \for(int i =0; i < stack.size(); i++){ System.out.print(\}

System.out.print(\访问过程： \ xiabiao=newint[stack.size()]; if(stack.isEmpty()){

System.out.println(\搜索失败\}else{

for(int i =0; i < stack.size(); i++){

System.out.print(\}

for(int i =0; i < stack.size()-1; i++){ result+=g.path[(Integer) stack.get(i)][(Integer) stack.get(i+1)]; }

System.out.println(\总长度为：\ g.markInit();//清空访问 } } }

PublicclassGraph{ //数组存储图 Publicint

path[][]=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[]{\\

Vilcea\ziceni\

\城市名 Publicint[]mark=newint[20];//访问标记 PublicGraph(){//得到数据 markInit(); // 访问标志初始化 }

Publicvoid markInit(){

for(int i =0; i < mark.length; i++){ mark[i]=0; } }

Publicint getFirstVex(int start){//第一个孩子，return -1表示一个孩子都没有 if(start>=0&&start

if(path[start][j]0)//有关系 return j; }

return-1; }

Publicint getNextVex(int start,int w){//下一个孩子

if(start>=0&&start=0&&w

for(int i = w+1; i < path.length; i++) //w表示图G中顶点i的第j个邻接顶点的下一个邻接顶点

if(path[start][i]0) return i; }

return-1; // 返回-1，表示后面没有邻接点了 }

Publicint getNumber(){