深度优先搜索
baikeViewInfo={id:"288277",editable:"true",title:"深度优先搜索",expIndex:"0"};
求助编辑百科名片

深度优先搜索
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。
目录
详细解释
别的方法
穷举
产生式系统和搜索树
深度优先搜索方法
回溯（深度优先搜索）基本框架
举例
bk.view.catalog().start("0");
编辑本段详细解释　　事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
　　举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束).

图简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort.
编辑本段别的方法　　当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索 (BFS).状态（state):状态是制问题求解过程中每一步的状况。
　　算符（operater）算符是把问题从一种状态变换到另一种状态的方法代号。算符的取值范围就是搜索的范围。（一般设为局部变量)。
　　结点（node）:用来表明状态特征及相关信息。
编辑本段穷举　　在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）；
　　对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。
　　搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。
　　产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）
　　搜索的要点：（1）初始状态；
　　（2）重复产生新状态；
　　（3）检查新状态是否为目标，是结束，否转（2）；
　　如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。
　　如果扩展是首先扩展新产生的状态，则叫深度优先搜索。
　　深度优先搜索
　　深度优先搜索用一个数组存放产生的所有状态。
　　（1） 把初始状态放入数组中，设为当前状态；


　　（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；
　　（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
　　（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。
　　（5） 如果数组为空，说明无解。
　　对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。
　　搜索是人工智能中的一种基本方法，是一项非常普遍使用的算法策略，能够解决许许多多的常见问题，在某些情况下我们很难想到高效的解法时，搜索往往是可选的唯一选择。按照标准的话来讲：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。
　　搜索虽然简单易学易于理解，但要掌握好并写出速度快效率高优化好的程序却又相当困难，总而言之，搜索算法灵活多变，一般的框架很容易写出，但合适的优化却要根据实际情况来确定。在搜索算法中，深度优先搜索（也可以称为回溯法）是搜索算法里最简单也最常见的，今天我们就从这里讲起，下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。
编辑本段产生式系统和搜索树　　所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分——控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。
　　我们将所要解答的问题划分成若干个阶段或者步骤，当一个阶段计算完毕，下面往往有多种可选选择，所有的选择共同组成了问题的解空间，对搜索算法而言，将所有的阶段或步骤画出来就类似是树的结构（如图）。
　　从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。
　　上面的话可能难于理解，没关系，我们通过基本框架和例子来阐述这个算法，你会发现其中的原理非常简单自然。
编辑本段深度优先搜索方法　　下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到 A,A也没有未访问的相邻节点,本次搜索结束).
　　B--E
　　/
　　A-C--F
　　\ >H
　　D--G
编辑本段回溯（深度优先搜索）基本框架　　DFS（Node）
　　if (Node=目标节点)
　　then //找到目标，结束
　　for each next∈d[Node]
　　do DFS(next);
　　end
编辑本段举例　　现在以这题来举例(迷宫)
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
记录起点为(1,1)找到所有的到(4,4)的路径.
　　pascal程序如下：
　　const
　　b:array[1..4,1..4]of integer=((1,1,1,1),(0,1,0,1),(0,1,0,1),(0,1,1,1));
　　c:array[1..4,1..2]of -1..1=((0,1),(0,-1),(1,0),(-1,0));
　　var
　　a:array[1..16,1..2]of integer;
　　procedure print;
　　var
　　i,j:integer;
　　begin
　　for i:=1 to 4 do
　　begin
　　for j:=1 to 4 do
　　write(b[i,j]:3);
　　writeln;
　　end;
　　writeln('--------------');
　　end;
　　procedure try(k:integer);
　　var
　　i:integer;
　　begin
　　if (a[k,1]=4)and(a[k,2]=4) then begin print;exit;end;
　　for i:=1 to 4 do
　　begin
　　a[k+1,1]:=a[k,1]+c[i,1];
　　a[k+1,2]:=a[k,2]+c[i,2];
　　if (a[k+1,1]>=1) and (a[k+1,1]<=4 )and (a[k+1,2]>=1) and (a[k+1,2]<=4) and
　　(b[a[k+1,1],a[k+1,2]]=1) then
　　begin
　　b[a[k+1,1],a[k+1,2]]:=2;
　　try(k+1);
　　b[a[k+1,1],a[k+1,2]]:=1;
　　end;
　　end;
　　end;
　　begin
　　a[1,1]:=1;
　　a[1,2]:=1;
　　b[1,1]:=2;
　　try(1);
　　end.
　　这个程序的意思就是：进行搜索一条路，直到不能走为止，换另一条路。

白银圣牙党吧建立成功