人工智能综合实验.docx

人工智能综合实验.docx

《人工智能综合实验.docx》由会员分享，可在线阅读，更多相关《人工智能综合实验.docx（22页珍藏版）》请在冰点文库上搜索。

人工智能综合实验

山西财经大学综合性、设计性实验表

实验题目

等费用搜索算法的实现

实验类型

综合性√设计性√

实验用主要仪器设备

Netbeans6.1

一、目的和要求

1、通过实验加深对盲目搜索特例--代价驱动算法的理解。

2、可以用PHP语言以B/S模式来编程实现；也可用你所熟悉的编程语言来实现。

二、实验内容

1、 熟悉了解代价驱动算法；

2、对给定的推销员旅行图，编程实现求解最短路径；

3、最好能动态演示open表、closed表的变化情况；

三、分析与讨论

记下在设计过程中所出现的问题，分析讨论出现的原因。

下面是此路径的矩阵图：

A

B

C

D

E

A

0

2

3

7

-1

B

2

0

3

4

-1

C

3

3

0

4

10

D

7

4

4

0

5

E

-1

-1

10

5

0

一、一般的图搜索过程如下：

GRAPHSEARCH过程

1.将始点S放到OPEN表中。

2.OPEN表为空?

为空则失败退出。

否则则进行第三步。

3．将OPEN表中的第一个节点n取出，放入CLOSED表。

n为目标点否?

如果是目标节点则输出解并成功退出

否则进行下一步操作。

4.扩展节点n，即生成非n之祖先的后继节点集合M（根据结点n中的字母来扩展其后继结点）

5.将M中那些既未在OPEN表,也没在CLOSED表中出现过的节点加入OPEN表,并逐一设置指向n的指针

对M中每一个出现于OPEN中的节点K来说,则要确定一下它们是否应该”投奔新父点”n（当求最小费用路径时,必须进行这一判断）

对M中每一个出现于CLOSED表中的节点K来说,则要:

1．确定一下K是否应该”投奔新父点”n

2．由于K已扩展有子代,此时还需确认K的子孙后代节点的指针方向是否也要修改

6.按某一方式或按某个试探组，重排OPEN表（在这里我是按照从小到大的顺序排序了OPEN表这样容易取出没有扩展过的结点中最小的那个）

二、在设计过程中出现了以下问题：

1.链表与结点的结构以及功能设计的不合理导致在向open表与closed表插入时出现异常导致结果出现错误

解决方法是增加节点和链表的功能，完善它们的结构。

例如结点中增加一个boolean型的属性pk来做个标记。

（用扩展）

2.对于算法以及程序运行过程不熟悉，忘记设计了出错以及循环跳出处理是在进行搜索的过程中出现了死循环，经过多次的调试以及跟踪测试加上一段异常处理代码以后解决了此问题

3.在扩展结点后把扩展结点插入链表中，由于我没有重新为它分配空间导致它使用并覆盖了已被插入到链表中且未被扩展的结点所占用的空间。

导致OPEN链表中大量关键的数据丢失。

解决方法是在一开始就为结点分配足够的结点空间。

四、实验程序及代码：

packagejavaapplication1;

//定义结点结构用来储存每一步扩展的信息

publicclassNode{

booleanpk=false;//用来记录是否被扩展的标记

Stringa;//用来记录扩展过的路径

intnum;//用来记录路径的长度

publicNodenext;//指向下一个结点

publicNode（Stringa,Nodeb,intnum）{

this.a=a;

this.next=b;

this.num=num;

}

publicNode（Stringa）{

this.a=a;

this.next=null;

this.num=0;

}

publicNode（Stringa,intnum）{

this.a=a;

this.next=null;

this.num=num;

}

publicNode（）{

}

}

packagejavaapplication1;

//定义一个链表用来定义OPEN表与CLOSED表

publicclassList{

protectedNodehead=null;//链表的头结点

publicintlength=0;//链表的头结点用来指向第一个结点

publicList（）{

this.head=newNode（）;

}

publicList（Nodehead）{

this.head=head;

}

publicintlength（）{

inti=0;

Nodep=this.head;

while（p!

=null）{

i++;

p=p.next;

}

returni;

}

//定义一个向链表插入一个结点的方法并按照num的大小从小到大排列

publicvoidadd（Nodea）{

Nodem,n;

m=this.head;

if（m.next!

=null）{

intj=0;

while（m.next!

=null&&a.num>&&j<=this.length）{

m=m.next;

j++;

}

if（m.next==null）{

m.next=a;

a.next=null;

}else{

a.next=m.next;

m.next=a;

}

}

if（==null）{

=a;

a.next=null;

}

this.length++;

}

//定义一个查询的方法查询链表的结点的信息

publicNodeSearch（inti）{

intj=0;

Nodeb=newNode（）;

b=this.head;

while（j!

=i&&j<=this.length）{

b=b.next;

j++;

}

returnb;

}

}

packagejavaapplication1;

