搜索算法在大學生程序設計競賽中的應用

呂曉聰 賴啟騰 徐海力

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

關鍵詞：深度優先搜索；廣度優先搜索；剪枝；啟發式搜索；程序設計

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

1 搜索算法

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

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

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

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

2 搜索算法的選擇與優化

2.1 搜索策略選取原則

一般來說，深度優先搜索和廣度優先搜索都能解決一些比較簡單的問題，但由于深度優先搜索編寫方便，而且狀態管理也比較方便，所以通常采用深度優先搜索。如果遇到的問題需要用多個路徑來進行問題求解，那么我們也可以選擇深度優先搜索，因為深度優先搜索在得到一個路徑之后就可以直接進行輸出，所以選擇它可以最快的將問題解決。但是對于廣度優先搜索來說，如果用它來解決這種多路徑的問題，那么就會消耗大量的時間，因為在搜索過程中，廣度優先搜索會把路徑的節點全部保存起來，直到最后一個節點之后才會進行輸出，這樣不僅浪費空間，還會影響效率。對于廣度優先搜索來說，最優解的問題求解是最適合它的。

根據以上搜索策略的選取原則，我們在國內的一些OJ平臺（杭電、洛谷、51nod等等）選取了一些題目進行分析驗證，都取得了不錯的效果。

2.2 優化搜索策略

由于深度優先搜索和廣度優先搜索是兩種比較通用的搜索方法，在編程時我們往往采用較固定的模板，這樣一來，當我們面對較為復雜的問題，編寫的程序執行效率顯然不高。因此，我們往往需要根據不同的問題對算法進行優化。

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

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

3 結語

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

參考文獻

[1]曲大鵬，張迪，連秋雨，等.搜索算法在計算機程序設計競賽中的研究[J].遼寧大學學報（自然科學版），2016，（3）：209-213.

[2]劉洋.點格棋博弈中UCT算法的研究與實現[D].安徽大學，2016.

[3]光洋.愛恩斯坦棋計算機博弈系統的研究與實現[D].安徽大學，2016.

（作者單位：1.江蘇科技大學 計算機科學與工程學院；2.江蘇科技大學 計算機學院；3.江蘇科技大學 材料科學與工程學院）