算法 | 剪枝函数以及几种形式回溯法和分支限界法的区别算法特性分支限界法的思想分支限界法的基本步骤Prim和Kruscal回溯法的效率
what is 剪枝函数？
是对该问题能否得到最优解或者可行解的约束
限界函数：最优解
约束函数：可行解
回溯法和分支限界法的区别：
异：
| 回溯法 | 分支限界法 |
| 一次生成/扩展一个结点 | 一次生成所有的孩子结点 |
| BFS | DFS/最小耗费优先 |
| 找到所有解 | 找到最优解 |
同：
| 均需要定义解空间，解空间的组织结构一般是树或者是图 |
| 在解空间图上搜索问题的解 |
| 在搜索前需要确定判断条件，该条件用来判断该结点是否为可行解 |
| 在搜索的过程中，对生成的结点需要进行判断，满足判断条件的保留，不满足的就舍弃 |
算法特性
输入、输出、确定、可行、有限
分支限界法的思想：
从根开始，常以广度优先搜索的方式或者是最小耗费优先的方式搜索问题的解空间树，首先把根节点放入活节点表中，然后从活节点表中取出根节点，使其成为扩展节点，一次性生成扩展节点的孩子结点，舍弃那些导致不可行解或者不是最优解的节点，把其他合适的节点放入活节点表中，然后从活节点表中选取下一个扩展节点，一直搜索，直到找到解或者是活节点表为空。
分支限界法的基本步骤
- 定义解空间
- 确定解空间的组织结构（一般是树或者是图）
- 搜索解空间（确定限界函数和约束函数），如果采用优先级队列分支限界法，还要确定优先级确定方式
Prim和Kruscal
Prim:稠密图
Kruscal:稀疏图，边数较小
回溯法的效率
不依赖于：确定解空间的时间
依赖于：满足显约束的值的个数
计算约束函数的时间
计算限界函数的时间