搜索算法在大學(xué)生程序設(shè)計(jì)競賽中的應(yīng)用

呂曉聰 賴啟騰 徐海力

摘 要：在運(yùn)用計(jì)算機(jī)技術(shù)時(shí)，如果出現(xiàn)了一些較為復(fù)雜的問題，那么我們就可以采用搜索算法來進(jìn)行解決，這種方法在計(jì)算機(jī)技術(shù)中起著至關(guān)重要的作用，并且在相關(guān)的程序設(shè)計(jì)競賽中，搜索算法也是考察的重點(diǎn)之一。運(yùn)用簡單卻嚴(yán)密的算法來解決實(shí)際問題是鍛煉一個(gè)人基本功和積累潛力最強(qiáng)有力的途徑，深度優(yōu)先搜索和廣度優(yōu)先搜索是搜索算法中最為關(guān)鍵的兩部分，要想熟練的運(yùn)用搜索算法，我們就必須了解這兩種搜索算法。其次，探討搜索算法的規(guī)律，根據(jù)不同問題的特點(diǎn)制定不同的搜索方案，這也是我們熟練運(yùn)用搜索算法的必然工作之一。

關(guān)鍵詞：深度優(yōu)先搜索；廣度優(yōu)先搜索；剪枝；啟發(fā)式搜索；程序設(shè)計(jì)

隨著社會(huì)的發(fā)展，計(jì)算機(jī)技術(shù)水平也變得越來越高，現(xiàn)階段，很多計(jì)算機(jī)都已經(jīng)具備高性能的操作方法，而搜索算法在計(jì)算機(jī)技術(shù)中起著至關(guān)重要的作用，它可以利用計(jì)算機(jī)的高性能在一定的時(shí)間內(nèi)有效的求出問題解決的方法，也正是因?yàn)檫@一點(diǎn)，很多學(xué)者都將目光放到了搜索算法當(dāng)中，并且這種算法也得到了大多數(shù)人的關(guān)注?，F(xiàn)在，越來越多的大學(xué)生都開始關(guān)注起計(jì)算機(jī)程序設(shè)計(jì)競賽，參加到這類競賽，可以讓大學(xué)生提高利用編程解決實(shí)際問題的能力，同時(shí)也能將一些方法靈活地運(yùn)用在不同的問題之中，總而言之，大學(xué)生積極的參加到這類競賽中可以提高自己的編程能力。

1 搜索算法

搜索算法是利用計(jì)算機(jī)高性能的特點(diǎn)通過遍歷每一種可能性來尋求解決問題的方案，一般包括枚舉法、深度優(yōu)先（DFS）、廣度優(yōu)先（BFS）、A*算法等等。本文主要探討深度優(yōu)先算法和廣度優(yōu)先算法這兩種較通用的算法。

深度優(yōu)先算法，顧名思義，以深度優(yōu)先進(jìn)行搜索，是圖算法的一種。英文全稱為Depth First Search。深度優(yōu)先搜索的實(shí)質(zhì)是從某個(gè)未被訪問過的節(jié)點(diǎn)出發(fā)，不斷訪問與當(dāng)前結(jié)點(diǎn)相鄰且未被訪問過的結(jié)點(diǎn)，如果不存在這樣的結(jié)點(diǎn)，則返回上一個(gè)結(jié)點(diǎn)。這一特性與遞歸的思想十分一致，在當(dāng)前所要做的事情和下一步所要做的事情是一致的，所以，深度優(yōu)先搜索用遞歸實(shí)現(xiàn)十分簡單，當(dāng)然，用非遞歸的方法同樣可以實(shí)現(xiàn)。當(dāng)結(jié)點(diǎn)返回到上一結(jié)點(diǎn)之后，DFS就可以沿另外一個(gè)方向進(jìn)行搜索，當(dāng)其找到最終目標(biāo)之后，搜索工作就會(huì)結(jié)束。深度優(yōu)先搜索并不是完美無缺的，也存在一些問題，當(dāng)數(shù)據(jù)規(guī)模比較大，求解問題所用的時(shí)間會(huì)很長，在不限制搜索深度的情況下，可能引起堆棧溢出，從而找不到解。而且，在找到解的情況下，也不能保證找到的是問題的最優(yōu)解。

