本文主要是介绍知情搜索（二）-找到最优解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
普通分支界定算法
分支界定算法是努力寻找一条最优路径，为了确保找到一条到达目的地的路径，它找到路径后会继续生成部分路径，直到每条路径的代价大于或等于所找到的路径的代价。不具备启发值。
伪代码如下：
//Branch Bound Search
Branch_Bound(Root_Node, goal)
{Create Queue QInsert Root Node into Qwhile(Q_Is_Not){G = Remove from QIf(G=goal) Return the path from Root_Node to G;elseInsert children of G into the QSort Q by path length}//and whileReturn failure
}使用低估值的分支定界法
具有低估值的分支界定法是获得最佳解且具备启发性的方式。
采用动态规划的分支界定法
该算法给出如下建议：如果两条或者多条路径到达一个公共节点，只有到达这个公共节点具有最小代价的路径才被保存（其他路径删除）。
伪代码如下：
// Branch and Bound with Dynamic Programming
B_B_W_Dynamic_Programming (Root_Node, goal)
{Create Queue QInsert Root_Node into Qwhile(Q_Is_Not_Empty){G = Remove from QMark G visitedIf this mode has been visited previously, retain only the shortest path to GIf(G = goal) Return the Path from Root_Node to GInsert the children of G which have not been previously visited into the Q }return failure
}
A*搜索
该方法采用具有剩余距离估计值和动态规划的分支定界法。
伪代码如下：
// A* Search
A* Search (Root_Node, Goal)
{Create Queue QInsert Root_Node into Qwhile(Q_Is_Not_Empty){G = Remove from QMark G visitedIf(G=goal) Return the path from Root_Node to G;ElseAdd each child node's estimated distance to current distanceInsert the children of G which have not been previously visited into the Q Sort Q by the path length;} Return failure
}
这篇关于知情搜索（二）-找到最优解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
