搜索优化方法课件.ppt

搜索优化方法长沙市一中曹利国什么是搜索?搜索是对一个问题不断地寻找可行方案,然后找到最优的可行方案。搜索称为“通用解题法”,但是大部分情况下搜索所需的时间复杂度很高。搜索一般分为:深度优先搜索(DFS)和广度优先搜索(BFS)搜索关键字状态状态转移优先搜索遍历枚举深度优先搜索广度优先搜索剪枝状态状态转移状态:是对问题在某一时刻的进展情况的数学描述状态转移:是问题从一种状态转移到另一种状态的操作。搜索过程:通过状态转移不断地寻找目标状态或最优状态。深度优先遍历深度优先搜索遍历:遍历类似树的先根遍历,它是一个递归过程,可称述为:首先访问一个顶点Vi(开始为初始点),并将其标记为已访问过,然后从Vi的一个未被访问可到达的邻接点出发进行深度优先搜索遍历,当Vi所有可到达的邻接点均被访问过时,则退回上一个顶点Vk,从Vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历。深度优先搜索深度优先搜索:按照深度优先搜索遍历所有的状态。实现方式可以采用递归或者栈来实现深度优先搜索递归实现的框架:VoidDFS(longstate,longdepth){for(longi=1;i<=count(state);i++)newstate=make(state,i);if(answer)printans;elseif(depth<maxdepth)DFS(newstate,depth+1)}深度优先搜索深度优先搜索可以看成按深度优先顺序遍历一颗树:一般深度优先搜索要用到回溯。回溯算法适用问题:求解搜索问题一般的深度优先搜索问题都要用到回溯算法,每次不能遍历下去时,回溯到前一个点,继续遍历。例题1走迷宫问题(高级本)有一个m*n格的迷宫(表示有m行、n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用-1表示无路)。