这次学习分支定界法。

指标说明

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

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

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

分支定界法

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

与BFS的比较

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

例子

问题：从A走到G，要求路径最短。 看下面两张图和图中文字，应该很好理解，我就不做过多描述了。

使用低估值的分支定界法

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

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

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

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

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

A*搜索