人工智能吴飞基于树搜索的贪婪最佳优先搜索例题
贪婪最佳优先搜索算法Greedy_BFS
算法原理: 利用优先队列（优先级属性每一个结点的估计函数值）后进先出的性质来一层层的遍历。有信息搜索策略使用问题本身的定义之外的特定知识，比无信息的搜索策略更有效的进行问题求解。一般考虑的算法称为最佳优先搜索。最佳优先搜索中，结点是基于评价函数值被选择扩展的。
算法时间空间复杂度分析：时间复杂度：O(b^m )，空间复杂度：O(b^m )
算法步骤：
1)将开始结点压入优先队列中；
2)取出队列结点当前拓展结点，设置为已访问；
3)判断当前结点是否为目标结点，若是则输出路径搜索结束，否则进行下一步；
4)访问当前结点的所有相邻子节点；
5)判断该该子节点是否被访问过，若已经访问过则回到2），若还未访问过则继续下一步6）；
6)对于每一个子节点，获取其相关信息值并进行路径更新，将其子节点的父亲结点指向当前结点，返回2）；
7)对新的队列进行一次优先级排序；
8)若优先队列为空还未到目标结点，返回搜索失败；
package 实验一;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Greedy_BFS extends BuildGraph{
    public void ShortestPath(){
        ShortestPath(start,end);
    }
    public Queue<Vertex> SortTest(Queue<Vertex> queue){
        List<Vertex> list=new ArrayList<>();
        while(!queue.isEmpty()){
            list.add(queue.poll());
        }
        Collections.sort(list, new Comparator<Vertex>(){
            @Override
            public int compare(Vertex o1, Vertex o2) {
                // TODO Auto-generated method stub
                return o1.h<o2.h? -1:(o1.h==o2.h? 0:1);
            }
        });
        int i=0;
        while(i<list.size()){
            //System.out.(i).h+" ");
            queue.(i));
sortout什么意思中文
            i++;
        }
        //System.out.println();
        return queue;
    }
    public void ShortestPath(Vertex startNode,Vertex endNode){
        //初始化
        Queue<Vertex> queue = new LinkedList<>();
        //startNode.dist=0;
        queue.offer(startNode);//将源点dist设置为0并入队列
          while(!queue.isEmpty()){
            Vertex v = queue.poll();
            explored.put(v.vertexLabel, 1);
            if(v.vertexLabel==endNode.vertexLabel){
                System.out.println("Greedy_BFS Route:");
                showPath_H(v,startNode);
                return;
            }
            for(int i=0;i<v.child.size();i++){
                Vertex current=(i).endVertex;
                //System.out.(current.vertexLabel));
                (current.vertexLabel)==0){
                    current.dist=v.dist+((i));
                    queue.offer(current);
                    current.preNode=v;
                }
            }
            queue=SortTest(queue);
        }
        System.out.println("Greedy_BFS Route:"+" Failure!");
        return;
    }
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。