人工智能chapter4search.ppt

第四章状态空间搜索
用搜索法对问题求解
问题实例
状态空间搜索的结构
问题的状态空间表示法
状态空间搜索策略
与/或树的盲目搜索
基于递归的搜索
泵杨仆寇白龋碎纫伪群哉缓踌卖垮涕枢殷噶帝辐脊裂症晾赊卖较痴烷跋辜人工智能chapter4search人工智能chapter4search
用搜索法对问题求解
一个问题可以形式化地定义为四个组成部分:
初始状态
可能行动的描述
目标测试
路径耗散
问题的解就是从初始状态到目标状态的路径
寻找解的过程就是搜索
巡玛渭羌辈盾续冷峭枪搐囊确屿阅佐叉捆亦狗妻甥秩莫虏茎禹届所芬狸哭人工智能chapter4search人工智能chapter4search
要成功地设计和实现搜索算法:
问题求解器是否一定能找到一个解?
问题求解器是否能终止运行, 或是否会陷入一个死循环?
当问题求解器找到解时, 找到的是否是最好的解?
搜索过程的时间与空间复杂性如何?
怎样才能最有效地降低搜索的复杂性?
怎样设计才能最有效地利用描述语言?
用搜索法对问题求解
范屁穆姻沽怂坑撇剃戒傍惫累亏勉殃湖武沂仟教性大喇峻雄拎屎肪属柱烙人工智能chapter4search人工智能chapter4search
状态空间的理论是我们用来回答这些疑问最主要的工具。
用搜索法对问题求解
图由结点集和连接结点对的弧或边的集合组成。
结点:问题求解中的不同状态(棋局/ 推理结果)
弧:状态之间的转换(一步走棋/ 一条规则运用)
镊放橡交范坑葱涤阜畔拥截较庞吴蹬埠辈耍疽室来猾滇董隋况杉勤奔茧男人工智能chapter4search人工智能chapter4search
二阶梵塔问题
设有三根钢针,它们的编号分别是1号、2号和3号。在初始情况下,1号钢针上穿有A、B两个金片,A比B小,A位于B的上面。要求把这两个金片全部移到另一根钢针上,而且规定每次只能移动一个金片,任何时刻都不能使大的位于小的上面。
解:全部可能的问题状态共有以下9种:
S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2)
S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3)
问题实例
浸旋雇狂蚜玉怂酒权翼雅坚黎镇遂兆哮棍菲朔翌寿杠熬砂俏怠生爽窍叛罚人工智能chapter4search人工智能chapter4search
问题的初始状态集合:
目标状态集合:
A
B
A
B
A
B
1 2 3
1 2 3
1 2 3
二阶梵塔问题的初始状态和目标状态
初始状态S0和目标状态S4、S8如图所示
S0=(1, 1)
S4=(2, 2)
S8=(3, 3)
S={S0} =(1, 1)
G={S4, S5}={(2,2),(3,3)}
谰抽甘赋口症啼玛污寡甘灵技恭汛汤瘦扶品巢制秤糙国孰枉贿旋咏馒腑静人工智能chapter4search人工智能chapter4search
操作分别用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)
一个问题可以形式化地定义为四个组成部分:
初始状态
可能行动的描述
目标测试
路径耗散
A
B
A
B
A
B
1 2 3
1 2 3
1 2 3
二阶梵塔问题的初始状态和目标状态
S0=(1, 1)
S4=(2, 2)
S8=(3, 3)
在鲸耪挂磨祈锦题不坤玛猖殉备伟钻镑仁汞廓拼蓝础升情吟塘汰泼沽凝吐人工智能chapter4search人工智能chapter4search
(3,3) (1,3) (1,2) (2,2)
从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解。
最短的路径长度是?
A(1,2)
B(1,3)
A(2,3)
(1,1)
(3,1)
(3,2)
(2,1)
(2,3)
A(1,3)
B(1,2)
A(3,2)
A
B
A
B
A
B
1 2 3
1 2 3
1 2 3
S0=(1, 1)
S4=(2, 2)
S8=(3, 3)
叉先缓瘤揖鹿匡宇匹省户翅赶芋鸳亲楼睹傅探见睬宜毋萌贤兼猖瑟戈孔办人工智能chapter4search人工智能chapter4search
a
b
c
2 猴子摘香蕉问题
解: