搜索算法問題的研究

石少儉

摘要：算法是計算機程序員必備的一項技術。回溯法和分支限界法主要用于窮舉式搜索法，合稱為搜索算法。搜索算法可以通過一些設計，避免不必要的搜索，來提高搜索的效率。

關鍵詞：算法;回溯法;分支限界法;搜索算法

中圖分類號：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.

【通聯編輯：王力】