from http://blog.csdn.net/wzwdcld/article/details/46125259
方法
|
对解空间树的搜索方式
|
存储结点的常用数据结构
|
结点存储特性
|
常用应用
|
|
|
回溯法
|
深度优先搜索
|
堆栈
|
活结点的所有可行子结点被遍历后才被从栈中弹出
|
找出满足约束条件的所有解
|
|
分支限界法
|
广度优先或最小消耗优先搜索
|
队列、优先队列
|
每个结点只有一次成为活结点的机会
|
找出满足约束条件的一个解或特定意义下的最优解
|
B、一个既可以采用回溯法也可以采用分支限界法解决的问题——0-1背包问题
0-1背包问题的解空间树是一棵子集树，所要求的解具有最优性质。
如果我们采用分支限界法解决这个问题，同样需要用到贪心算法构造的上界函数，所不同的是，这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索，因为在搜索到达叶节点之前，我们也无法知道已经得到的最优解是什么。在这里，我们用一个最大堆来实现活结点的优先队列，上界函数的值将作为优先级，这样一旦有一个叶结点成为扩展结点，就表明已经找到了最优解。
C、一个比较适合采用分支限界法解决的问题——布线问题
布线问题的解空间是一个图，适合采用队列式分支限界法来解决。从起始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入到活结点队列中，并且将这些方格标记为1，表示它们到a的距离为1。接着从活结点队列中取出队首作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活节点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止（表示没有通路）。
现在来看上面两张图。左图演示了分支限界法的过程。最开始，队列中的活结点为标1的格子，随后经过一个轮次，活结点变为标2的格子，以此类推，一旦b方格成为活节点便表示找到了最优方案。为什么这条路径一定就是最短的呢？这是由于我们这个搜索过程的特点所决定的，假设存在一条由a至b的更短的路径，b结点一定会更早地被加入到活结点队列中并得到处理。
还有许多类似于布线的问题可以为分支限界法提供良好的展示空间。在今年10月底刚刚结束的ACM竞赛北京分赛区的比赛中，就出现一一个和布线问题十分相似的问题，可以用分支限界法取得很好的效果。
要做如何的处理才能解决这个问题呢？可以采取布线问题的解决框架，但是在每个结点处所出现的障碍物需要变化。如果我们仅仅在每个结点处把蛇身标记为与障碍物相同的记号固然是一种容易想到的思路，但是这样处理不利于从一个格子的障碍物情形推广到相邻格子的障碍物情形。比较有效的做法是将蛇身描述成一个定长队列，队列首是蛇尾而队列尾是蛇头（如果为了思路的连贯性，也可以反过来处理，但是这样应该使用双向队列），这样一来从一个方格推广到相邻方格的时候，我们只要对这个队列做一步处理就可以得到新的描述蛇身的队列。然后，可以用这个队列和方格本身的位置组成一个结构或类，在求解过程中依然使用队列式分支限界法，只不过队列中的元素是我们所定义的那个结构或类的对象。利用STL等一些泛型技术，这个过程还是比较容易实现的。
struct Position //描述一个位置的结构
{
int posx,posy；
}；
struct SnakeNode //描述分支限界法队列中一个结点的结构
{
Position square；//方格位置信息
list<Position> snakeBody(snakeLength)；
//描述蛇身的队列，每一个格的蛇仍用Position描述
}；
{
Position square；//方格位置信息
list<Position> snakeBody(snakeLength)；
//描述蛇身的队列，每一个格的蛇仍用Position描述
}；
这样初始时我们用queue<SnakeNode> nodeList(0)建立这个队列，之后的过程和布线问题就基本一致了。