廣度優(yōu)先搜索，又稱為寬度優(yōu)先搜索，也是圖算法的一種，有點(diǎn)類似于樹中的層序遍歷，從某個(gè)未被訪問過的結(jié)點(diǎn)出發(fā)，假設(shè)每兩個(gè)相鄰結(jié)點(diǎn)的距離為1，先訪問與起始結(jié)點(diǎn)距離為1的所有結(jié)點(diǎn)，再訪問與起始結(jié)點(diǎn)距離為2且未被訪問過的結(jié)點(diǎn)，以此類推，直至所有的結(jié)點(diǎn)都被訪問過。廣度優(yōu)先搜索的搜索方式更為細(xì)致，當(dāng)問題有解時(shí)，可以找到最優(yōu)解，而且它會(huì)將每個(gè)出口的路徑都記錄下來，就算經(jīng)過不同的路口，它也會(huì)按照同樣的方式進(jìn)行記錄。但是在最后一層的搜索時(shí)，廣度優(yōu)先搜索可能會(huì)采取一次性輸出可能情況的手段，這就導(dǎo)致所需的存儲(chǔ)空間較大。而且相比于深度優(yōu)先搜索而言，效率比較低。

一般來說，深度優(yōu)先搜索和廣度優(yōu)先搜索可以解決大多數(shù)的搜索問題，但是有些情況下，它們會(huì)受到內(nèi)存、時(shí)間等因素的限制，這就導(dǎo)致在實(shí)際問題中，這兩種搜索方式無法找到最優(yōu)的解決方案。針對(duì)這一問題，我們必須對(duì)這兩種搜索方式進(jìn)行一定的改進(jìn)。

2 搜索算法的選擇與優(yōu)化

2.1 搜索策略選取原則

一般來說，深度優(yōu)先搜索和廣度優(yōu)先搜索都能解決一些比較簡單的問題，但由于深度優(yōu)先搜索編寫方便，而且狀態(tài)管理也比較方便，所以通常采用深度優(yōu)先搜索。如果遇到的問題需要用多個(gè)路徑來進(jìn)行問題求解，那么我們也可以選擇深度優(yōu)先搜索，因?yàn)樯疃葍?yōu)先搜索在得到一個(gè)路徑之后就可以直接進(jìn)行輸出，所以選擇它可以最快的將問題解決。但是對(duì)于廣度優(yōu)先搜索來說，如果用它來解決這種多路徑的問題，那么就會(huì)消耗大量的時(shí)間，因?yàn)樵谒阉鬟^程中，廣度優(yōu)先搜索會(huì)把路徑的節(jié)點(diǎn)全部保存起來，直到最后一個(gè)節(jié)點(diǎn)之后才會(huì)進(jìn)行輸出，這樣不僅浪費(fèi)空間，還會(huì)影響效率。對(duì)于廣度優(yōu)先搜索來說，最優(yōu)解的問題求解是最適合它的。

根據(jù)以上搜索策略的選取原則，我們?cè)趪鴥?nèi)的一些OJ平臺(tái)（杭電、洛谷、51nod等等）選取了一些題目進(jìn)行分析驗(yàn)證，都取得了不錯(cuò)的效果。

2.2 優(yōu)化搜索策略

由于深度優(yōu)先搜索和廣度優(yōu)先搜索是兩種比較通用的搜索方法，在編程時(shí)我們往往采用較固定的模板，這樣一來，當(dāng)我們面對(duì)較為復(fù)雜的問題，編寫的程序執(zhí)行效率顯然不高。因此，我們往往需要根據(jù)不同的問題對(duì)算法進(jìn)行優(yōu)化。

