书目：人工智能第2版
有需要电子版的可以私信我。

这次学习分支定界法。

指标说明

在讲爬山法的时候，是不考虑之前的代价的，即只考虑当前状态到目标的代价。这次学的算法则考虑了当前节点到初始节点的代价的。
用式子$f(n)=g(n)+h\ast (n)$来表示从初始节点S经过节点n，然后到达目标G的确切代价。
其中，$g(n)$是从S到n的实际路径，$h\ast (n)$是经过最短路径到达G的剩余代价。
由于$h\ast (n)$未知，所以需要算出估计值$h(n)$，估计值必须比真实值小(低估)，即有$h\ast (n)\ge h(n)$

实际上之所以用$g(n)$而不用$g\ast (n)$是因为$g\ast (n)$不好算。要特别注意，此时的大小关系是和h反过来的，即$g\ast (n)\le g(n)$

过多的废话就不讲了，感兴趣的可以看书。

分支定界法

这个算法有个假设：$h(n)=0$，即只考虑到初始节点的距离。

与BFS的比较

BFS努力找到通往目标的某一路径，然而分支定界法努力找到一条最优路径。使用分支定界法时，一旦找到了一条通往目标的路径，这条路径很可能是最优的。为了确保这条路径确实是最优的，分支定界法继续生成部分路径，知道每条路径的代价大于或等于所找到的路径的代价。

例子

问题：从A走到G，要求路径最短。

看下面两张图和图中文字，应该很好理解，我就不做过多描述了。

使用低估值的分支定界法

大白话：使用低估剩余距离的值，增强分支定界发，如下图。

采用动态规划的分支定界法

这里实际上是想说明最优性原理，看下面这个图：

如果要从S到G，必经I，而从S到I有多条路径，那为了获得最优路径，肯定是选最优的从S到I的路径，这就是最优性原理的意思——最优路径由最优子路径构建而成。

应用了动态规划的分支定界法的伪代码如下图，其实就是应用最优性原理，对于同个节点，只保留最小g(n)的那个路径：

A*搜索

这个是使用动态规划且采用剩余距离估计值的分支定界法，就是在分支定界法的基础上，结合了前面的两种改进，不多说，直接看伪代码就行了。

这次就到这里了，可以点个赞吗？