深度优先搜索是什么

深度优先搜索是爬虫早期开发中广泛使用的方法。它的目的是到达被搜索结构的叶子节点(也就是那些不包含任何超链接的HTML文件)。

深度优先搜索是爬虫早期开发中广泛使用的方法。它的目的是到达被搜索结构的叶子节点(也就是那些不包含任何超链接的HTML文件)。在一个HTML文件中，当选中一个超链接时，被链接的HTML文件会执行深度优先搜索，也就是说，在搜索其余的超链接结果之前，必须完全搜索单个链。深度优先搜索跟随HTML文件上的超链接，直到它不能更深入，然后返回到一个HTML文件，然后继续选择HTML文件中的其他超链接。当没有其他超链接可供选择时，搜索结束。

详细说明

其实深度优先搜索是一种图算法，简称DFS(深度优先搜索)。简而言之，这个过程是深入每一个可能的分支路径，每个节点只能被访问一次。

例如，下图是一个无向图。如果我们从A点开始深度优先搜索(下面的访问顺序不是唯一的，第二个点可以是B或者C或者D)，可能会得到下面的访问过程:A->；B->。e(没办法！回到a)->:C->；F->。H->。g->；d(没有路，最后回到A，A没有未被访问过的邻居节点，本次搜索结束)。

简要说明深度优先搜索的特点:每次深度优先搜索的结果必须是一个图的连通分量。深度优先搜索可以从多个点开始。如果& # 8221；结束时间& # 8221；排序(具体方法是创建一个链表，然后在每个节点的相邻节点都被访问过的情况下，将该节点添加到链表的末尾，然后将整个链表反转)，那么就可以得到所谓的& # 8221；拓扑排序& # 8221；，即拓扑排序。

基本想法

深度优先遍历方法是从图中的顶点v开始:

(1)访问顶点v；

(2)从V的未接入相邻点出发，首先用深度遍历图；直到图中与v连通的顶点有路径被访问；

(3)如果此时图中仍有未被访问的顶点，则从一个未被访问的顶点开始深度优先遍历，直到图中的所有顶点都已被访问。当然，当人们刚刚掌握深度优先搜索时，往往会用它来走迷宫。事实上，我们还有其他方法，那就是广度优先搜索(BFS)。

穷尽性

在我们遇到的一些问题中，我们找不到确切的数学模型，也就是找不到解决这类问题的直接方法，所以我们通常采用搜索法来解决。搜索就是利用问题的所有可能性进行测试，按照一定的顺序和规则不断测试，直到找到问题的解决方案。试了试，没有找到解决办法，就是没有解决办法。测试的时候一定要测试所有的情况(其实就是疲惫)；

问题的第一个状态称为初始状态，需要的状态称为目标状态。

搜索是将规则应用于初始状态，在生成的状态中，直到获得目标状态。

生成新状态的过程称为扩展(通过应用来自状态的规则来生成新状态的过程)

搜索要点:(1)初始状态；

(2)重复生成新状态；

(3)检查新状态是否是目标，是否是结束(2)；

如果搜索由接近初始状态的程序按顺序扩展，则称为宽度优先搜索。

如果扩展是先扩展新生成的状态，则称为深度优先搜索。

深度优先搜索

深度优先搜索使用数组来存储所有生成的状态。

(1)将初始状态放入数组中，设置为当前状态；

(2)扩展当前状态，生成新的状态放入数组，将新生成的状态设置为当前状态；

(3)判断当前状态是否与前一状态重复，如果重复，则返回前一状态，生成另一状态；

(4)判断当前状态是否为目标状态，如果是，则寻找解决方案，结束算法。

(5)如果数组为空，则无解。

就pascal语言而言，支持递归，可以自动实现回溯(使用局部变量)。所以用递归写深度优先搜索程序比较简单，当然也有非递归算法。

搜索是人工智能中的一种基本方法，是一种非常常用的算法策略，可以解决很多常见的问题。在某些情况下，当我们很难想到有效的解决方案时，搜索往往是唯一的选择。按照标准，搜索算法是利用计算机的高性能，有目的地穷尽一个问题的部分或全部可能情况，从而得到问题的解的方法。

搜索虽然易学易懂，但是要掌握和写出一个高速高效优化的程序还是相当困难的。总之，搜索算法灵活，总体框架易于编写，但要根据实际情况确定合适的优化。在搜索算法中，深度优先搜索(也称为回溯)是最简单、最常见的搜索算法。今天，我们就从这里开始。以下内容假设读者已经知道最基本的编程和简单的递归算法。

系统算法

所有的搜索算法都可以分为两部分——控制结构和生成系统。前面说过，搜索算法就是简单的把所有可能的情况都穷尽，找到合适的答案，所以最基本的问题就是把所有可能的情况都列出来，这其实就是一个生产系统。

我们把要解决的问题分成几个阶段或步骤。当计算一个阶段时，下面往往有很多选择，所有的选择共同构成问题的解空。对于搜索算法来说，画出所有的阶段或步骤就像一个树形结构(如图)。

回溯(depth-first search)作为最基本的搜索算法，采用了“一个下去，过不去就转”(知道“回溯”这个词)的思想，相当于用先根遍历的方法构造搜索树。

以上的话可能很难理解。没关系。我们通过基本框架和例子来解释算法，你会发现原理非常简单自然。