网站建设的基本流程是怎样的,苏州诶茵诶公司网站,商业空间设计图片,济南网络推广公司摘要#xff1a;本文介绍适合于大数据规模情况下的#xff0c;新型的迭代深化深度优先搜索(IDDFS)算法的原理、实例及实现的C#源代码。
引言
常用的树#xff08;或图#xff09;遍历算法是两种#xff1a; 广度优先搜索算法#xff08;BFS#xff09; 和 深度优先搜索… 摘要本文介绍适合于大数据规模情况下的新型的迭代深化深度优先搜索(IDDFS)算法的原理、实例及实现的C#源代码。
引言
常用的树或图遍历算法是两种 广度优先搜索算法BFS 和 深度优先搜索算法DFS。然而在遇到巨大高度和宽度的树(或图)时BFS 和 DFS 都不是非常有效。因为
1DFS首先遍历通过根的一个相邻节点然后遍历下一个相邻节点。这种方法的问题是如果有一个节点靠近根但不在DFS探索的前几个子树中那么DFS到达该节点的时间很晚。此外DFS可能无法找到到节点的最短路径根据边的数量。而BFS 一级一级的走但是需要更多的空间。
2DFS 需要的空间是 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 1elsereturn 0
为了实现迭代深化搜索我们必须标记以下各项之间的差异
1当达到深度极限界限时发生破裂。
2未达到深度界限的故障。
而在这种情况下我们通过每次增加深度限制来多次尝试搜索方法在第二种情况下即使我们继续搜索多次因为不存在解决方案这意味着浪费时间。因此我们得出结论在第一种情况下失败被发现是非自然的失败在第二种情况下失败是自然的。
三、IDDFS实例
咱们看看一个实例 在给定的树中起始节点是A深度初始化为0。目标节点是R我们必须找到到达它的深度和路径。图中的深度为4。在这个例子中我们考虑树作为有限树而我们也可以考虑同样的过程的无限树。我们知道在IDDFS算法中我们首先进行DFS直到指定的深度然后增加每个循环的深度。这个特殊步骤是DLS或深度限制搜索的一部分。因此下面的遍历显示了IDDFS搜索。 四、IDDF的优点和缺点
以下是优点和缺点。
1、优势
1IDDFS让我们有希望找到树中存在的解决方案。
2当在较低的深度例如n找到解时该算法被证明是有效且及时的。
3IDDFS的最大优势是在博弈树搜索中发现IDDFS搜索操作试图改进搜索节点的深度定义、启发式和得分从而提高搜索算法的效率。
4IDDFS算法的另一个主要优点是响应速度快。早期结果是该算法的一个优点。在单独的迭代完成后进行了多次改进。
5虽然在这里做了更多的工作但IDDF的性能优于单独的BFS和DFS。
6空间和时间复杂性表示为Od这里d被定义为目标深度。
7让我们考虑IDDFS的运行时间。假设bl其中b是分支因子l是深度极限。然后我们在边界k下搜索目标节点。在深度k上我们说可能有只生成一次的节点。类似地深度限制k-1处的节点是k-2深度的两倍和三倍。因此在深度l处生成的节点是k倍。
2、缺点
1到达目标节点所需的时间是指数级的。
2IDDF的主要问题是在每个深度进行的时间和浪费的计算。
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/// 序号/// /summarypublic int Id { get; set; } 0;/// summary/// 数据/// /summarypublic string Value { get; set; } ;/// summary/// 访问标识/// /summarypublic bool Visited { get; set; } false;/// summary/// 默认构造方法/// /summarypublic NodeInfo(){}/// summary/// 构造函数/// /summary/// param nameid/param/// param namevalue/parampublic NodeInfo(int id, string value){Id id;Value value;}}/// summary/// 边信息/// /summarypublic class EdgeInfo{/// summary/// 起点Id/// /summarypublic int From { get; set; } -1;/// summary/// 终点Id/// /summarypublic int To { get; set; } -1;/// summary/// 默认构造方法/// /summarypublic EdgeInfo(){}/// summary/// 构造方法/// /summary/// param namefrom/param/// param nameto/parampublic EdgeInfo(int from, int to){From from;To to;}}/// summary/// 图信息/// /summarypublic class IDDFS_Graph{/// summary/// 节点信息/// /summarypublic ListNodeInfo Nodes { get; set; } new ListNodeInfo();/// summary/// 图的边连线集合/// /summarypublic ListEdgeInfo Edges { get; set; } new ListEdgeInfo();/// summary/// 默认构造方法/// /summarypublic IDDFS_Graph(){}/// summary/// 添加“边信息”用于构建“图”数据/// /summary/// param namefrom/param/// param nameto/parampublic 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 namesrc/param/// param nametarget/param/// param namelimit/param/// returns/returnsprivate 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 namesrc起点/param/// param nametarget目标/param/// param namemax_depth最大深度差/param/// returns/returnspublic 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