publicclassShortest{

ListOpenlist=newList（）;//定义一个Open表并初始化

ListClosedlist=newList（）;//定义个Closed表并初始化

intpath[][]={{0,2,3,7,-1},//路径的矩阵用来记录每段的权值

{2,0,3,4,-1},

{3,3,0,4,10},

{7,4,4,0,5},

{-1,-1,10,5,0}

};

publicNodep[][]=newNode[10][1000];//为每个扩展的结点定义个结点名称

publicShortest（）{

intmark=0;

intmark1=0;

intmark2=0;

inti=0;

Nodea=newNode（）;

a.a="A";

a.num=0;

Openlist.add（a）;

for（intk=0;k

for（intj=0;j

p[k][j]=newNode（）;

}

}

Nodem=newNode（）;

while（!

=null）{//开始进入查询的循环中

intk1=0;

intk=0;

m=;

while（m.next!

=null&&m.pk==true）{//查询在Open链表中未被提出扩展中的最小结点提出扩展

m=m.next;

k++;

}

if（m.next==null&&m.pk==true）{

"失败"）;

}

Nodeb=newNode（）;

Nodeb1=newNode（m.a,m.num）;//把需要提出扩展结点的信息赋给具有传递信息的结点b1

m.pk=true;

if（i>0）{

;

"提出扩展"）;

}

Closedlist.add（b1）;

b=;

while（b.next!

=null&&b.pk==true）{//查询Closed表中已从Open表中移过来但还没有被扩展的结点

b=b.next;

k1++;

}

if（b.next==null&&b.pk==true）{

"失败"）;

}else{//根据需要扩展结点的最后一个字母来判段它将与哪几个结点相连接

if（-1）=='A'）{//最后一个字母为A

for（intj=0;j

if（path[0][j]!

=-1&&path[0][j]!

=0）{

switch（j）{

case0:

if（"A"）==-1）{

p[0][j]=b;

p[0][j].a+="A";

p[0][j].num+=path[0][j];

Openlist.add（p[0][j]）;

}

break;

case1:

if（"B"）==-1）{

p[0][j].a=b.a;

p[0][j].num=b.num;

p[0][j].a+="B";

p[0][j].num+=path[0][j];

Openlist.add（p[0][j]）;

;

}

break;

case2:

if（"C"）==-1）{

p[0][j]=newNode（）;

p[0][j].a=b.a;

p[0][j].a+="C";

p[0][j].num+=path[0][j];

Openlist.add（p[0][j]）;

;

}

break;

case3:

if（"D"）==-1）{

p[0][j]=newNode（）;

p[0][j].a=b.a;

p[0][j].num=b.num;

p[0][j].a+="D";

p[0][j].num+=path[0][j];

Openlist.add（p[0][j]）;

;

}

break;

case4:

if（"E"）==-1）{

p[0][j]=newNode（）;

p[0][j].a=b.a;

p[0][j].a+="E";

p[0][j].num+=path[0][j];

Openlist.add（p[0][j]）;

;

}

break;

}

}

}

b.pk=true;

}

if（-1）=='B'）{//最后一个字母为B

for（intj=0;j

if（path[1][j]!

=-1&&path[1][j]!

=0）{

switch（j）{

case0:

if（"A"）==-1）{

if（mark>=5）{

p[1][j+mark]=b;

p[1][j+mark].a+="A";

p[1][j+mark].num+=path[1][j];

Openlist.add（p[1][j+mark]）;

}else{

p[1][j].a=b.a;

p[1][j].num=b.num;

p[1][j].a+="A";

p[1][j].num+=path[1][j];

Openlist.add（p[1][j]）;

}

}

break;

case1:

if（"B"）==-1）{

if（mark>=5）{

p[1][j+mark].a=b.a;

p[1][j+mark].a+="B";

p[1][j+mark].num=b.num;

p[1][j+mark].num+=path[1][j];

Openlist.add（p[1][j+mark]）;

}else{

p[1][j].a=b.a;

p[1][j].a+="B";

p[1][j].num+=path[1][j];

Openlist.add（p[1][j]）;

}

;

}

break;

case2:

if（"C"）==-1）{

if（mark>=5）{

p[1][j+mark]=newNode（）;

p[1][j+mark].a=b.a;

p[1][j+mark].num=b.num;

p[1][j+mark].a+="C";

p[1][j+mark].num+=path[1][j];

Openlist.add（p[1][j+mark]）;

}else{

p[1][j].a=b.a;

p[1][j].num=b.num;

p[1][j].a+="C";

p[1][j].num+=path[1][j];

Openlist.add（p[1][j]）;

}

+mark].a）;

}

break;

case3:

if（"D"）==-1）{

if（mark>=5）{

p[1][j+mark]=newNode（）;

p[1][j+mark].a=b.a;

p[1][j+mark].num=b.num;

p[1][j+mark].a+="D";

p[1][j+mark].num+=path[1][j];

Openlist.add（p[1][j+mark]）;

}else{

p[1][j]=newNode（）;

p[1][j].a=b.a;

p[1][j].num=b.num;

p[1][j].a+="D";

p[1][j].num+=path[1][j];

Openlist.add（p[1][j]）;

}

+mark].a）;

}

break;

case4:

if（"E"）==-1）{

if（mark>=5）{

p[1][j+mark]=newNode（）;

p[1][j+mark].a=b.a;

p[1][j+mark].num=b.num;

p[1][j+mark].a+="E";

p[1][j+mark].num+=path[1][j];

Openlist.add（p[1][j+mark]）;

}else{

p[1][j].a=b.a;

p[1][j].num=b.num;

p[1][j].a+="E";

p[1][j].num+=path[1][j];

Openlist.add（p[1][j]）;

}

Openlist.add（p[1][j]）;

+mark].a）;

}

break;

}

}

}

