第一章搜索问题.ppt

1,第一章 搜索问题,内容： 状态空间的搜索问题。 搜索方式： 盲目搜索 启发式搜索 关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。,2,搜索问题,讨论的问题： 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。,3,1.1 回溯策略,例：皇后问题,4,( ),5,( ),Q,(1,1),6,( ),Q,Q,(1,1),(1,1) (2,3),7,( ),Q,(1,1),(1,1) (2,3),8,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),9,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),10,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),11,( ),Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),12,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),13,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),14,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),15,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),16,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),Q,(1,2) (2,4) (3,1) (4,3),17,递归的思想,当前状态,目标状态g,18,一些深入的问题,失败原因分析、多步回溯,19,一些深入问题,回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。,