搜索算法讲解.ppt
文本预览下载声明
广度优先搜索:从初始状态开始,通过规则来生成第一层结点,同时检查生成结点中是否有目标结点.若没有则生成下一层接点,并检查是否有目标结点… 广度优先搜索 采用队列存储 每次扩展出当前结点的所有子结点 广度优先搜索 void BFS(int curNode,int curDepth){ while(front rear) { ++front; for(i = 0; i m; i++) { newNode = Expend(q[front].node) if(!Exist(newNode)) { q[rear++].node = newnode; } if(newNode == target) return ; } } return; } 搜索算法举例:八数码难题 在3×3的方格棋盘上,分别放置了标有数字1、2、3、4、5、6、7和8的八个棋子 广度优先搜索算法举例 深度优先搜索 用堆栈存储 当前结点为下一次扩展结点的父结点 void DFS(int curNode,int curDepth){ if(curNode == Target ) return ; if(curEdpth MaxDepth)return; for(int i=0;in;++i){ int newNode = Expend(curNode,i); DFS(newNode,++curDepth); } return; } 函数的返回值可以根据具体的情况来设定 深度优先搜索算法举例 1241 Description The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid. Input The input contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 = m = 100 and 1 = n = 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*, representing the absence of oil, or `@, representing an oil pocket. Output are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets. Sample Input 1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @
显示全部