人工智能概论通识课 第3章 图有哪些信誉好的足球投注网站与问题求解.ppt

… 8组规则: r22: (X8==0)?( X1==n)? (X8=n) ?( X1=0) r23: (X8==0)?( X0==n)? (X8=n) ?( X0=0) r24: (X8==0)?( X7==n)? (X8=n) ?( X7=0) 于是, 八数码问题的状态图可表示为 ({So}, {r1, r2, …, r24}, {Sg}) 　　例 3-6 梵塔问题。传说在印度的贝那勒斯的圣庙中,主神梵天做了一个由64个大小不同的金盘组成的“梵塔”, 并把它穿在一个宝石杆上。另外, 旁边再插上两个宝石杆。 然后, 他要求僧侣们把穿在第一个宝石杆上的64个金盘全部搬到第三个宝石杆上。 搬动金盘的规则是：一次只能搬一个；不允许将较大的盘子放在较小的盘子上。于是,梵天预言：一旦64个盘子都搬到了3号杆上, 世界将在一声霹雳中毁灭。 盘子的搬动次数： 264-1＝18 446 744 073 709 511 615 　二阶梵塔问题 设有三根宝石杆,在1号杆上穿有A、B两个金盘, A小于B, A位于B的上面。用二元组(SA,SB)表示问题的状态, SA表示金盘A所在的杆号, SB表示金盘B所在的杆号, 这样, 全部可能的状态有9种, 可表示如下： (1, 1), (1, 2), (1, 3) (2, 1), (2, 2), (2, 3) (3, 1), (3, 2), (3, 3) 如图3-10所示。 图 3-10 二阶梵塔的全部状态 　　这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘从第i号杆移到第j号杆上;B(i,j)表示把B盘从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是： A(1,2),　A(1,3),　A(2,1),　A(2,3),　A(3,1),　A(3,2) B(1,2),　B(1,3),　B(2,1),　B(2,3),　B(3,1),　B(3,2) 规则的具体形式应是： IF〈条件〉THEN A(i,j) IF〈条件〉THEN B(i, j) 　　这样由题意,问题的初始状态为(1, 1),目标状态为(3, 3), 则二阶梵塔问题可用状态图表示为 ({(1, 1)}, {A(1, 2), …, B(3, 2)}, {(3, 3)}) 　　由这9种可能的状态和12种操作, 二阶梵塔问题的状态空间图如图3-11所示。 图 3-11 二阶梵塔状态空间图 　 例 3-7 旅行商问题(Traveling-Salesman Problem,TSP)。 设有n个互相可直达的城市, 某推销商准备从其中的A城出发,周游各城市一遍, 最后又回到A城。要求为该推销商规划一条最短的旅行路线。 该问题的状态为以A打头的已访问过的城市序列: A … So: A。 Sg: A, …, A。 其中“…”为其余n-1个城市的一个序列。 　　状态转换规则： 　　规则1 如果当前城市的下一个城市还未去过, 则去该城市,并把该城市名排在已去过的城市名序列后端。 　　规则2 如果所有城市都去过一次, 则从当前城市返回A城, 把A也添在去过的城市名序列后端。 3.3.2 状态图问题求解程序举例 例 3-8 下面是一个通用的状态图有哪些信誉好的足球投注网站程序。对于求解的具体问题，只需将其状态图的程序表示并入该程序即可。 /*状态图有哪些信誉好的足球投注网站通用程序*/ DOMAINS state=领域说明 %例如:state=symbol DATABASE-mydatabase 　　 open(state,integer) 　%用动态数据库实现OPEN表 　　closed(integer,state,integer) %和CLOSED表 　　 res(state) 　　 open1(state,integer) 　　min(state,integer) 　　mark(state) 　　 fail_ PREDICAT