搜索算法问题的研究

石少俭

摘要：算法是计算机程序员必备的一项技术。回溯法和分支限界法主要用于穷举式搜索法，合称为搜索算法。搜索算法可以通过一些设计，避免不必要的搜索，来提高搜索的效率。

关键词：算法;回溯法;分支限界法;搜索算法

中图分类号：G642        文献标识码：A

文章编号：1009-3044（2020）23-0216-02

Abstract： Algorithm is a necessary technology for computer programmers. Backtracking method and branch and bound method are mainly used for exhaustive search method， which is collectively called search algorithm. Search algorithm through some design， avoid unnecessary search， to improve the efficiency of search.

Key words： algorithm; backtracking method; branch and bound method; search algorithm

1 引言

算法，晦涩难懂，但又是IT领域最受重视的素养之一。 大学的计算机算法课一般讲授经典的算法，主要是分治算法、动态规划算法、贪心算法、回溯法、分支限界法等。回溯法和分支限界法主要用于穷举式搜索法，可以合称为搜索算法。搜索算法可以通过一些必要的设计，避免不必要的搜索，来提高搜索的效率。回溯法和分支限界法有许多相似的应用[1-4]。

2 基本概念

应用搜索算法解问题时，应定义问题的解空间。问题的解空间至少包含问题的一个解或者最优解。

定义1[5]：如果一个问题的解能够表示成一个n元向量[（x1，x2，...，xn）]的形式，称为问题的解向量。

定义2[5]：解向量的分量xi的取值限定称为问题的显约束。为满足问题的解而对不同分量之间施加的约束称为问题的隐约束。

定义3[5]：对于问题的一个实例，满足显约束条件的所有解向量，构成了该实例的一个解空间。

解空间一般表示成树的形式，常见的解空间树有子集树和排列树。

定义4：问题的一个解是解向量各分量取值的子集，称为子集树。

定义5：问题的一个解是解向量各分量取值的一种排列，称为排列树。

同一个问题的解空间可以有多种表示，有些表示方法更简单，搜索方法更简单，搜索效率更高。

定义6[5]：问题的显约束和隐约束对应的子树称为约束函数。不可能到达目标函数的子树称为限界函数。约束函数和限界函数统称为剪枝函数。

3 回溯法

具有限界函数的深度优先算法称为回溯法。如果问题需要找出它的解集或者满足某些约束条件的最优解时，优先使用回溯法解决问题。

回溯法的算法思想：按深度优先算法，从根结点出发搜索解空间树。利用剪枝函数判断该结点是否包含问题的解：如果不包含，则跳过对该结点的子树的搜索，向上回溯;否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本步骤：

（1）针对所给问题，定义问题的解空间;

（2）确定解空间结构;

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

4 分支限界法

以广度优先或以最优目标优先的方式搜索问题的解空间树的算法称为分支限界法。分支限界法可以以最优目标优先的方式搜索，可以解决求可行解和最优解的问题。

分支限界法的算法思想：解空间树上的一个结点成为扩展结点后，产生所有儿子结点。利用剪枝函数，把导致不可行解或导致非最优解的结点剪除，其余结点加入活结点表。一直到找到所需的解或活结点表为空时结束。根据结点加入活结点表的顺序不同，分支限界法可以分为队列式分支限界法和优先队列式分支限界法。

分支限界法的基本步骤：

（1）针对所给问题，定义问题的解空间;

（2）确定解空间结构;

（3）以广度优先或以最优目标优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

5 分支限界法与回溯法的区别

求解目标不同：回溯法是找出满足约束条件的所有解。分支限界法找出满足条件的一个解，或某种意义下的最优解。搜索方式不同：回溯法，深度优先。分支限界法，广度优先或最优目标优先。

6 应用实例

例2.最小重量机器设计问题

某一机器由n个零件组成，每一种零件由m个供应商处提供。设 wij 和cij分别是供应商j 提供零件i的重量和价格。求总价格不超过d的最小重量机器设计。

因为该问题需要求最优解，所以用分支限界法求解。

7 總结

我们正处于信息爆炸的时代，需要进行穷举式搜索的问题会越来越多。分支限界法和回溯法作为最常用的搜索算法，一定会得到越来越多的应用。

参考文献：

[1] 王剑辉，梁路，王彪.基于分支限界的不平衡气象数据晴雨分析[J].计算机应用研究，2016，33（6）：1648-1652.

[2] 刘家保，陆一南，陈中华.一类新的平面图的超边幻和标号[J].北华大学学报（自然科学版），2012，13（1）：41-43.

[3] 程国忠，张世禄.三个典型问题的回溯算法[J].四川师范学院学报（自然科学版），2000（2）：187-191.

[4] 杨元生，张成学.在有向图中寻找哈密顿回路的快速回溯法[J].大连理工大学学报，1989（2）：223-228+236

[5] 王晓东. 计算机算法设计与分析. 第5版[M]. 北京：清华大学出版社，2018.

【通联编辑：王力】