《广工人工智能搜索习题课件》由会员分享，可在线阅读，更多相关《广工人工智能搜索习题课件（48页珍藏版）》请在金锄头文库上搜索。
1、1、迷宫问题如下，F是入口，B是出口，试采用深度优先搜索算法进行求解。,F,G,H,E,C,A,D,B,深度优先搜索结果：搜索到的路径为粗线所示,F,G,H,E,C,A,B,1,2,3,4,5,6,OPEN:G CLOSED:F,OPEN:H,E CLOSED:F,G,OPEN:E CLOSED:F,G,H,OPEN:A,C CLOSED:F,G,H,E,OPEN:B,C CLOSED:F,G,H,E,A,OPEN:C CLOSED:F,G,H,E,A,2、上述问题采用宽度优先搜索算法进行求解。,F,G,H,E,C,A,D,B,F,G,H,E,C,A,D,B,1,2,3,4,5,6,7,宽度优
2、先搜索：搜索到的路径为粗线所示。,8,OPEN:G CLOSED:F,OPEN:E,H CLOSED:F,G,OPEN:H,C,A CLOSED:E,G,E,OPEN:C,A CLOSED:F,G,E,H,OPEN:A,D CLOSED:F,G,E,H,C,OPEN:D,B CLOSED:F,G,E,H,C,A,OPEN:B CLOSED:F,G,E,H,C,A,D,OPEN: CLOSED:F,G,E,H,C,A,D,3、对左图采用分支界限法(均一代价法)进行搜索求解。,LISP算法解析,分支界限搜索树,分支搜索路径过程,4、对上题采用动态规划法搜索解决。 动态规划法实际上是分支界限法的改进
3、。对某个中间节点来说，也许有多条路径可达到它，但只保留耗散值最小的那条路径。,3、用A*算法求解下列八数码魔方，启发函数h*(n)分别采用： 1) h=0; 2) h为放错的棋子数； 3) h为用曼哈顿距离的和。,5,6,7,4,8,1,3,2,5,6,7,4,8,3,2,1,解题分析：,由于A*算法的估价函数为： f*(n)=g*(n)+h*(n) 其中，g*(n)代表从初始点到n的路径代价和； h*(n)代表从n开始到目标的距离估算值。 当h*(n)=0时，则A*算法的估价函数只剩下g*(n)，即为均一代价算法。,1) h=0, 即为均一代价搜索算法(粗线表示搜索到的路径，小括号内的数字为
4、该节点的代价值),1,A,2,3,4,5,6,7,8,9,10,11,1,2,3,8,4,5,6,7,B,C,D,目标,OPEN:B,C,D CLOSED:A,2)h为放错的棋子数，则f*(n)=g*(n)+h*(n)。,1,2,3,4,(3=0+3),(3=1+2),(5=1+4),(4=1+3),(3=2+1),(5=3+2),(3=3+0),粗线表示搜索到的路径，小括号内的数字为该节点的估价函数值,A,OPEN:B(3), D(4), C(5) CLOSED:A(3),OPEN:E(3), D(4), C(5) CLOSED:A(3),B(3),B,C,D,E,F,G,OPEN:G(3)
5、, D(4), C(5),F(5) CLOSED:A(3),B(3),E(3),OPEN:D(4), C(5),F(5) CLOSED:A(3),B(3),E(3),3) h是节点中每个棋子与目标位置的最短距离(曼哈顿距离)之和。,1,2,3,4,(3=0+3),(3=1+2),(5=1+4),(5=1+4),(3=2+1),(5=3+2),(3=3+0),粗线表示搜索到的路径，小括号内的数字为该节点的估价函数值,OPEN:B(3), D(4), C(5) CLOSED:A(3),A,B,C,D,OPEN:E(3),D(4), C(5) CLOSED:A(3),B(3),OPEN:G(3),
6、D(4), C(5),F(5) CLOSED:A(3),B(3),E(3),E,F,G,OPEN: D(4), C(5),F(5) CLOSED:A(3),B(3),E(3),4、对右图所示的状态空间图进行： 1) 深度优先搜索; 2) 宽度优先搜索； 3) 均一代价搜索； 4) 最佳优先搜索； 5) A*搜索。 其中A为起始节点，E为目标节点，各节点的启发值表示在括号内。,F,G,H,E,C,A,D,B,4,2,3,4,8,2,4,3,3,8,5,(15),(14),(10),(2),(11),(9),(5),(0),1) 深度优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,搜
7、索出的路径为： ABCDE,5,OPEN:B,H CLOSED:A,OPEN:C,H CLOSED:A,B,OPEN:D,G,H CLOSED:A,B,C,OPEN:E,F,G,H CLOSED:A,B,C,D,OPEN:F,G,H CLOSED:A,B,C,D,2) 宽度优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,5,6,7,搜索到的路径为：ABC DE,8,OPEN:B,H CLOSED:A,OPEN:H,C CLOSED:A,B,OPEN:C,G CLOSED:A,B,H,OPEN:G,D CLOSED:A,B,H,C,OPEN:D,F CLOSED:A,B,H,C,G
8、,OPEN:F,E CLOSED:A,B,H,C,G,D,OPEN:E CLOSED:A,B,H,C,G,D,F,OPEN: CLOSED:A,B,H,C,G,D,F,3) 均一代价搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,5,6,7,搜索出的路径为： AHGFDE，整条路径的代价和为15。,8,OPEN:B(3),H(4) CLOSED:A(0),OPEN:H(4),C(7) CLOSED:A(0),B(3),OPEN:G(6),C(7) CLOSED:A(0),B(3),H(4),OPEN:C(7),F(10),D(14) CLOSED:A(0),B(3),H(4),G(6
9、),OPEN:F(10),D(14) CLOSED:A(0),B(3), H(4),G(6),C(7),OPEN:D(1413) CLOSED:A(0),B(3),H(4),G(6),C(7),F(10),OPEN:E(15) CLOSED:A(0),B(3),H(4),G(6),C(7),F(10),D(14 13),OPEN: CLOSED:A(0),B(3),H(4),G(6),C(7),F(10),D(1413),4) 最佳优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,搜索出的路径为： AHGDE，整条路径的代价和为16。,OPEN:H(11),B(14) CLOSED
10、:A(15),OPEN:G(9),B(14) CLOSED:A(15),H(11),OPEN:D(2),F(5),C(10),B(14) CLOSED:A(15),H(11),G(9),OPEN:E(0),F(5),C(10),B(14) CLOSED:A(15),H(11),G(9),D(2),5,OPEN:F(5),C(10),B(14) CLOSED:A(15),H(11),G(9),D(2),5) A*算法,F,G,H,E,A,B,1,2,3,4,C,D,5,搜索出的路径为： AHGDE，整条路径的代价和为15。,6,OPEN:H(15),B(17) CLOSED:A(15),OPEN
11、:G(15),B(17) CLOSED:A(15),H(15),OPEN:F(15),D(16),B(17),C(19) CLOSED:A(15),H(15),G(15),OPEN:D(1615),B(17),C(19) CLOSED:A(15),H(15),G(15),F(15),OPEN:E(15),B(17),C(19) CLOSED:A(15),H(15),G(15),F(15), D(1615),OPEN:B(17),C(19) CLOSED:A(15),H(15),G(15),F(15), D(1615),5、对右图所示的状态空间图用A*算法进行搜索。 其中A为起始节点，E为目标节
12、点，各节点的启发值表示在括号内。,E,C,A,D,B,1,1,9,6,1,20,(14),(20),(4),(8),4,OPEN表,CLOSED表,A(20),B(15),1,C(14),D(13),OPEN表,CLOSED表,A(20),B(15),1,C(14),D(13),E(29),2,OPEN表,CLOSED表,A(20),B(15),1,C(14),D(1311),E(29),2,3,OPEN表,CLOSED表,A(20),B(15),1,C(14),D(1311),E(2927),2,3,4,OPEN表,CLOSED表,A(20),B(15),1,C(1410),D(13119)
13、,E(2927),2,3,4,5,OPEN表,CLOSED表,A(20),B(15),1,C(1410),D(13119),E(292725),2,3,4,5,6,OPEN表,CLOSED表,A(20),B(15),1,C(1410),D(13119),E(292725),2,3,4,5,6,7,OPEN表,CLOSED表,E(29272523),A(20),B(15),1,2,C(1410),D(131197),3,4,5,6,7,8,搜索出的路径为： ABCDE，整条路径的代价和为23。,9,对下图所示的状态空间图进行：(1) 深度优先搜索；(2) 宽度优先搜索；（3）均一代价搜索；(4)
14、 A*算法搜索。（图中A为初始节点，F 为目标节点，各节点的启发值标注在小括号内）。给出搜索过程及搜索出的最佳路径，并标注各节点的估价函数值。,6. 利用-剪枝法对下图的博弈树进行搜索。,6,1,2,5,3,4,1,6,5,1,1,7,2,4,3,2,6,1,2,5,3,4,1,6,1,1,=1,6,1,2,5,3,4,1,6,1,1,=2,=1,2,=2,2,6,1,2,5,3,4,1,6,剪枝,1,1,=1,2,=2,=2,2,3,=3,3,=2,2,5,1,1,7,2,4,3,2,2,5,=1,1,剪枝,1,=1,1,5,1,1,7,2,4,3,2,2,5,=1,1,剪枝,1,=1,1,剪枝,=2,6,1,2,5,3,4,1,6,5,1,1,7,2,4,3,2,1,剪枝,两次剪枝,=1,2,=2,1,=2,2,3,=3,3,=2,2,5,=1,1,1,=1,1,
