05-搜索：最优、分支界限、A

1、引入

• 搜索是关于选择的
• 启发式距离：黑板上粉色的直线线段是现实中没有的，叫做启发式距离。
• 启发式找到的路不见得都能走得通，因为在现实中考虑问题的时候，离得近不一定是最好的，因为可能会出现死胡同
• 上节的爬山算法和束搜索，目的都是考虑离目标最近的距离
• 例子

2、最短路径的4种算法

1.branch bound分支限界

• 没有考虑离目标有多远，只考虑自己走了多远
• 直到积累的长度都已经大于等于到达目标的长度，就不需要再进行扩展了
• 总是扩展当前最短的路径，直到目标节点
• 把当前所有的路径都扩展出来，比较最后距离最短的
• 然后扩展最短的，再进行比较没有扩展的
• 只要没有负值长度，我们就肯定能得到一个最短路径

入队和扩展的概念

• 我们跟踪已经扩展过的节点，不再扩展。
• 这些放在队列中的所有路径就是入队列表
• 入队思想对于这些最短路径并不奏效
• 路径需要加到扩展队列（不是入队队列）
• 因为我们必须要保证扩展的都是短路径（最后要得到最短路径）
• 这个就相当于迪杰斯特拉算法，单独用一张列表来保存所有扩展，叫做扩展列表

2.分支限界+扩展列表

• 找到迄今为止最短的路径进行扩展（类似Dijkstra算法）
• 已经扩展过的，就不需要再扩展，这会减掉很多多余的树枝
• 死马原则（the dead horse principal)：只要发现一条不是最短路径，就不再扩展它

3.可容许启发式

• 可容许启发式：不用扩展队列而考虑剩下的直线距离的下界
• 可容许启发式：最优搜索的稳妥方式,可以避免左边那些远离目标节点的路径

例子：
现在我们把直线距离考虑进来，来选择扩展AorB
A到G的距离，直线距离略大于7
B到G的直线距离正好是6
所以扩展最可能是最短距离的那一个节点
当两者分值一样的时候，我们考虑在字典中靠前的那一个
A——G：7,3+7=10
B——G:6,5+6=11;所以扩展A

4.A*

• 分支界限+扩展列表+可容许启发式
• 程序流程图中的排序应该是依照积累距离+可容许启发式排序
• 但在这里排序是没有必要的计算
• 检验的就不是第一个路径，而是最短路径.

A*算法流程图

反例

• 可容许性的概念，在考虑图的时候可容许启发式总是最优搜索的稳妥方法，但是搜索不是关于图的，所以使用这个方法就会出现问题
• 例子：并不是平面地图，而是一个模型，可以在任意的连线上放想放的数值。
• 然后就在扩展c的时候停住了，因为c已经被扩展过了，所以没能找到最短路径，这就是可容许方法的弊端

对可容许性进行强化

解释

• 可容许性：任意节点x同目标G之间的估计距离H(x,G)≤x和目标G之间的实际距离D(x,G)
• 一致性：|节点x同目标G之间的估计距离H(x,G)-另外一个节点y和目标之间的估计距离H(y,G)|≤x和y之间的实际距离D(x,y)
• 反例满足可容许性，但不满足一致性，所以不能找到最短路径