人工智能综合实验()

《人工智能综合实验()》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、山西财经大学综合性、设计性实验表实验题目等费用搜索算法的实现实验类型综合性√设计性√实验用主要仪器设备Netbeans6.1一、目的和要求1、通过实验加深对盲目搜索特例--代价驱动算法的理解。2、可以用PHP语言以B/S模式来编程实现；也可用你所熟悉的编程语言来实现。二、实验内容1、 熟悉了解代价驱动算法；2、对给定的推销员旅行图，编程实现求解最短路径；3、最好能动态演示open表、closed表的变化情况；三、分析与讨论记下在设计过程中所出现的问题，分析讨论出现的原因。下面是此路径的矩阵图：ABCDEA0237-1B2034-1C330410D7

2、4405E-1-11050一、一般的图搜索过程如下：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来说,则要确定一下它们是否应该”投奔新

3、父点”n(当求最小费用路径时,必须进行这一判断)对M中每一个出现于CLOSED表中的节点K来说,则要:1．确定一下K是否应该”投奔新父点”n2．由于K已扩展有子代,此时还需确认K的子孙后代节点的指针方向是否也要修改6.按某一方式或按某个试探组，重排OPEN表（在这里我是按照从小到大的顺序排序了OPEN表这样容易取出没有扩展过的结点中最小的那个）二、在设计过程中出现了以下问题：1.链表与结点的结构以及功能设计的不合理导致在向open表与closed表插入时出现异常导致结果出现错误解决方法是增加节点和链表的功能，完善它们的结构。例如结点中增加一个bo

4、olean型的属性pk来做个标记。（用扩展）2.对于算法以及程序运行过程不熟悉，忘记设计了出错以及循环跳出处理是在进行搜索的过程中出现了死循环，经过多次的调试以及跟踪测试加上一段异常处理代码以后解决了此问题3.在扩展结点后把扩展结点插入链表中，由于我没有重新为它分配空间导致它使用并覆盖了已被插入到链表中且未被扩展的结点所占用的空间。导致OPEN链表中大量关键的数据丢失。解决方法是在一开始就为结点分配足够的结点空间。四、实验程序及代码：packagejavaapplication1;//定义结点结构用来储存每一步扩展的信息publicclassNod

5、e{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

6、=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

7、){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>m.next.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(this.head.next

8、==null){this.head.next=a;a.next=null;}this.length++;}//定义一个查询