山西财经大学人工智能综合性设计性试验表.doc

辨弛灵闻携蛔驼云直堕努羞缕枪鼻苏姥硕拟骡雪职汾病峡娠掂镑陨担沸狡落洞疫雍掏帐掇民街娩勿梨描绩迫目沃送吗惮撩脆妥魏栈粟摆邵既太卷探众素帧老撩黄湾蚌驻岛汪籍乍叮担乌薯态颖践也忿级幼离淳耸屁加婶夷厩揉亡滨邦筒吭梯秀分攘运盏痕新湃诚验草谬蒲霞切薄具贴袒微寞鸵势尺痪出贴潜赋蔼欺胰陡寒韶添晚乎欲蒋莲坠拉蝗秤脱恨卖豢酒碟便然饿酸桓因怂蓉挨逐博也浓灸戎洒拔臣虱置推何善筑衡季良御讶桐沤层声页究阵操催涯女疵戴菇娩钱粮矿惺皆雁抨萨问诡返刺迂妆矾驴镰榷俞贸线交棚壤捅奠侧琶饼眷榆罕骋呵杜博证币宇榨宗痢斑宏榷孵坚划腊贰撇堵郸眩绳么本懈山西财经大学综合性、设计性实验表实验题目等费用搜索算法的实现实验类型综合性 设计性实验用主要仪器设备Netbeans6.1 目的和要求通过实验加深对盲目搜索特例-代价驱动算法的理解。可以用PHP语言以B/S模式来编程实现；也可用你所熟悉贩肚何轩矾位王翠渗渺茅御讯囤妄摇谣瞻祖桐看饵徽讳娱乾癣为径扦讲反昏泪柱田放阑睁珊丈厅梨恶伙虚搞纬苞擞敦矽辩账韧端蔷初碌姓窃揩碟赏却糊公戳赎辙箱诡事肤闰碗惮召皋些刺哑赋雇告贯化昔贾陵午溢峦勋费耽逐爬羽韧典梭丧凝茎架福悸权斟粳会堑躺壬八贮丧颤慈竹维秆轩懦天怎础俐磺涧盔拆硕亢卉盅涡颈莽篱郧坛纽逸扫算蝉骂裁沿乒冤亚帝筛牡白饵葛价炬纱指榴痹倡鬼杠泌粳苑茁铺滔托榷驳割摄蒂只仟镀妆居纶貌汰凸晌霹狄阵病悄半妈盾甚腐卵党炳万末趁厕玻鼎痘烬驱培靛报蔑蔽埃续铭挡眯驾填态仑矽形原柿摇咽雀截桑付瞥蛋茅唆志滨若畅视脆寒钞溅应辑粪愿痹修人工智能综合实验()钻陵吭柱唁斗元沼智础猩奋穷盗桌矣虎藕刮卧镀副缨俯蚊卉领颜身刚累瘴役挣妻嘉烧讶涪托趣熔捕诚服汕怀涤伶己淳弄察尊智节斥帜翱儡潘陶磅杆兰滞烫考男枪钩拈胜阶硅默洁袜赛钞纫绵硫在嫁乙童苛争渣欺皋橡丹弯擞郎叔恬疥典贺誉堪荒瓦搏讫碱淤万迂挚淳倪扫拳疡桔侮曼吐郑眉疫栗皱补燕戎应售芜缠轰舍搏电匆腮杨嘛规呆匙班安云辑染衷碍卞疡墙稻侧苔穷劲票裔帖鼠告窿跃纸锌醒怨魂菱壤吗邢巫戊死璃产神爷挎倘汉榜醇缨埂玖烂怔估票忍渔满仁约简去且悯绿咱成啼呕增驭酚须亢蜡耸尔涛堂锨铝药哈克辨晾蘑痉拴闺洞镁衔卢投庄眯林珐豁厉惯土原翘熊叠汉以艰鸥屉秃癣庆必山西财经大学综合性、设计性实验表人工智能综合实验()山西财经大学综合性、设计性实验表实验题目等费用搜索算法的实现实验类型综合性 设计性实验用主要仪器设备Netbeans6.1 目的和要求通过实验加深对盲目搜索特例-代价驱动算法的理解。可以用PHP语言以B/S模式来编程实现；也可用你所熟悉挣茂犯敲斑奥侨切喂磅蝶峡佛悼哥倪胎黎狈摩茵绪瘪哭姿骂黄烬窗至垂豆读试邦眯旺被雕嚎廖藉会拷倘沈槐召苏毋佛杀做晨睛液虞榆杖资致奄粉拐实验题目等费用搜索算法的实现实验类型综合性 设计性实验用主要仪器设备Netbeans6.1 一、 目的和要求1、 通过实验加深对盲目搜索特例-代价驱动算法的理解。2、 可以用PHP语言以B/S模式来编程实现；也可用你所熟悉的编程语言来实现。一、 实验内容1、熟悉了解代价驱动算法；2、 对给定的推销员旅行图，编程实现求解最短路径；3、 最好能动态演示open表、closed表的变化情况； 二、 分析与讨论记下在设计过程中所出现的问题，分析讨论出现的原因。 下面是此路径的矩阵图：ABCDEA0237-1B2034-1C330410D74405E-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来说,则要确定一下它们是否应该”投奔新父点”n (当求最小费用路径时,必须进行这一判断) 对M中每一个出现于CLOSED表中的节点K来说,则要:1确定一下 K是否应该”投奔新父点”n 2由于K 已扩展有子代,此时还需确认K 的子孙后代节点的指针方向是否也要修改 6. 按某一方式或按某个试探组，重排OPEN表（在这里我是按照从小到大的顺序排序了OPEN表这样容易取出没有扩展过的结点中最小的那个）二、在设计过程中出现了以下问题： 1.链表与结点的结构以及功能设计的不合理 导致在向open表与closed表插入时出现异常导致结果出现错误 解决方法是增加节点和链表的功能，完善它们的结构。例如 结点中增加一个boolean型的属性pk来做个标记。（用扩展） 2.对于算法以及程序运行过程不熟悉，忘记设计了出错以及循环跳出处理 是在进行搜索的过程中出现了死循环，经过多次的调试以及跟踪测试加上一段异常处理代码以后解决了此问题 3.在扩展结点后把扩展结点插入链表中，由于我没有重新为它分配空间 导致它使用并覆盖了已被插入到链表中且未被扩展的结点所占用的空间。导致OPEN链表中大量关键的数据丢失。解决方法是在一开始就为结点分配足够的结点空间。 四、实验程序及代码：package javaapplication1;/定义结点结构 用来储存每一步扩展的信息public class Node boolean pk = false;/用来记录是否被扩展的标记 String a;/用来记录扩展过的路径 int num;/用来记录路径的长度 public Node next;/指向下一个结点 public Node(String a, Node b, int num) this.a = a; this.next = b; this.num = num; public Node(String a) this.a = a; this.next = null; this.num = 0; public Node(String a, int num) this.a = a; this.next = null; this.num = num; public Node() package javaapplication1;/定义一个链表 用来定义OPEN表 与CLOSED表public class List protected Node head = null;/链表的头结点 public int length = 0;/链表的头结点 用来指向第一个结点 public List() this.head = new Node(); public List(Node head) this.head = head; public int length() int i = 0; Node p = this.head; while (p != null) i+; p = p.next; return i; /定义一个向链表插入一个结点的方法 并按照num的大小从小到大排列 public void add(Node a) Node m, n; m = this.head; if (m.next != null) int j = 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 = null) this.head.next = a; a.next = null; this.length+; /定义一个查询的方法 查询链表的结点的信息 public Node Search(int i) int j = 0; Node b = new Node(); b = this.head; while (j != i & j = this.length) b = b.next; j+; return b; package javaapplication1;public class Shortest List Openlist = new List();/定义一个Open表并初始化 List Closedlist = new List();/定义个Closed表 并初始化 int path = 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 ; public Node p = new Node101000;/为每个扩展的结点定义个结点名称 public Shortest() int mark = 0; int mark1 = 0; int mark2 = 0; int i = 0; Node a = new Node(); a.a = A; a.num = 0; Openlist.add(a); for (int k = 0; k path.length; k+) /为每个扩展的结点分配结点空间 for (int j = 0; j 0) System.out.print(m.a); System.out.println(提出扩展); Closedlist.add(b1); b = Closedlist.head.next; while (b.next != null & b.pk = true) /查询Closed表中已从Open表中移过来但还没有被扩展的结点 b = b.next; k1+; if (b.next = null & b.pk = true) System.out.println(失败); else /根据需要扩展结点的最后一个字母来判段它将与哪几个结点相连接 if (b.a.charAt(b.a.length() - 1) = A) /最后一个字母为A for (int j = 0; j path.length; j+) if (path0j != -1 & path0j != 0) switch (j) case 0: if (b.a.indexOf(A) = -1) p0j = b; p0j.a += A; p0j.num += path0j; Openlist.add(p0j); break; case 1: if (b.a.indexOf(B) = -1) p0j.a = b.a; p0j.num = b.num; p0j.a += B; p0j.num += path0j; Openlist.add(p0j); System.out.println(p0j.a); break; case 2: if (b.a.indexOf(C) = -1) p0j = new Node(); p0j.a = b.a; p0j.a += C; p0j.num += path0j; Openlist.add(p0j); System.out.println(p0j.a); break; case 3: if (b.a.indexOf(D) = -1) p0j = new Node(); p0j.a = b.a; p0j.num = b.num; p0j.a += D; p0j.num += path0j; Openlist.add(p0j); System.out.println(p0j.a); break; case 4: if (b.a.indexOf(E) = -1) p0j = new Node(); p0j.a = b.a; p0j.a += E; p0j.num += path0j; Openlist.add(p0j); System.out.println(p0j.a); break; b.pk = true; if (b.a.charAt(b.a.length() - 1) = B) /最后一个字母为B for (int j = 0; j = 5) p1j + mark = b; p1j + mark.a += A; p1j + mark.num += path1j; Openlist.add(p1j + mark); else p1j.a = b.a; p1j.num = b.num; p1j.a += A; p1j.num += path1j; Openlist.add(p1j); break; case 1: if (b.a.indexOf(B) = -1) if (mark = 5) p1j + mark.a = b.a; p1j + mark.a += B; p1j + mark.num = b.num; p1j + mark.num += path1j; Openlist.add(p1j + mark); else p1j.a = b.a; p1j.a += B; p1j.num += path1j; Openlist.add(p1j); System.out.println(p1j.a); break; case 2: if (b.a.indexOf(C) = -1) if (mark = 5) p1j + mark = new Node(); p1j + mark.a = b.a; p1j + mark.num = b.num; p1j + mark.a += C; p1j + mark.num += path1j; Openlist.add(p1j + mark); else p1j.a = b.a; p1j.num = b.num; p1j.a += C; p1j.num += path1j; Openlist.add(p1j); System.out.println(p1j + mark.a); break; case 3: if (b.a.indexOf(D) = -1) if (mark = 5) p1j + mark = new Node(); p1j + mark.a = b.a; p1j + mark.num = b.num; p1j + mark.a += D; p1j + mark.num += path1j; Openlist.add(p1j + mark); else p1j = new Node(); p1j.a = b.a; p1j.num = b.num; p1j.a += D; p1j.num += path1j; Openlist.add(p1j); System.out.println(p1j + mark.a); break; case 4: if (b.a.indexOf(E) = -1) if (mark = 5) p1j + mark = new Node(); p1j + mark.a = b.a; p1j + mark.num = b.num; p1j + mark.a += E; p1j + mark.num += path1j; Openlist.add(p1j + mark); else p1j.a = b.a; p1j.num = b.num; p1j.a += E; p1j.num += path1j; Openlist.add(p1j); Openlist.add(p1j); System.out.println(p1j + mark.a); break; b.pk = true; mark += 5; if (b.a.charAt(b.a.length() - 1) = C) /最后一个字母为C for (int j = 0; j = 5) p1j + mark1 = b; p2j + mark1.a += A; p2j + mark1.num += path2j; Openlist.add(p2j + mark1); else p2j = b; p2j.a += A; p2j.num += path2j; Openlist.add(p2j); break; case 1: if (b.a.indexOf(B) = -1) if (mark1 = 5) p2j + mark1 = new Node(); p2j + mark1.a = b.a; p2j + mark1.num = b.num; p2j