搜索算法問題的研究

石少儉

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

關(guān)鍵詞：算法;回溯法;分支限界法;搜索算法

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：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領(lǐng)域最受重視的素養(yǎng)之一。 大學(xué)的計算機(jī)算法課一般講授經(jīng)典的算法，主要是分治算法、動態(tài)規(guī)劃算法、貪心算法、回溯法、分支限界法等。回溯法和分支限界法主要用于窮舉式搜索法，可以合稱為搜索算法。搜索算法可以通過一些必要的設(shè)計，避免不必要的搜索，來提高搜索的效率。回溯法和分支限界法有許多相似的應(yīng)用[1-4]。

2 基本概念

應(yīng)用搜索算法解問題時，應(yīng)定義問題的解空間。問題的解空間至少包含問題的一個解或者最優(yōu)解。

定義1[5]：如果一個問題的解能夠表示成一個n元向量[（x1，x2，...，xn）]的形式，稱為問題的解向量。

定義2[5]：解向量的分量xi的取值限定稱為問題的顯約束。為滿足問題的解而對不同分量之間施加的約束稱為問題的隱約束。

定義3[5]：對于問題的一個實例，滿足顯約束條件的所有解向量，構(gòu)成了該實例的一個解空間。

解空間一般表示成樹的形式，常見的解空間樹有子集樹和排列樹。

定義4：問題的一個解是解向量各分量取值的子集，稱為子集樹。

定義5：問題的一個解是解向量各分量取值的一種排列，稱為排列樹。

同一個問題的解空間可以有多種表示，有些表示方法更簡單，搜索方法更簡單，搜索效率更高。

定義6[5]：問題的顯約束和隱約束對應(yīng)的子樹稱為約束函數(shù)。不可能到達(dá)目標(biāo)函數(shù)的子樹稱為限界函數(shù)。約束函數(shù)和限界函數(shù)統(tǒng)稱為剪枝函數(shù)。

3 回溯法

具有限界函數(shù)的深度優(yōu)先算法稱為回溯法。如果問題需要找出它的解集或者滿足某些約束條件的最優(yōu)解時，優(yōu)先使用回溯法解決問題。

回溯法的算法思想：按深度優(yōu)先算法，從根結(jié)點出發(fā)搜索解空間樹。利用剪枝函數(shù)判斷該結(jié)點是否包含問題的解：如果不包含，則跳過對該結(jié)點的子樹的搜索，向上回溯;否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。

回溯法的基本步驟：

（1）針對所給問題，定義問題的解空間;

（2）確定解空間結(jié)構(gòu);

（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

4 分支限界法

以廣度優(yōu)先或以最優(yōu)目標(biāo)優(yōu)先的方式搜索問題的解空間樹的算法稱為分支限界法。分支限界法可以以最優(yōu)目標(biāo)優(yōu)先的方式搜索，可以解決求可行解和最優(yōu)解的問題。

分支限界法的算法思想：解空間樹上的一個結(jié)點成為擴(kuò)展結(jié)點后，產(chǎn)生所有兒子結(jié)點。利用剪枝函數(shù)，把導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的結(jié)點剪除，其余結(jié)點加入活結(jié)點表。一直到找到所需的解或活結(jié)點表為空時結(jié)束。根據(jù)結(jié)點加入活結(jié)點表的順序不同，分支限界法可以分為隊列式分支限界法和優(yōu)先隊列式分支限界法。

分支限界法的基本步驟：

（1）針對所給問題，定義問題的解空間;

（2）確定解空間結(jié)構(gòu);

（3）以廣度優(yōu)先或以最優(yōu)目標(biāo)優(yōu)先搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

5 分支限界法與回溯法的區(qū)別

求解目標(biāo)不同：回溯法是找出滿足約束條件的所有解。分支限界法找出滿足條件的一個解，或某種意義下的最優(yōu)解。搜索方式不同：回溯法，深度優(yōu)先。分支限界法，廣度優(yōu)先或最優(yōu)目標(biāo)優(yōu)先。

6 應(yīng)用實例

例2.最小重量機(jī)器設(shè)計問題

某一機(jī)器由n個零件組成，每一種零件由m個供應(yīng)商處提供。設(shè) wij 和cij分別是供應(yīng)商j 提供零件i的重量和價格。求總價格不超過d的最小重量機(jī)器設(shè)計。

因為該問題需要求最優(yōu)解，所以用分支限界法求解。

7 總結(jié)

我們正處于信息爆炸的時代，需要進(jìn)行窮舉式搜索的問題會越來越多。分支限界法和回溯法作為最常用的搜索算法，一定會得到越來越多的應(yīng)用。

參考文獻(xiàn)：

[1] 王劍輝，梁路，王彪.基于分支限界的不平衡氣象數(shù)據(jù)晴雨分析[J].計算機(jī)應(yīng)用研究，2016，33（6）：1648-1652.

[2] 劉家保，陸一南，陳中華.一類新的平面圖的超邊幻和標(biāo)號[J].北華大學(xué)學(xué)報（自然科學(xué)版），2012，13（1）：41-43.

[3] 程國忠，張世祿.三個典型問題的回溯算法[J].四川師范學(xué)院學(xué)報（自然科學(xué)版），2000（2）：187-191.

[4] 楊元生，張成學(xué).在有向圖中尋找哈密頓回路的快速回溯法[J].大連理工大學(xué)學(xué)報，1989（2）：223-228+236

[5] 王曉東. 計算機(jī)算法設(shè)計與分析. 第5版[M]. 北京：清華大學(xué)出版社，2018.

【通聯(lián)編輯：王力】