当我们想要用搜索解决一个问题时, 通常有下述手段可以使用:

1. Search Information. 主要是 branch 的方式.
2. Search Strategy. 主要是搜索的方式, 包括 回溯, DFS, BFS, 等, 具体内容在这篇文章中有介绍.
3. Bound Techniques. 包括 upper bound 和 lower bound, 一般是通过弱化/加强条件, 放缩松弛(线性规划技术)以及启发式等方法来获取原问题解的上下界, 这些解本身可以直接使用, 也可以用作搜索过程中的剪枝.
4. Decomposition Techniques.
5. Techniques for deciding which question to branch on.
6. Techniques for indentifying and solving tractable subproblems at each node.
7. Random restart techniques. 当搜索花费了相当长的时间时, 可以随机选择一个问题来 branching 继而重新尝试搜索. 一般没什么用处.
8. Caching Techniques. 存储一些子问题, 如果在后续的搜索过程中再次遇到这些子问题就直接取其解而不需要再求解. 一般的规则是: 存储经常碰到的子问题; 存储需要耗费了大量搜索代价的子问题; 存储可以被快速检索到的子问题.

值的详细介绍的是 1, 3, 4, 5, 6.

下面以 Winner determination problem(WDP) 为例子来进行介绍, 这个问题表述如下:

给定商品集 和 bid 集合 , 其中第 个竞标 bid 为二元组 , 是商品的集合, 为价格, 表示第 个 bid 出价 来拍卖 中的所有商品. WDP 要求选择最优的竞标集使得商品拍卖的总价格最大.

这实际上是一个带权独立集的问题, 即将 作为无向图 的顶点 , 则 , 每个顶点有点权 , 若商品 满足 则 , 那么 WDP 就是求 的最大权独立集.

Branch