文档介绍：?搜索被称为“通用解题法”,在算法中占有重要的地位。?有巨大的局限性和自身的灵活性。?首先建立“状态空间”然后“盲目”搜索。常用方法:深度优先搜索,广度优先搜索,双向广度优先搜索,迭代加深,…?优化策略:剪枝、启发式、…状态空间?状态:问题在某一时刻进展状况的数学描述。?状态转移:问题从一种状态到另一种或几种状态的操作。?状态空间:一个“图”,图结点对应于状态,点之间的边对应于状态转移。?搜索:寻找一种可行的操作序列,从起始状态经过一系列状态转移,达到目标状态。例:过河问题?某人要带一条狗、一只鸡、一箩米过河,但小船除需要人划外,最多只能载一物过河,而当人不在场时,狗要咬鸡、鸡要吃米。问此人应如何过河?例:过河问题?状态:建立四元组(人,狗,鸡,米)。用0表示在左岸,1表示在右岸。?起始状态(0,0,0,0),终止状态(1,1,1,1)?状态转移规则:(a,b,c,d)→(1-a,1-b,c,d)(当a=b)→(1-a,b,1-c,d)(当a=c)→(1-a,b,c,1-d)(当a=d)→(1-a,b,c,d)?约束:(a,b,c,d)中,当a≠b时b≠c;当a≠c时c≠d例:过河问题?搜索:(0,0,0,0)→(1,1,0,0)→(1,0,1,0)→(0,0,1,0)→(1,0,1,1)→(1,0,0,1)→(1,1,1,0)→(1,0,0,0)例:过河问题?搜索:→(1,0,1,1)→(0,0,0,1)→(1,1,0,1)→(0,1,0,1)→(1,1,1,1)ok→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)→(0,0,1,1)→(1,1,1,0)→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)→(0,1,0,0)→(1,1,0,1)→(0,1,0,1)→(1,1,1,1)ok→(0,1,1,0)例:过河问题?搜索在“图”中进行,但图不需要事先建立(“隐式图”)。?搜索过程就是对图的遍历过程,可以得到一棵“搜索树”。?搜索树的结点个数、分枝数、深度,决定着搜索的效率。例:过河问题?搜索树过河问题的程序实现?普通状态可以用4个整数表示?压缩状态用4个bit表示(char型有8个bit,足够用)。?用深度优先(DFS,DepthFirstSearch)或广度优先(BFS,BreathFirstSearch)。