摘要：本文介绍适合于大数据规模情况下的，新型的迭代深化深度优先搜索(IDDFS)算法的原理、实例及实现的C#源代码。
引言
常用的树（或图）遍历算法是两种： 广度优先搜索算法（BFS） 和 深度优先搜索算法（DFS）。然而在遇到巨大高度和宽度的树(或图)时，BFS 和 DFS 都不是非常有效。因为：
（1）DFS首先遍历通过根的一个相邻节点，然后遍历下一个相邻节点。这种方法的问题是，如果有一个节点靠近根，但不在DFS探索的前几个子树中，那么DFS到达该节点的时间很晚。此外，DFS可能无法找到到节点的最短路径（根据边的数量）。而，BFS 一级一级的走，但是需要更多的空间。
（2）DFS 需要的空间是 O(d)，其中 d 是树的深度，但是 BFS 需要的空间是 O(n)，其中 n 是树中的节点数(为什么？请注意，树的最后一级可以有大约 n/2 个节点，第二个最后一级可以有 n/4 个节点，在 BFS，我们需要让每一级都一个接一个地排队)。
IDDFS （迭代深化深度优先搜索，Iterative Deepening Depth-First Search，也简称为IDS）则是结合了深度优先搜索的空间效率和广度优先搜索的快速搜索（对于更接近根的节点）。
这里发布IDDFS 主要的原理性的代码，更全面的程序可在此基础上改进与增强。
一、IDDFS简介
迭代深化深度优先搜索（IDDFS）是一种算法，与BFS和DFS一样，它也是非信息搜索策略的重要组成部分。我们可以将IDDFS定义为BFS和DFS搜索技术的混合算法。在IDDF中，我们发现BFS和DFS存在一定的局限性，因此我们对这两种程序进行了混合，以消除它们各自的缺点。我们先进行有限深度搜索，直到固定的“有限深度”。然后，我们通过迭代过程不断增加深度限制，除非我们找到了目标节点或遍历了整个树（以较早的为准）。
二、IDDFS的工作原理
在非信息搜索策略中，BFS和DFS在最佳时间和空间搜索元素方面并不理想。这些算法只能保证在指数时间和空间中找到路径。因此，我们找到了一种方法，我们可以使用DFS的空间能力和BFS方法的最优解方法的融合，在那里我们开发了一种新的方法，称为迭代深化，使用这两种方法。这里的主要思想在于利用边界实体的重新计算，而不是囤积它们。每次重新计算都由DFS组成，因此占用的空间更少。现在让我们考虑在迭代加深搜索中使用BFS。
考虑将广度优先搜索转化为迭代加深搜索。
我们可以通过留出一个DFS来做到这一点，它将搜索到一个极限。它首先搜索到预定义的深度到深度的限制，然后生成路由长度1。
这是通过以DFS方式创建长度为1的路由来实现的。接下来，它为深度限制2、3及以上的路线让路。
它甚至可以在循环开始时删除所有之前的计算并进行迭代。因此，在某种程度上，如果树中存在任何问题，最终会找到解决方案，因为枚举是按顺序进行的。
伪代码：
IDDFS(T):
for d = 0 to infinity:
if (DLS(T, d)):
return 1
else
return 0为了实现迭代深化搜索，我们必须标记以下各项之间的差异：
（1）当达到深度极限界限时发生破裂。
（2）未达到深度界限的故障。
而在这种情况下，我们通过每次增加深度限制来多次尝试搜索方法，在第二种情况下，即使我们继续搜索多次，因为不存在解决方案，这意味着浪费时间。因此，我们得出结论，在第一种情况下，失败被发现是非自然的失败，在第二种情况下，失败是自然的。
三、IDDFS实例
咱们看看一个实例：
在给定的树中，起始节点是A，深度初始化为0。目标节点是R，我们必须找到到达它的深度和路径。图中的深度为4。在这个例子中，我们考虑树作为有限树，而我们也可以考虑同样的过程的无限树。我们知道在IDDFS算法中，我们首先进行DFS，直到指定的深度，然后增加每个循环的深度。这个特殊步骤是DLS或深度限制搜索的一部分。因此，下面的遍历显示了IDDFS搜索。
四、IDDF的优点和缺点
以下是优点和缺点。
1、优势
（1）IDDFS让我们有希望找到树中存在的解决方案。
（2）当在较低的深度（例如n）找到解时，该算法被证明是有效且及时的。
（3）IDDFS的最大优势是在博弈树搜索中发现，IDDFS搜索操作试图改进搜索节点的深度定义、启发式和得分，从而提高搜索算法的效率。
（4）IDDFS算法的另一个主要优点是响应速度快。早期结果是该算法的一个优点。在单独的迭代完成后，进行了多次改进。
（5）虽然在这里做了更多的工作，但IDDF的性能优于单独的BFS和DFS。
（6）空间和时间复杂性表示为：O（d），这里d被定义为目标深度。
（7）让我们考虑IDDFS的运行时间。假设b>l，其中b是分支因子，l是深度极限。然后，我们在边界k下搜索目标节点。在深度k上，我们说可能有只生成一次的节点。类似地，深度限制k-1处的节点是k-2深度的两倍和三倍。因此，在深度l处生成的节点是k倍。
2、缺点
（1）到达目标节点所需的时间是指数级的。
（2）IDDF的主要问题是在每个深度进行的时间和浪费的计算。
（3）情况并不像我们想象的那么糟糕，尤其是当分支因子被发现很高时。
（4）当BFS失败时，IDDF可能会失败。当我们要从IDDF中找到多个答案时，它会一次返回成功节点及其路径，即使在多次迭代后需要再次找到它。停止深度限制不会进一步增加。
五、结论
迭代深化深度优先搜索是BFS和DFS的混合算法。IDDF可能不会直接用于计算机科学的许多应用中，但该策略通过迭代增加深度限制来搜索无限空间的数据。这非常有用，在人工智能和新兴的数据科学行业中也有应用。
六、IDDFS的C#源代码
下面给出IDDFS的核心算法C#源代码。C#最优雅！
using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Algorithm.Graph
{
public class NodeInfo
{
/// <summary>
/// 序号
/// </summary>
public int Id { get; set; } = 0;
/// <summary>
/// 数据
/// </summary>
public string Value { get; set; } = "";
/// <summary>
/// 访问标识
/// </summary>
public bool Visited { get; set; } = false;
/// <summary>
/// 默认构造方法
/// </summary>
public NodeInfo()
{
}
/// <summary>
/// 构造函数
/// </summary>
/// <param name="id"></param>
/// <param name="value"></param>
public NodeInfo(int id, string value)
{
Id = id;
Value = value;
}
}
/// <summary>
/// 边信息
/// </summary>
public class EdgeInfo
{
/// <summary>
/// 起点Id
/// </summary>
public int From { get; set; } = -1;
/// <summary>
/// 终点Id
/// </summary>
public int To { get; set; } = -1;
/// <summary>
/// 默认构造方法
/// </summary>
public EdgeInfo()
{
}
/// <summary>
/// 构造方法
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
public EdgeInfo(int from, int to)
{
From = from;
To = to;
}
}
/// <summary>
/// 图信息
/// </summary>
public class IDDFS_Graph
{
/// <summary>
/// 节点信息
/// </summary>
public List<NodeInfo> Nodes { get; set; } = new List<NodeInfo>();
/// <summary>
/// 图的边（连线）集合
/// </summary>
public List<EdgeInfo> Edges { get; set; } = new List<EdgeInfo>();
/// <summary>
/// 默认构造方法
/// </summary>
public IDDFS_Graph()
{
}
/// <summary>
/// 添加“边信息”用于构建“图”数据
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
public void AddEdge(int idFrom, string valueFrom, int idTo, string valueTo)
{
if (!Nodes.Exists(t => t.Id == idFrom))
{
Nodes.Add(new NodeInfo(idFrom, valueFrom));
}
if (!Nodes.Exists(t => t.Id == idTo))
{
Nodes.Add(new NodeInfo(idTo, valueTo));
}
Edges.Add(new EdgeInfo(idFrom, idTo));
}
/// <summary>
/// 从 src 开始的有限深度搜索
/// </summary>
/// <param name="src"></param>
/// <param name="target"></param>
/// <param name="limit"></param>
/// <returns></returns>
private bool Depth_Limited_Search(int src, int target, int limit)
{
if (src == target)
{
return true;
}
if (limit <= 0)
{
return false;
}
int i = Edges[src].From;
while (i != Edges[src].To)
{
if (Depth_Limited_Search(i, target, limit - 1) == true)
{
return true;
}
i++;
}
return false;
}
/// <summary>
/// 迭代深化深度优先搜索
/// </summary>
/// <param name="src">起点</param>
/// <param name="target">目标</param>
/// <param name="max_depth">最大深度差</param>
/// <returns></returns>
public bool IDDFS(int src, int target, int max_depth)
{
// 深度控制
for (int i = 0; i <= max_depth; i++)
{
if (Depth_Limited_Search(src, target, i) == true)
{
return true;
}
}
return false;
}
}
}
改进的IDDFS在AI领域有很不错的表现。
值得继续研究与改进。
---------------------------------------------
POWER BY TRUFFER.CN
![IDEA[Debug]简单说明](https://img-blog.csdnimg.cn/direct/3d60ea7538384460a52963eab1103b13.gif)
