《人工智能全局择优搜索》由会员分享,可在线阅读,更多相关《人工智能全局择优搜索(1页珍藏版)》请在金锄头文库上搜索。
1、状态定义:S=aij33aij1,2,3,4,5,6,7,8初态:S0终态:Sg算符定义:算符集F=F1,F2,F3,F4空格左移F1;空格上移F2;空格右移F3;空格下移F4应用全局择优搜索策略生成搜索树:估计函数:fj = gj + hj代价函数 gj = gi + c(i,j) 由于所有算符的代价c(i,j)=1,故gj = gi + 1=djf(x)=d(x)+h(x)其中:d(x)表示节点x的深度,h(x)表示节点x的棋局与目标节点棋局位置不相同的棋子数目。 open = ( 1 (4) )Loop1: closed = ( 1 (4) ) open = ( 3 (4) , 2 (6
2、) , 4(6)Loop2: closed = ( 1 (4) , 3 (4) ) open = ( 5 (5) , 6 (5) , 2(6) , 4(6) , 7(6)Loop3: closed = ( 1 (4) , 3 (4) , 5 (5) ) open = ( 6(5) , 2(6) , 4(6) , 7(6) , 8(6) , 9(7)Loop4: closed = ( 1 (4) , 3 (4) , 5(5), 6(5) open = ( 10(5) , 2(6) , 4(6) , 7(6) , 8(6) , 9(7) , 11(7)Loop5: closed = ( 1 (4)
3、 , 3 (4) , 5 (5) , 6 (5) , 10(5) open = ( 12(5) , 2(6) , 4(6) , 7(6) , 8(6) , 9(7) , 11(7)Loop6: closed = ( 1 (4) , 3 (4) , 5 (5) , 6 (5) , 10(5) , 12(5) open = ( 13(5) , 2(6) , 4(6) , 7(6) , 8(6) , 9(7) , 11(7) , 4(7)Loop7: closed = ( 1 (4) , 3 (4) , 5 (5) , 6 (5) , 10(5) , 12(5) , 13(5)S13是目标状态,故算法成功终止。1 / 1