b.pk=true;

mark+=5;

}

if（-1）=='C'）{//最后一个字母为C

for（intj=0;j

if（path[2][j]!

=-1&&path[2][j]!

=0）{

switch（j）{

case0:

if（"A"）==-1）{

if（mark1>=5）{

p[1][j+mark1]=b;

p[2][j+mark1].a+="A";

p[2][j+mark1].num+=path[2][j];

Openlist.add（p[2][j+mark1]）;

}else{

p[2][j]=b;

p[2][j].a+="A";

p[2][j].num+=path[2][j];

Openlist.add（p[2][j]）;

}

}

break;

case1:

if（"B"）==-1）{

if（mark1>=5）{

p[2][j+mark1]=newNode（）;

p[2][j+mark1].a=b.a;

p[2][j+mark1].num=b.num;

p[2][j+mark1].a+="B";

p[2][j+mark1].num+=path[2][j];

Openlist.add（p[2][j+mark1]）;

}else{

p[2][j].a=b.a;

p[2][j].num=b.num;

p[2][j].a+="B";

p[2][j].num+=path[2][j];

Openlist.add（p[2][j]）;

}

+mark1].a）;

}

break;

case2:

if（"C"）==-1）{

"zou1"）;

if（mark1>=5）{

p[1][j+mark1].a=b.a;

p[1][j+mark1].num=b.num;

p[2][j+mark1].a+="C";

p[2][j+mark1].num+=path[1][j];

Openlist.add（p[2][j+mark1]）;

}else{

p[2][j].a=b.a;

p[2][j].num=b.num;

p[2][j].a+="C";

p[2][j].num+=path[2][j];

Openlist.add（p[2][j]）;

}

;

}

break;

case3:

if（"D"）==-1）{

if（mark1>=5）{

p[2][j+mark1]=newNode（）;

p[2][j+mark1].a=b.a;

p[2][j+mark1].num=b.num;

p[2][j+mark1].a+="D";

p[2][j+mark1].num+=path[2][j];

Openlist.add（p[2][j+mark1]）;

}else{

p[2][j].a=b.a;

p[2][j].num=b.num;

p[2][j].a+="D";

p[2][j].num+=path[2][j];

Openlist.add（p[2][j]）;

}

+mark1].a）;

}

break;

case4:

if（"E"）==-1）{

if（mark1>=5）{

p[2][j+mark1]=newNode（）;

p[2][j+mark1].a=b.a;

p[2][j+mark1].num=b.num;

p[2][j+mark1].a+="E";

p[2][j+mark1].num+=path[2][j];

Openlist.add（p[2][j+mark1]）;

}else{

p[2][j].a=b.a;

p[2][j].num=b.num;

p[2][j].a+="E";

p[2][j].num+=path[2][j];

Openlist.add（p[2][j]）;

}

Openlist.add（p[2][j]）;

+mark1].a）;

}

break;

}

}

}

b.pk=true;

mark1+=5;

}

if（-1）=='D'）{//最后一个字母为D

for（intj=0;j

if（path[3][j]!

=-1&&path[3][j]!

=0）{

switch（j）{

case0:

if（"A"）==-1）{

if（mark2>=5）{

p[3][j+mark2]=b;

p[3][j+mark2].a+="A";

p[3][j+mark2].num+=path[3][j];

Openlist.add（p[3][j+mark2]）;

}else{

p[3][j]=b;

p[3][j].a+="A";

p[3][j].num+=path[3][j];

Openlist.add（p[3][j]）;

}

}

break;

case1:

if（"B"）==-1）{

if（mark2>=5）{

p[3][j+mark2]=newNode（）;

p[3][j+mark2].a=b.a;

p[3][j+mark2].num=b.num;

p[3][j+mark2].a+="B";

p[3][j+mark2].num+=path[3][j];

Openlist.add（p[3][j+mark2]）;

}else{

p[3][j].a=b.a;

p[3][j].num=b.num;

p[3][j].a+="B";

p[3][j].num+=path[3][j];

Openlist.add（p[3][j]）;

}

+mark2].a）;

}

break;

case2:

if（"C"）==-1）{

if（mark2>=5）{

p[3][j+mark2]=newNode（）;

p[3][j+mark2].a=b.a;

p[3][j+mark2].num=b.num;

p[3][j+mark2].a+="C";

p[3][j+mark2].num+=path[3][