迭代加深搜索算法ID_BFS
算法原理: 利用栈后进先出的性质来进行递归迭代加深(加深的深度有限制不再直接一定要搜索到叶节点才能返回)加回溯的遍历搜索。迭代加深的深度优先搜索是一种常用策略,它经常和深度优先搜索结合使用来确定最好的深度界限。
算法时间空间复杂度分析:时间复杂度:O(b^d )
算法步骤:
1)将开始结点压入栈中;
2)取出队列结点当前拓展结点,设置为已访问;
3)判断当前结点是否为目标结点,若是则输出路径搜索结束,否则进行下一步;
4)判断当前结点的深度是已经超过设置的深度限制D,若超过返回2),否则继续下一步5)
5)访问当前结点的所有相邻子节点;
6)判断该该子节点是否被访问过,若已经访问过则回到2),若还未访问过则继续下一步7);
7)对于每一个子节点,获取其相关信息值并进行路径更新,将其子节点的父亲结点指向当前结点,返回2);
8)若优先队列为空还未找到目标结点,返回搜索失败;
package 实验一;
import java.util.Stack;
public class ID_DFS extends BuildGraph{
public void ShortestPath(int D){
ShortestPath(start,end,D);
}
public void ShortestPath(Vertex startNode,Vertex endNode ,int D){
//初始化
Stack<Vertex> stack= new Stack<>();
//startNode.dist=0;
stack.push(startNode);//将源点dist设置为0并入队列
while(!stack.isEmpty()){
Vertex v = stack.pop();
if(v.depth>D) continue;//检查一下
explored.put(v.vertexLabel, 1);
if(v.vertexLabel==endNode.vertexLabel){
System.out.println("ID_DFS Route:"+"("+D+")");
showPath(v,startNode);
return;
}
for(int i=0;i<v.child.size();i++){
Vertex current=v.child.get(i).endVertex;
//System.out.println(explored.get(current.vertexLabel));
if(explored.get(current.vertexLabel)==0){
current.dist=v.dist+v.adjEdges.get(v.child.get(i));
current.depth=v.depth+1;
stack.push(current);
current.preNode=v;
}
}
}
System.out.println("ID_DFS Route:"+"("+D+")"+" Failure!");
return;
}
}
版权声明:本文为m0_45020051原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。