2023年7月29日发(作者：)

人工智能吴飞基于树搜索的贪婪最佳优先搜索例题

贪婪最佳优先搜索算法Greedy_BFS

算法原理: 利用优先队列（优先级属性每一个结点的估计函数值）后进先出的性质来一层层的遍历。有信息搜索策略使用问题本身的定义之外的特定知识，比无信息的搜索策略更有效的进行问题求解。一般考虑的算法称为最佳优先搜索。最佳优先搜索中，结点是基于评价函数值被选择扩展的。

算法时间空间复杂度分析：时间复杂度：O(b^m )，空间复杂度：O(b^m )

算法步骤：

1)将开始结点压入优先队列中；

2)取出队列结点当前拓展结点，设置为已访问；

3)判断当前结点是否为目标结点，若是则输出路径搜索结束，否则进行下一步；

4)访问当前结点的所有相邻子节点；

5)判断该该子节点是否被访问过，若已经访问过则回到2），若还未访问过则继续下一步6）；

6)对于每一个子节点，获取其相关信息值并进行路径更新，将其子节点的父亲结点指向当前结点，返回2）；

7)对新的队列进行一次优先级排序；

8)若优先队列为空还未找到目标结点，返回搜索失败；

package 实验一;

import tions;

import ator; import ;

import ist;

import List;

import ;

public class Greedy_BFS extends BuildGraph{

});

int i=0;

@Override

public int compare(Vertex o1, Vertex o2) {

}

// TODO Auto-generated method stub

return o1.h

public void ShortestPath(){

}

public Queue SortTest(Queue queue){

List list=new ArrayList<>();

while(!y()){

}

(list, new Comparator(){

(());

ShortestPath(start,end);

}

while(i<()){

}

//n();

return queue;

//((i).h+" ");

((i));

i++;

public void ShortestPath(Vertex startNode,Vertex endNode){

//初始化

Queue queue = new LinkedList<>();

//=0;

(startNode);//将源点dist设置为0并入队列

while(!y()){

Vertex v = ();

(Label, 1);

if(Label==Label){

}

for(int i=0;i<();i++){

n("Greedy_BFS Route:");

showPath_H(v,startNode);

return;

Vertex current=(i).endVertex;

//n((Label));

}

}

}

n("Greedy_BFS Route:"+" Failure!");

return;

}

queue=SortTest(queue);

if((Label)==0){

}

=+((i));

(current);

e=v;