贪婪最佳优先算法之美

2021/6/17 14:25:58

本文主要是介绍贪婪最佳优先算法之美,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

贪婪最佳优先算法

下面是贪婪优先算法的完整代码,注意这个实现假设h(x)的值在执行过程中总是不变的。

currentNode = startNode
add currentNode to closedSet
do
   //把邻接节点加入开放集合
   foreach Node n adjacent to currentNode
       if closedSet contains n
          continue
        else
           n.parent=currentNode
           if openSet does not contain n
              compute n.h
              add n to openSet
           end
         end
      loop
      //所有可能性都尝试过了
      if openSet is empty
         break
      end
      //选择新的当前节点
      currentNode = Node with lowest h in openSet
      remove currentNode from openSet
      add currentNode to closeSet
 until currentNode == endNode
 //如果路径解出,通过栈重新构造路径
 if currentNode == endNode
    Stack path
    Node n = endNode
    while n is not null
       push n onto path
       n=n.parent
    loop
  else
    //寻路失败
  end


如果我们不想用栈构造路径,另一个方案就是直接计算起点到终点的路径。这样,在寻路结束的时候就能得到从起点到终点的路径,可以节省一点计算开销。


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 



这篇关于贪婪最佳优先算法之美的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程