[搜索算法的通用优化方法]
[DFS]
[搜索剪枝]
在很多情况下,我们已经找到了一组比较好的解.但是计算机仍然会义无返顾地去搜索比它更"劣"的其他解,搜索到后也只能回溯.为了避免出现这种情况,我们需要灵活地去定制回溯搜索的边界.
*例题 计算机网络连接
要将n(n=kx,那么这个方案的总长度一定不小于kx,那么,就不必要搜索下去了,直接换下一个结点继续搜索.
路径A1-A2-…An与路径An-An-1-…A1这两条路径是一个"正反"的关系,本质上是相同的,于是我们可以规定起点始的下标总是小于终点的下标
假如路径的A-B-C-D的长度
X
X
X
X
然后回溯一次,换下一个点继续搜索.
这个算法的效率,是
实际上,在放置了(1,1)这个皇后,再把皇后放置在(2,1)就是毫无意义的:前面一个皇后一定能攻击到它.
为了避免这种情况,我们这样做:
X
.
.
.
->
X
.
.
.
.
.
.
.
X
.
.
.
.
.
.
.
.
走了一个棋子以后,把它的"势力范围"给圈出来,并且告诉以后的皇后:这里不能放置.举简单的例子:放置皇后(1,1),由于打"."的格子在放了(1,1)这颗子之后,被标注为了"不能走",所以这些点我们就不去理会了.这样就节省了很多时间,大大提高了搜索的效率.
而对于很多回溯的题目,我们都可以采用分枝定界法,把搜索树中不必要的枝剪去,大大提高了搜索的效率.
[记忆化]

下一页