搜索优化方法课件.ppt

《搜索优化方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索优化方法长沙市一中曹利国什么是搜索？搜索是对一个问题不断地寻找可行方案，然后找到最优的可行方案。搜索称为“通用解题法”，但是大部分情况下搜索所需的时间复杂度很高。搜索一般分为：深度优先搜索（DFS）和广度优先搜索（BFS）搜索关键字状态状态转移优先搜索遍历枚举深度优先搜索广度优先搜索剪枝状态状态转移状态：是对问题在某一时刻的进展情况的数学描述状态转移：是问题从一种状态转移到另一种状态的操作。搜索过程：通过状态转移不断地寻找目标状态或最优状态。深度优先遍历深度优先搜索遍历：遍历类似树的先根遍历，它是一个递归过程，可称述为：首先访问一个顶点Vi（开始为初始点）

2、，并将其标记为已访问过，然后从Vi的一个未被访问可到达的邻接点出发进行深度优先搜索遍历，当Vi所有可到达的邻接点均被访问过时，则退回上一个顶点Vk，从Vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历。深度优先搜索深度优先搜索：按照深度优先搜索遍历所有的状态。实现方式可以采用递归或者栈来实现深度优先搜索递归实现的框架：VoidDFS(longstate,longdepth){for(longi=1;i<=count(state);i++)newstate=make(state,i);if(answer)printans;elseif(depth

3、pth)DFS(newstate,depth+1)}深度优先搜索深度优先搜索可以看成按深度优先顺序遍历一颗树：一般深度优先搜索要用到回溯。回溯算法适用问题：求解搜索问题一般的深度优先搜索问题都要用到回溯算法，每次不能遍历下去时，回溯到前一个点，继续遍历。例题1走迷宫问题（高级本）有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下

4、左右四个方向。如果一条路都不可行，则输出相应信息(用-1表示无路)。例题1分析我们不难想到可以采用深度优先搜索。我们用深度优先搜索扩展一个点时，向4个方向按照深度优先搜索进行扩展，但是注意一些到过的点不能再次经过。当到达目标点时不扩展下去，并且计数器加一，输出答案，回溯。当前这个点不能继续扩展下去时，回溯到上一节点，扩展下去。深度优先搜索的优化尽可能减少生成的节点数定制回溯边界条件，剪掉不可能得到最优解的子树运用记忆化的方法，使得一些遍历过的子树不要重复遍历减少所遍历的状态总数例题2：定货单（ceoi试题）某商店经理已将所有的货物按它们的标号的字母顺序进行了分

5、类。所有的标号首字母相同的货物被存储在同一仓库中，该仓库也用该字母进行标记。在某天中，经理接到并登记了许多定货单，每张定货单仅需一种货物你已知道了该天经理所需处理的所有定货单，但你不知道它们的登记顺序。计算出所有可能的访问仓库的方法，来为经理解决该天所有的定货要求。输入文件ORDERS.IN中仅有一行，包含所有所需货物的标号（一个随机的顺序）。每一种货物是用它标号的首字母来表示的，只使用英文小写字母。定货单的数目不超过200输出：输出文件ORDERS.OUT要包含经理访问仓库的所有可能顺序。示例Order.inorder.outbbjdbbdjbbjdbdbj

6、bdjbbjbdbjdbdbbjdbjbdjbbjbbdjbdbjdbb分析因为题目要求我们输出所有可能的登记顺序，而数据的范围也不大，不难看出它是一个搜索题目。由于方案数可能会比较大，如果要保存下所有的方案也是没有必要的，因此我们宜采用深搜而放弃广搜。一般来讲，要确定某个顺序第I位上的字母，我们是从“a“到“z”循环，依次查找，看哪个字母还可以再选，当可选字母的比较少，且可选字母中每一个字母又可以选较多次时，每一重循环就有很多扫描是多余的。我们可以对这种情况作如下优化：在输入完毕后，先统计出各种字母的总个数，并且将可选的字母按字典顺序依次放入到一个字符串数组

7、中（每个字母最多放一次），搜索的时候，我们将从“a”到“z”的循环改为从头到尾扫描字符串数组，由于该字符串数组中的各字母都是可选的，所以我们每扫到一个字母，就将它插入到当前方案的序列中，并将它的可选次数减1如果一个字母已经不能再选（可选次数为0），则暂时将它从字符串数组中删去，等到当前过程递归调用完毕后再将其插入该字符串数组。这样一来，就可以保证每一次循环扫描到的字母都是可选的，搜索中几乎没有了多余的运算搜索剪枝在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵

8、活地去定制回溯搜索的边界。剪枝1、正确