搜索
2023-12-29 22:36:24
发布于:浙江
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。
中文名深度优先搜索
外文名Depth-First-Search
提出者——霍普克洛夫特与罗伯特·塔扬
应用学科计算机
#################
目录
1、详细解释
2、基本思路
3、穷举
4、系统算法
5、基本框架
6、C++的实现
7、举例
################
详细解释
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束).简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort. [1]
基本思路
深度优先遍历图的方法是,从图中某顶点v出发:
(1)访问顶点v;
(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索(BFS).
穷举
在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举); [2]
对于问题的第一个状态,叫初始状态,要求的状态叫目标状态。
搜索就是把规则应用于实始状态,在其产生的状态中,直到得到一个目标状态为止。
产生新的状态的过程叫扩展(由一个状态,应用规则,产生新状态的过程)
搜索的要点:(1)初始状态;
(2)重复产生新状态;
(3)检查新状态是否为目标,是结束,否转(2); [1]
如果搜索是以接近起始状态的程序依次扩展状态的,叫宽度优先搜索。
如果扩展是首先扩展新产生的状态,则叫深度优先搜索。
深度优先搜索
深度优先搜索用一个数组存放产生的所有状态。
(1) 把初始状态放入数组中,设为当前状态;
(2) 扩展当前的状态,产生一个新的状态放入数组中,同时把新产生的状态设为当前状态;
(3) 判断当前状态是否和前面的重复,如果重复则回到上一个状态,产生它的另一状态;
(4) 判断当前状态是否为目标状态,如果是目标,则找到一个解答,结束算法。
(5) 如果数组为空,说明无解。
对于pascal语言来讲,它支持递归,在递归时可以自动实现回溯(利用局部变量)所以使用递归编写深度优先搜索程序相对简单,当然也有非递归实现的算法。 [3]
搜索是人工智能中的一种基本方法,是一项非常普遍使用的算法策略,能够解决许许多多的常见问题,在某些情况下我们很难想到高效的解法时,搜索往往是可选的唯一选择。按照标准的话来讲:搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。
搜索虽然简单易学易于理解,但要掌握好并写出速度快效率高优化好的程序却又相当困难,总而言之,搜索算法灵活多变,一般的框架很容易写出,但合适的优化却要根据实际情况来确定。在搜索算法中,深度优先搜索(也可以称为回溯法)是搜索算法里最简单也最常见的,今天我们就从这里讲起,下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。
系统算法
所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构和产生系统。正如前面所说的,搜索算法简而言之就是穷举所有可能情况并找到合适的答案,所以最基本的问题就是罗列出所有可能的情况,这其实就是一种产生式系统。 [2]
我们将所要解答的问题划分成若干个阶段或者步骤,当一个阶段计算完毕,下面往往有多种可选选择,所有的选择共同组成了问题的解空间,对搜索算法而言,将所有的阶段或步骤画出来就类似是树的结构(如图)。
从根开始计算,到找到位于某个节点的解,回溯法(深度优先搜索)作为最基本的搜索算法,其采用了一种“一直向下走,走不通就掉头”的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。
上面的话可能难于理解,没关系,我们通过基本框架和例子来阐述这个算法,你会发现其中的原理非常简单自然。
基本框架
定义一个结构体来表达一个NODE的结构: [2]
struct Node { int self; //数据 node *left; //左节点 node *right; //右节点 };
那么我们在搜索一个树的时候,从一个节点开始,能首先获取的是它的两个子节点。 [2]例如:
“
A B C D E F G
”
A是第一个访问的,然后顺序是B和D、然后是E。然后再是C、F、G。那么我们怎么来保证这个顺序呢? [3]
这里就应该用堆叠的结构,因为堆叠是一个先进后出的顺序。通过使用C++的STL,下面的程序能帮助理解:
const int TREE_SIZE = 9;
std::stack<node*> visited, unvisited;
node nodes[TREE_SIZE];
node* current;
for( int i=0; i<TREE_SIZE; i++) //初始化树
{
nodes[i].self = i;
int child = i*2+1;
if( child<TREE_SIZE ) //Left child
nodes[i].left = &nodes[child];
else nodes[i].left = NULL;
child++;
if( child<TREE_SIZE ) //Right child
nodes[i].right = &nodes[child];
else nodes[i].right = NULL;
}
unvisited.push(&nodes[0]); //先把0放入UNVISITED stack
while(!unvisited.empty()) //只有UNVISITED不空
{
current=(unvisited.top()); //当前应该访问的
unvisited.pop();
if(current->right!=NULL)
unvisited.push(current->right); // 把右边压入 因为右边的访问次序是在左边之后
if(current->left!=NULL)
unvisited.push(current->left);
visited.push(current);
cout<<current->self<<endl;
}
这个程序的意思就是:进行搜索一条路,直到不能走为止,换另一条路。
##############################################
##############################################
广度优先算法,又称广度优先搜索算法,是最简便的图的算法之一,其特点是:在扫描数据空间时,每个点以最短路径生成广度优先生成树。广度优先搜索这种算法遍历整个图的所有节点并记录,直至找到所需结果为止,是一种盲目算法,但它还有一个非常重要的特性一最佳解,即当所有的边长相等,它就是最佳解,若在距离聚类算法中,应用广度优先搜索此特性去搜寻数据对象的同类,则可以有效地提高聚类速度。[1]
此外,可以把网格单元作为点来处理,利用广度优先搜索某网格的直接网格邻居单元邻居和间接网格邻居单元,以类似于树的层次迅速遍历整个网格空间,对符合条件的所有找到的邻居合并,从而将显著网格单元进行连通并聚类。同时设置类门限,归类时做出正确判断,提高聚类精度。[2]
主要过程
(1)将图中所有结点储存在队列中;
(2)从队列取出第一个结点,从此结点出发,访其未访问的所有邻接点,并将此结点从队列中删除;
(3)对所有邻接点重复步骤(2),直至队列为空。
编号方案
广度优先搜索编号即分层编号,是按照节点。支路及分支线距离根节点的远近,将网络元件划分为不同层次。然后根据层次遍历树的访问顺序,来给各支路和节点编号。广度优先搜索方案分为基于支路分层法和分支线分层法
分支线分层法编号方案
按照分支线距离根节点的远近,对分支线进行分层。即按照从分支线的末端到源节点所经历的分支数目对分支线进行分层从配电网选出一条带多条分支线路的主馈线。在分支线之下又分出子分支线,子分支线又可能再分出子分支线可以对节点编号采用规定方法:(1)分支线按所在的层次大小编号,主馈线的层次为1,其子分支线的层次为2,子分支线之下再分出子分支线的层次为3,以此类推。(2)同一层上的各分支线按宽度优先搜索进行顺序编号。(3)用一个标量Ⅳ=(a,b,C)给每个节点编号,a是节点分支线所在层次。b是该分支线在a层的次序。c是节点在分支线上的次序,节点表示第a条层次为b的分支线上的第C个节点。(4)源节点编号为~=(1,1,0)。
基于分支线分层法广度优先搜索编号方案分析
(1)节点编号复杂,对于分支线所在层次序以及该分支线在Ⅱ层的次序b的确定均需要根据其他分支线在a层的次序才能予以确定,尤其对于同一节点具有多条分支线,难以确定该分支线在层的次序6。(2)节点编号无法直观反应其拓扑结构,即无法根据节点编号构建拓扑结构,如Ni=(2,3、4)节点编号虽然知道该节点处于第2层次的第3条分支线上的第4个节点。但是却并不知道该节点所在分支线具体连接在哪4-节点上(3)用3类数字进行节点编号,计算机需要用三维数组来储存编号,占用内存大,降低计算速度。
算法
简化算法
基于广度优先算法的简化算法(v-bfs算法)
该算法运用图的广度优先搜索算法(BFS)来求解简化轨迹大小Tsim最小值问题,称该算法为V-bfs:算法,构造步骤如下:
(1)图的构造。构造一个图称为Ge(V,E),V表示点的集合,E表示边的集合。对任意的Pi点(1≤i<j≤n),对任意的位置点P和P(1≤i<j≤n),如果 \varepsilon(PiPj)≤\varepsilonu,则边(Pi,pj)\inE。
(2)寻找最短路径。在图Ge(V,E),中用广度优先索算法(BFS)寻找一条从P1到Pn的最短路径。
(3)找到图的简化轨迹。根据第(2)步的路径关系到一条简化轨迹。
优化算法
优化算法的目的是为了降低算法的时间复杂度,在提出优化算法之前先介绍几个概念。
算法比较
v-bfs算法来和DP算法、SP算法比较,用以上3个指标来度量算法在权衡轨迹简洁度和精确度上的优劣性。
采用DP算法来作为比较对象,因为该离线算法是纯粹的基于位置信息来简化轨迹,同时也是非常著名的算法。采用ZP算法作为比较对象,因为该离线算法同样是纯粹地基于方向信息来简化轨迹。算法的时间复杂度和空间复杂度比较如表1。
对每一个速度阈值\varepsilon,用算法v-bfs:得到简化轨迹Tsim,根据公式求出简化轨迹Tsim与原始轨迹T的角度偏差,作为SP算法的输入值。用相同的简化轨迹Tsim求出每个轨迹段的轨迹点到轨迹两端点的最大垂线距离,所有轨迹段垂线距离的最大值即为DA算法的输入值。在图3中,v-bfs算法和DP算法的L(H)值随着\varepsilon的增大而逐渐变小,当\varepsilon等于6.0m/S时,L(H)近似相等,然而SP算法L(H)值先变小然后保持不变;表明v-bfs算法在\varepsilon较小时能保证简化轨迹与原始估计的方向偏差;然而\varepsilon大于0.5m/s时,简化轨迹与原始估计的方向偏差非常大。图3表明v-bfs算法的简洁性均没有DP算法和SP算法好。
在图4中,三种算法的(L(D/H)的值均随着\varepsilon的增大先增大后保持不变,且(L(D/H)在保持不变前,v-bfs:算法的轨迹一直处于另外两条轨迹的下方,说明v-bfs算法比DP算法和SP算法保留了更多原始轨迹的信息。表明经过v-bfs:算法简化后的轨迹比SP算法和DP算法的精确度更高。
在图5中,当速度阈值\varepsilon小于1.5m/s时,v-bfs算法在权衡简洁度和精确度上都要比DP算法和SP算法好;速度阈值\varepsilon大于1.5m/S时,经过三种算法后的简化轨迹与原始轨迹的总偏差大体上相差不大,并且随着\varepsilon的逐渐增大,这三种算法效果一样。
总的来说,v-bfs算法在简洁度上比SP算法和DP算法差,在精确度上比SP算法和DP算法要好,在权衡简洁性和精确性上比SP算法和DP算法也要好。
空间划分
根据定理1,要验证MI=\varphi是否成立,需要逐步验证MI=\varphii一\varphi是否成立。[[\varphi]]作为模型的一个划分,其定义的形式将直接影响空间划分的验证效率。
定理2设\vartheta是模型M中的一个变量,{\upsilon0,\upsilon1…\upsilonn是\upsilon的取值范围,其中。是初始值:
证明从初始状态So出发,若So共有n+1个可能的后继状态,其中变量的取值分别为\upsilon0,\upsilon1,\upsilon2,⋯,\upsilonn,则模型的所有路径可以划分为n+1个子集,分别为,M0,M1,⋯,Mn,对于i∈{0,1,⋯,n}中的任意取值,都有:
由图1可以得出,路径集合M1,M2,⋯,Mn满足式(1),所以这些路径集合上的状态在验证过程中无须遍历,只要对路径集合进行验证。同理当i=1时,只要对路径集合M1进行验证,即可达到搜索空间划分的目的。
实例
以可信系统中的隐通道(covert channe1)分析为例。因为隐通道利用了系统原本不是用于数据传送的资源来传送数据,所以这种通信方式一般不能被系统的固有安全机制所检测和控制。[3]其工作方式可以简单地概括为:一个高安全级主体使用某种操作更改了共享客体的某一属性在先,而另一个具有较低安全级或不可比安全级的主体借助某种操作观察到这种属性的变化在后。在状态机模型的约束下可以将隐通道的特征描述为:不同安全级主体依据其合法权限并按照某种规则交替访问同一共享客体的系统模型中的一组状态迁移序列。因此隐通道是最常见的隐蔽信息流。[4]
以一个包含m个主体和N个共享客体的一般访问模型作为分析对象,采用模型检测的方法进行隐通道分析。[5]需要指出的是,这是一个具有一般性的例子,在任意的代码片断中,当m个主体共享n个客体时,以下分析结果均成立。通过NuSMV的验证,上述公式在模型中满足约束条件,因此具有访问互斥性。
首先取共享客体数n=1,主体数m分别取2、5、10、15和20,原始模型的可达状态数和状态迁移数的变化情况如表1所示。抽象后的模型可达状态数和状态迁移数,如表2所示:
由于主体的密级集合SC:{TS,S,C,UC}只包含四个元素,且每一个主体的类别集合相等,所以抽象主体不超过4个。抽象后进行路径划分,系统情况如表3所示。下面取主体数m=10,共享客体数n分别取1、2、3、4和5。抽象后主体数为3。原始模型的可达状态数和状态迁移数的变化如表4所示。抽象模型情况如表5所示。
由于该模型中含有多个共享客体,首先划分客体,使每个子空间中只含有一个共享客体,因为本例中主体数已经确定。划分客体后,每个只含有一个共享客体的子空间规模是一致的,因此可以选取含有三个共享客体的例子作为分析对象,其可达状态数和状态迁移数的变化情况如表6所示。从中可以看出,经过抽象和客体划分操作后,原始模型的可达状态数分别约减了99.9%和98.7%;经过抽象和两次划分后,原始模型的状态迁移数分别约减了99.9%、98.7%和74.1%。
需要说明的是,表6中划分路径后,模型的可达状态数并没有发生变化,同为108,是因为划分路径后模型的主客体数并没有变化,只是在模型的众多路径中选取相应路径作为验证子空间,因此可达状态数没有变化,而状态迁移数发生了变化。
的抽象方法为一种一般性方法,抽象模型与原始模型的属性保持难以确定,且抽象只在一个维度上进行,因此本文的抽象方法更为精确有效。下面选取10个主体,1个共享客体的例子,分别用抽象方法与本文抽象方法进行隐通道搜索,对比情况如表7所示。[6]
抽象模型1表示使用抽象方法,抽象模型表示使用本文方法。从表7中可以看出,使用本文的抽象方法后可达状态数和状态迁移数更少。
从上面的实例可以看出,针对具体的隐通道问题进行抽象和搜索空间划分后,得到的待验证模型中包含的可达状态数和状态迁移数得到了有效约减,从而缓解了状态空间爆炸的问题。
这里空空如也
有帮助,赞一个