回溯法与分枝—限界法的区别以及分支限界法分类以及LC学习

区别

首先理解什么是状态空间树。
状态空间树：是指解空间的树结构
在状态空间树生成过程中有3类结点：活结点、E-结点、死结点
而回溯法与分支限界法的区别主要在于：构造状态空间树的过程不一样。
回溯法是利用深度优先搜索构造，分支限界法是用广度优先搜索构造。

分类

接下来了解分支限界法。
可以利用队列或栈来导出分支限界法，所以依次分支限界法可以分为：FIFO（队列）检索、LIFO（栈）检索
但两种扩充结点的方法过于呆板，导致偏向于正确答案的结点没有优先权。
分支限界法是扩展完一个E-结点所有儿子后再找一个结点作为E-结点扩展，上面两种扩展过于呆板，那是不是可以选择代价最小的结点的作为下一个E-结点进行拓展？
可以，这就是LC（least cost ）检索的分支限界法。

LC分支限界法

LC分支限界法：选用一个成本函数C来标识结点成本，选择最小代价结点作为下一个E-结点:初始：C定义为结点x到目标答案结点的步数，但这个问题是要已知目标答案，所以不能这么精确.然后用g’来估计x到答案结点的代价，但是又会造成纵深检索；最后引入h函数表示根结点到x结点的位置减少纵深检索。
C’=f(h(x))+g’(x)
LC检索分支限界法流程：

当有多个答案是是否LC算法能够最小成本答案？
否，除非保证C（X）<C(Y),有C’（X）<C’(Y)，或者保证C’（X）<=C(X)而且对答案结点有两种成本函数相等。

LC分支限界法应用

1. 15迷问题

首先先判断是否可达！
首先按照目标状态给棋盘方格编号，得出position（i）代表初始状态下标号i所在位置的棋盘编号，空格位置用16代替。
记录less（i）函数（编号比i小但是初始位置在position（i）之后的数字数目）
若less（i）累加+x（空格是否在偶数位（不考虑目标状态的偶数位），偶1，奇0）为偶数，可达！

LC算法：g’(x)：该结点与目标状态的差距=不在其目标位置的非空白牌数目（精髓）

成本函数的上界的作用和定义：求答案的最小成本，过滤，初始为无穷

2.带期限的作业排序问题

按编号选取作业
g’(x)为已经考虑过但不在j集合的罚款数目
这里c’=g’.