人工智能综合实验()

山西财经大学综合性 设计性实验表山西财经大学综合性 设计性实验表 实验题目 等费用搜索算法的实现等费用搜索算法的实现 实验类型综合性 设计性 实验用主要仪器设备Netbeans6 1 一 目的和要求 1 通过实验加深对盲目搜索特例 代价驱动算法的理解 2 可以用 PHP 语言以 B S 模式来编程实现 也可用你所熟悉的编程语言来实现 二 实验内容 1 熟悉了解代价驱动算法 2 对给定的推销员旅行图 编程实现求解最短路径 3 最好能动态演示 open 表 closed 表的变化情况 三 分析与讨论 记下在设计过程中所出现的问题 分析讨论出现的原因 下面是此路径的矩阵图 ABCDE A0237 1 B2034 1 C330410 D74405 E 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 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 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 Node 10 1000 为每个扩展的结点定义个结点名称 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 k1 if b next null else 根据需要扩展结点的最后一个字母来判段它将与哪几个结点相连接 if b a charAt b a length 1 A 最后一个字母为 A for int j 0 j path length j if path 0 j 1 p 0 j a A p 0 j num path 0 j Openlist add p 0 j break case 1 if b a indexOf 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 System out println p 0 j a break case 2 if b a indexOf C 1 p 0 j new Node p 0 j a b a p 0 j a C p 0 j num path 0 j Openlist add p 0 j System out println p 0 j a break case 3 if b a indexOf D 1 p 0 j new Node 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 System out println p 0 j a break case 4 if b a indexOf E 1 p 0 j new Node p 0 j a b a p 0 j a E p 0 j num path 0 j Openlist add p 0 j System out println p 0 j a break b pk true if b a charAt b a length 1 B 最后一个字母为 B for int j 0 j 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 case 1 if b a indexOf 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 System out println p 1 j a break case 2 if b a indexOf C 1 if mark 5 p 1 j mark new Node 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 System out println p 1 j mark a break case 3 if b a indexOf D 1 if mark 5 p 1 j mark new Node 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 new Node 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 System out println p 1 j mark a break case 4 if b a indexOf E 1 if mark 5 p 1 j mark new Node 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 System out println p 1 j mark a break b pk true mark 5 if b a charAt b a length 1 C 最后一个字母为 C for int j 0 j 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 case 1 if b a indexOf B 1 if mark1 5 p 2 j mark1 new Node 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 System out println p 2 j mark1 a break case 2 if b a indexOf C 1 System out println 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 System out println Openlist head next next next a break case 3 if b a indexOf D 1 if mark1 5 p 2 j mark1 new Node 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 System out println p 2 j mark1 a break case 4 if b a indexOf E 1 if mark1 5 p 2 j mark1 new Node 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 System out println p 2 j mark1 a break b pk true mark1 5 if b a charAt b a length 1 D 最后一个字母为 D for int j 0 j 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 case 1 if b a indexOf B 1 if mark2 5 p 3 j mark2 new Node 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 System out println p 3 j mark2 a break case 2 if b a indexOf C 1 if mark2 5 p 3 j mark2 new Node 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 j Openlist add p 3 j mark2 else p 3 j a b a p 3 j num b num p 3 j a C p 3 j num path 3 j Openlist add p 3 j System out println p 3 j mark2 a break case 3 if b a indexOf D 1 if mark2 5 p 3 j mark2 b p 3 j mark2 a D p 3 j mark2 num path 3 j Openlist add p 3 j mark2 else p 3 j b p 3 j a D p 3 j num path 3 j Openlist add p 3 j System out println p 3 j mark a break case 4 if b a indexOf E 1 if mark2 5 p 3 j mark2 new Node p 3 j mark2 a b a p 3 j mark2 num b num p 3 j mark2 a E p 3 j mark2 num path 3 j Openlist add p 3 j mark2 else p 3 j new Node p 3 j a b a p 3 j num b num p 3 j a E p 3 j num path 3 j Openlist add p 3 j System out println p 3 j mark2 a break b pk true mark2 5 if b a charAt b a length 1 E 最后一个字母为 E 则查询结束 System out print 最短路径为 System out println b a System out print 值为 System out println b num System out print Open 表 System out println Close 表 for int i1 1 i1 Openlist length i1 System out println Openlist Search i1 a Openlist Search i1 num Openlist Search i1 pk for int i1 1 i1 Closedlist length i1 System out println Closedlist Search i1 a Closedlist Search i1 num Closedlist Search i1 pk System exit 0 break b pk true m pk true i public static void main String a new