剪枝是搜索算法中常常采用的一種優(yōu)化方法，也是大學(xué)生程序設(shè)計(jì)競賽中的重要考點(diǎn)之一，如果我們的程序在比賽中運(yùn)行超時(shí)，不妨考慮一下剪枝優(yōu)化。剪枝的思想十分簡單，它是根據(jù)上一層已經(jīng)得到的結(jié)果進(jìn)行判斷，如果在現(xiàn)有條件下有可能出現(xiàn)問題的解，則繼續(xù)往下搜索，否則立即返回上一層。這樣一來，就可以避免搜索一些肯定沒有結(jié)果的分支，從而提高了程序的效率。

啟發(fā)式搜索也是一種對(duì)搜索策略的優(yōu)化，它引導(dǎo)搜索朝著最后可能的方向前進(jìn)，以搜索算法中著名的八數(shù)碼問題為例，要想將數(shù)碼移動(dòng)步數(shù)降到最低，那么我們千萬不能采取深度優(yōu)先搜索方式，因?yàn)檫@種運(yùn)算方式中采用了太多沒有意義的中間狀態(tài)，它會(huì)使運(yùn)算過程變得過于復(fù)雜。雖然廣地優(yōu)先搜索可以在運(yùn)算過程中找到最短的路徑，但由于八數(shù)碼問題空間過高，運(yùn)用廣度優(yōu)先搜索仍會(huì)消耗大量的時(shí)間以及存儲(chǔ)空間，所以綜合來看，這兩種運(yùn)算方式都不合適。然而，啟發(fā)式搜索可以在搜索前對(duì)相應(yīng)的位置進(jìn)行評(píng)估，并且按照指定的方向進(jìn)行搜索，通過比較我們可以得出一個(gè)結(jié)論，在進(jìn)行復(fù)雜問題解決的時(shí)候，啟發(fā)式搜索具有較大的優(yōu)勢，所以在解決八數(shù)碼問題的時(shí)候，我們通常采用的搜索算法都是啟發(fā)式搜索。

3 結(jié)語

綜上所述我們可以看出，現(xiàn)在，計(jì)算機(jī)的發(fā)展和搜索算法有著密切的關(guān)聯(lián)，兩者缺一不可。而且隨著社會(huì)的進(jìn)步，搜索的應(yīng)用也變得越來越廣泛，現(xiàn)階段，我們的學(xué)習(xí)目標(biāo)主要就是如何運(yùn)用簡單的運(yùn)算方法來解決問題，這樣可以有效的增強(qiáng)我們的個(gè)人能力以及解決問題的能力。其次，在現(xiàn)有的計(jì)算機(jī)程序設(shè)計(jì)競賽中，搜索問題所占的比例是極高的，這也說明了一個(gè)問題，搜索算法在計(jì)算機(jī)技術(shù)中起著極為關(guān)鍵的作用。搜索策略是搜索過程中最重要的一步，好的策略可以有效的解決問題，為我們節(jié)省時(shí)間。在面對(duì)不同的問題時(shí)，我們要學(xué)會(huì)選擇不同的方式，合理的搜索策略不僅可以節(jié)省時(shí)間，同時(shí)還可以在很大程度上提高搜索效率。

參考文獻(xiàn)

[1]曲大鵬，張迪，連秋雨，等.搜索算法在計(jì)算機(jī)程序設(shè)計(jì)競賽中的研究[J].遼寧大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，（3）：209-213.

[2]劉洋.點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)[D].安徽大學(xué)，2016.

[3]光洋.愛恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)的研究與實(shí)現(xiàn)[D].安徽大學(xué)，2016.

（作者單位：1.江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院；2.江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院；3.江蘇科技大學(xué) 材料科學(xué)與工程學(xué)院）