《第一章搜索问题》由会员分享，可在线阅读，更多相关《第一章搜索问题（19页珍藏版）》请在金锄头文库上搜索。
1、第一章 搜索问题内容：状态空间的搜索问题。搜索方式：盲目搜索盲目搜索启发式搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。1 1搜索问题讨论的问题：有哪些常用的搜索算法。有哪些常用的搜索算法。问题有解时能否找到解。问题有解时能否找到解。找到的解是最佳的吗？找到的解是最佳的吗？什么情况下可以找到最佳解？什么情况下可以找到最佳解？求解的效率如何。求解的效率如何。2 21.1 回溯策略例：皇后问题3 3( )4 4( )Q(1,1)5 5( )QQ(1,1)(1,1) (2,3)6 6( )Q(1,1)(1,1) (2,3)7 7( )QQ(1,1)(1,1) (2,3)(
2、1,1) (2,4)8 8( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)9 9( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)1010( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)1111( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)1212( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)1313( )(1,1)(1,1) (2,3)(1
3、,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)1414( )(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)1515( )(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)1616递归的思想当前状态目标状态g1717一些深入的问题失败原因分析、多步回溯QQ1818一些深入问题回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3 2 2 31919
