搜索之BFS.pptx

SEARCHINGSTRATEGIESACM/ICPC之搜索篇2020/4/122搜索概论搜索被称为“通用解题法”,在算法和人工智能中占据重要地位。但由于它巨大的局限性和自身灵活性,也被认为是最难学难用的算法之一。本节目标:希望同学们对于任意一个问题, :按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索:在搜索中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向发展,加速问题的求解过程并找到最优解。2020/4/124搜索算法盲目搜索:(BreadthFirstSearch)(DepthFirstSearch)、重复式搜索、迭代加深搜索、迭代加宽搜索、柱型搜索启发式搜索:**算法2020/4/125状态空间明确以下概念:状态:问题在某一时刻进展状况的数学描述。状态转移:问题从一种状态到另一种或几种状态的操作。状态空间:一个“图”,图结点对应于状态,点之间的边对应于状态转移。搜索:寻找一种可行的操作序列,从起始状态经过一系列状态转移,达到目标状态。2020/4/126过河问题某人要带一条狗、一只鸡、一箩米过河,但小船除需要人划外,最多只能载一物过河,而当人不在场时,狗要咬鸡、鸡要吃米。问此人应如何过河?2020/4/127过河问题(con1)状态:建立四元组(人,狗,鸡,米)。用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≠d2020/4/128过河问题(con2)搜索:(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)2020/4/129过河问题(con3)搜索:→(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)2020/4/1210过河问题(con4)搜索在“图”中进行,但图不需要事先建立(“隐式图”)。搜索过程就是对图的遍历过程,可以得到一棵“搜索树”。搜索树的结点个数、分枝数、深度,决定着搜索的效率。