跳转到内容

人工智能/搜索/启发式搜索/深度优先搜索

Add links
来自维基教科书，开放的书籍，开放的世界

背景和定义

[编辑 | 编辑源代码]

深度优先搜索是一种用于查找以图形格式表示的信息的算法。深度优先搜索的第一个版本，最初被称为 Tremaux 算法，是在 19 世纪被设计为解决迷宫的一种方法（Stewart，1999）。然而，“Tremaux 迷宫求解方法的理论特性”直到 1970 年才在计算机科学领域被发现，当时 John Hopcroft 和 Robert Tarjan 合作使用深度优先搜索来“获得线性时间算法”（Tarjan，1972，第 146 页）。

算法，这个词最初是由数学家穆罕默德·伊本·穆萨·花拉子米在公元 8 世纪后期创造的，指的是用于找到问题解决方案的程序或公式（Berardi、Kroon、McDermott 和 Newton，2006）。算法使用各种输入；这些输入通常包含的信息量不同。一个好的算法必须能够有效地将任何长度的输入组织成基本的功能步骤，这些步骤可以存储在程序的内存中（“PC”，2008）。Hopcroft 和 Trajan 的线性时间算法使输入的大小与程序解决特定问题所花费的资源和时间相等（Tarjan，1972）。

深度优先搜索算法用于垂直遍历以树状结构格式化的图形信息节点。从图形顶部的单个节点开始，搜索从树状结构的最左侧开始，移动到每个后续节点，直到搜索到达树状结构的最底部节点。在每个树状结构段上的每个节点的搜索完成之前，搜索不会从左到右水平移动（Siek & Lee，2000）。

深度优先搜索最重要的功能之一是能够跟踪已经访问过的节点。以下伪代码允许此功能。

DFS(u):

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

由 Kravitz、David 和 Lafferty（1997）创建的这个伪代码展示了深度优先搜索算法如何通过有效地跟踪已经访问过的节点和仍然需要探索的节点来工作。Kravitz 等人将每个需要探索的节点设为白色，每个正在探索的节点设为灰色，每个已经探索过的节点设为黑色。节点的颜色编码允许用户跟踪搜索算法的进度，以及保持一个准确的数据映射，显示哪些节点已经被存储。代码中的第一行初始化深度优先搜索，从图形中最左侧的树段开始。

DFS(u):

这段代码块允许搜索引擎访问树状结构中最左侧树段上的每个节点，在搜索每个节点一次时，将节点从白色变为灰色。

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

这段代码块将搜索水平地跨越树状结构，从左到右，一旦树状结构左侧的每个节点都被搜索过一次。换句话说，算法会朝向白色节点移动。当算法完成对某个节点的搜索后，该节点会变为黑色，算法不能再次搜索该节点。

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

实际应用

[编辑 | 编辑源代码]

深度优先搜索的一个实际应用是“用于确定图形是否为平面的算法”（“图形”，2008）。基本上，平面图形可以绘制在平面上，而不会使图形边缘交叉（Weisstein，2008）。深度优先搜索使用户能够“通过树[结构]的后序遍历”来组织图形中表示的信息（“平面”，2008）。换句话说，深度优先搜索使用户能够决定他们想要“嵌入反向边”的顺序，从第一个节点到每个后续节点。如果在此过程中，用户确定某个节点组与当前未在树状结构图形中表示的其他节点有潜在连接，那么用户就会知道该特定树段必须“保持在平面图形的外部面”（“平面”，2008）。

问题

[编辑 | 编辑源代码]

在深度优先搜索中，“每个节点都与两个时间相关联：发现时间和完成时间”（Kravitz、David & Lafferty，1997）。如果搜索参数很大（即大量节点），那么“存储所有这些时间所需的存储空间”将很快变得难以管理（Kravitz、David & Lafferty，1997）。

参考文献

[编辑 | 编辑源代码]
检索自“https://wikibooks.cn/w/index.php?title=Artificial_Intelligence/Search/Heuristic_search/Depth-first_search&oldid=3222334”
华夏公益教科书