算法（Algorithm）是為了解決一個(gè)特定的問(wèn)題而精心設(shè)計(jì)的一套數(shù)學(xué)模型以及在這套數(shù)學(xué)模型上的一系列操作步驟，這些操作步驟是將描述的輸入數(shù)據(jù)逐步處理、轉(zhuǎn)換，并最后得到一個(gè)確定的結(jié)果。當(dāng)然，準(zhǔn)確性是基本前提，時(shí)間和空間效率是衡量一個(gè)算法優(yōu)劣的重要評(píng)估標(biāo)準(zhǔn)。算法通常在函數(shù)中使用控制結(jié)構(gòu)來(lái)實(shí)現(xiàn)。
1 算法分類(lèi)
算法是一個(gè)比較大的概念范疇，為便于理解，可以從算法思想，典型應(yīng)用及與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，將算法分為三類(lèi)：
1.1 經(jīng)典算法思想
一般來(lái)說(shuō)，算法設(shè)計(jì)沒(méi)有什么固定的方法可循。但是通過(guò)大量的實(shí)踐，人們也總結(jié)出算法某些共性的規(guī)律，包括窮舉法(Enumeration)、遞推法(Recurrence)、遞歸法、分治法(Divide and Conquer)、貪心法、回溯法(Backtracking)、動(dòng)態(tài)規(guī)劃法等。
1.2 經(jīng)典算法思想在典型問(wèn)題上的應(yīng)用
如排序、查找（檢索）等算法。盡管計(jì)算學(xué)科的整個(gè)發(fā)展可以很短，但前人們還是留下了很多非常經(jīng)典的算法，僅就排序而言，就可以數(shù)出一大堆，如冒泡排序法、快速排序法、選擇排序法、插入排序法、基數(shù)排序法等。
1.3 在數(shù)據(jù)結(jié)構(gòu)上應(yīng)用的算法
包括增、查、刪、改、遍歷、圖的最路徑、最小生成樹(shù)、樹(shù)的遍歷方法，線性表的二分查找，以及數(shù)據(jù)類(lèi)型的運(yùn)算符，類(lèi)類(lèi)型的操作符重載。
有些算法充滿著智慧，如Dijistra最短路徑、Huffman樹(shù)、蒙特卡洛方法、快速排序、堆排序、紅黑樹(shù)、A+樹(shù)、字符串匹配的KMP算法等。
2 從算法中的分治思想來(lái)體現(xiàn)各類(lèi)算法思想中的細(xì)微區(qū)別
復(fù)雜的問(wèn)題可以分而治之。對(duì)于復(fù)雜的問(wèn)題，通常都需要應(yīng)用分治的思想，同時(shí)，很多算法中也有分治思想的體現(xiàn)。分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：
① 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；
② 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)
③ 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；
④ 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。
因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。
遞歸的子問(wèn)題之間是同類(lèi)、縱向的關(guān)系，而枚舉是橫向的關(guān)系。
如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。
特征④涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。
動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。
遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。
通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。
顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路徑問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。
貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類(lèi)算法的一個(gè)共同點(diǎn)。嚴(yán)格地說(shuō)，用動(dòng)態(tài)規(guī)劃的問(wèn)題一般都有前后重疊的，需要用前一階段的結(jié)果局部貪心推出下一個(gè)階段結(jié)果。貪心算法一般要得到最優(yōu)解只能各個(gè)階段沒(méi)有重疊，以局部最優(yōu)構(gòu)造全局最優(yōu)。
3 了解算法的8個(gè)要點(diǎn)
3.1 算法是程序設(shè)計(jì)的“熟語(yǔ)”（常見(jiàn)短語(yǔ)）,有大算法與有小算法；
3.2 算法中解決問(wèn)題的步驟是明確且有限的；
3.3 計(jì)算機(jī)不靠直覺(jué)而是機(jī)械地解決問(wèn)題（就是簡(jiǎn)單傻瓜式地一步一步做）；
3.4 了解并應(yīng)用典型算法；
3.5 利用計(jì)算機(jī)的處理速度；無(wú)論是多么冗長(zhǎng)繁瑣的步驟，只要明確并且機(jī)械就是優(yōu)秀的算法；
3.6 使用編程技巧提升程序執(zhí)行速度；也就是說(shuō)解決問(wèn)題的方法是可以優(yōu)化的，就像做事有方法，效率就會(huì)高一樣，算法也是可以優(yōu)化的；
3.7 找出數(shù)字間的規(guī)律；因?yàn)樵谟?jì)算機(jī)中所有的信息都可以用數(shù)字表示，因此構(gòu)造算法，就可以利用到存在于數(shù)字間的規(guī)律。規(guī)律+邏輯；
3.8 先在紙上考慮算法；也就是先在紙上把步驟用文字或圖形表示出來(lái)，用簡(jiǎn)單的數(shù)字先做驗(yàn)證；
4 九種基本算法思想簡(jiǎn)述
4.1枚舉法Enumeration method
枚舉算法思想的最大特點(diǎn)是，在面對(duì)任何問(wèn)題時(shí)它會(huì)去嘗試每一種解決方法。在進(jìn)行歸納推理時(shí)，如果逐個(gè)考察了某類(lèi)事件的所有可能情況，因而得出一般結(jié)論，那么這個(gè)結(jié)論是可靠的，這種歸納方法叫作枚舉法。
枚舉算法的思想是：將問(wèn)題的所有可能的答案一一列舉，然后根據(jù)條件判斷此答案是否合適，保留合適的，丟棄不合適的。在C語(yǔ)言中，枚舉算法一般使用while循環(huán)實(shí)現(xiàn)。使用枚舉算法解題的基本思路如下。
① 確定枚舉對(duì)象、枚舉范圍和判定條件。
② 逐一列舉可能的解，驗(yàn)證每個(gè)解是否是問(wèn)題的解。
枚舉算法一般按照如下3 個(gè)步驟進(jìn)行。
① 題解的可能范圍，不能遺漏任何一個(gè)真正解，也要避免有重復(fù)。
② 判斷是否是真正解的方法。
③ 使可能解的范圍降至最小，以便提高解決問(wèn)題的效率。
4.2迭代法Iteration method
迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過(guò)程。與迭代法相對(duì)應(yīng)的是直接法（或者稱為一次解法），即一次性解決問(wèn)題。迭代法又分為精確迭代和近似迭代。“二分法”和“牛頓迭代法”屬于近似迭代法，功能都比較類(lèi)似。
迭代算法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。
在使用迭代算法解決問(wèn)題時(shí)，需要做好如下3 個(gè)方面的工作。
（1）確定迭代變量
在可以使用迭代算法解決的問(wèn)題中，至少存在一個(gè)迭代變量，即直接或間接地不斷由舊值遞推出新值的變量。
（2）建立迭代關(guān)系式
迭代關(guān)系式是指如何從變量的前一個(gè)值推出其下一個(gè)值的公式或關(guān)系。通?？梢允褂眠f推或倒推的方法來(lái)建立迭代關(guān)系式，迭代關(guān)系式的建立是解決迭代問(wèn)題的關(guān)鍵。
（3）對(duì)迭代過(guò)程進(jìn)行控制
在編寫(xiě)迭代程序時(shí)，必須確定在什么時(shí)候結(jié)束迭代過(guò)程，不能讓迭代過(guò)程無(wú)休止地重復(fù)執(zhí)行下去。通?？煞譃槿缦聝煞N情況來(lái)控制迭代過(guò)程：
① 所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來(lái)，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來(lái)實(shí)現(xiàn)對(duì)迭代過(guò)程的控制；
② 所需的迭代次數(shù)無(wú)法確定，需要進(jìn)一步分析出用來(lái)結(jié)束迭代過(guò)程的條件。
4.3遞推法Recurrence method
與枚舉算法思想相比，遞推算法能夠通過(guò)已知的某個(gè)條件，利用特定的關(guān)系得出中間推論，然后逐步遞推，直到得到結(jié)果為止。由此可見(jiàn)，遞推算法要比枚舉算法聰明，它不會(huì)嘗試每種可能的方案。
遞推算法可以不斷利用已有的信息推導(dǎo)出新的東西，在日常應(yīng)用中有如下兩種遞推算法。
① 順推法：從已知條件出發(fā)，逐步推算出要解決問(wèn)題的方法。例如斐波那契數(shù)列就可以通過(guò)順推法不斷遞推算出新的數(shù)據(jù)。
② 逆推法：從已知的結(jié)果出發(fā)，用迭代表達(dá)式逐步推算出問(wèn)題開(kāi)始的條件，即順推法的逆過(guò)程。
4.4遞歸法Recursion method
因?yàn)檫f歸算法思想往往用函數(shù)的形式來(lái)體現(xiàn)，所以遞歸算法需要預(yù)先編寫(xiě)功能函數(shù)。這些函數(shù)是獨(dú)立的功能，能夠?qū)崿F(xiàn)解決某個(gè)問(wèn)題的具體功能，當(dāng)需要時(shí)直接調(diào)用這個(gè)函數(shù)即可。
在計(jì)算機(jī)編程應(yīng)用中，遞歸算法對(duì)解決大多數(shù)問(wèn)題是十分有效的，它能夠使算法的描述變得簡(jiǎn)潔而且易于理解。遞歸算法有如下3 個(gè)特點(diǎn)。
① 遞歸過(guò)程一般通過(guò)函數(shù)或子過(guò)程來(lái)實(shí)現(xiàn)。
② 遞歸算法在函數(shù)或子過(guò)程的內(nèi)部，直接或者間接地調(diào)用自己的算法。
③ 遞歸算法實(shí)際上是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類(lèi)問(wèn)題的子問(wèn)題，然后再遞歸調(diào)用函數(shù)或過(guò)程來(lái)表示問(wèn)題的解。
在使用遞歸算法時(shí)，應(yīng)該注意如下4 點(diǎn)。
① 遞歸是在過(guò)程或函數(shù)中調(diào)用自身的過(guò)程。
② 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，這稱為遞歸出口。
③ 遞歸算法通常顯得很簡(jiǎn)潔，但是運(yùn)行效率較低，所以一般不提倡用遞歸算法設(shè)計(jì)程序。
④ 在遞歸調(diào)用過(guò)程中，系統(tǒng)用棧來(lái)存儲(chǔ)每一層的返回點(diǎn)和局部量。如果遞歸次數(shù)過(guò)多，則容易造成棧溢出，所以一般不提倡用遞歸算法設(shè)計(jì)程序。
4.5分治法Divide and conquer
分治算法采取各個(gè)擊破的方法，將一個(gè)規(guī)模為N的問(wèn)題分解為K個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同。只要求出子問(wèn)題的解，就可得到原問(wèn)題的解。
在編程過(guò)程中，經(jīng)常遇到處理數(shù)據(jù)相當(dāng)多、求解過(guò)程比較復(fù)雜、直接求解法會(huì)比較耗時(shí)的問(wèn)題。在求解這類(lèi)問(wèn)題時(shí)，可以采用各個(gè)擊破的方法。具體做法是：先把這個(gè)問(wèn)題分解成幾個(gè)較小的子問(wèn)題，找到求出這幾個(gè)子問(wèn)題的解法后，再找到合適的方法，把它們組合成求整個(gè)大問(wèn)題的解。如果這些子問(wèn)題還是比較大，還可以繼續(xù)再把它們分成幾個(gè)更小的子問(wèn)題，以此類(lèi)推，直至可以直接求出解為止。這就是分治算法的基本思想。
使用分治算法解題的一般步驟如下。
① 分解，將要解決的問(wèn)題劃分成若干個(gè)規(guī)模較小的同類(lèi)問(wèn)題。
② 求解，當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決。
③ 合并，按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。
4.6動(dòng)態(tài)規(guī)劃Dynamic programming
動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程(multistep decision process)的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法——動(dòng)態(tài)規(guī)劃。
(1) 基本概念
每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，所以，這種多階段最優(yōu)化決策解決問(wèn)題的過(guò)程就稱為動(dòng)態(tài)規(guī)劃。
(2) 基本思想
與分治法類(lèi)似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題，按順序求解子問(wèn)題，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解，依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。
與分治法最大的差別：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。
(3) 適用的情況
① 最優(yōu)化原理：如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。
② 無(wú)后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響，也就是說(shuō)，某狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
④ 有重疊子問(wèn)題：即子問(wèn)題之間是不獨(dú)立的，一個(gè)子問(wèn)題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒(méi)有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)）
(4) 解題步驟
動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開(kāi)始，通過(guò)對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟：
初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
① 劃分階段：按照問(wèn)題的時(shí)間特征，把問(wèn)題分為若干個(gè)階段，在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。
② 確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)，當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。
③確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫(xiě)出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來(lái)確定決策方法和狀態(tài)轉(zhuǎn)移方程。
④ 尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。
一般，只要解決問(wèn)題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫(xiě)出狀態(tài)轉(zhuǎn)移方程。實(shí)際應(yīng)用中可以按以下幾個(gè)簡(jiǎn)化的步驟進(jìn)行設(shè)計(jì)：
① 分析最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征。
② 遞歸的定義最優(yōu)解。
③ 以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值。
④ 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問(wèn)題的最優(yōu)解。
(5) 算法實(shí)現(xiàn)的說(shuō)明
動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于上面4個(gè)步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。使用動(dòng)態(tài)規(guī)劃求解問(wèn)題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：
① 問(wèn)題的階段
② 每個(gè)階段的狀態(tài)
③ 從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。
遞推關(guān)系必須是從次小的問(wèn)題開(kāi)始到較大的問(wèn)題之間的轉(zhuǎn)化，從這個(gè)角度來(lái)說(shuō)，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來(lái)實(shí)現(xiàn)，不過(guò)因?yàn)檫f推可以充分利用前面保存的子問(wèn)題的解來(lái)減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō)，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。
確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過(guò)程就可以用一個(gè)最優(yōu)決策表來(lái)描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問(wèn)題狀態(tài)，表格需要填寫(xiě)的數(shù)據(jù)一般對(duì)應(yīng)此問(wèn)題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值（如最短路徑，最長(zhǎng)公共子序列，最大價(jià)值等），填表的過(guò)程就是根據(jù)遞推關(guān)系，從1行1列開(kāi)始，以行或者列優(yōu)先的順序，依次填寫(xiě)表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過(guò)簡(jiǎn)單的取舍或者運(yùn)算求得問(wèn)題的最優(yōu)解。
4.7貪心法Greedy
貪心算法也被稱為貪婪算法，它在求解問(wèn)題時(shí)總想用在當(dāng)前看來(lái)是最好方法來(lái)實(shí)現(xiàn)。這種算法思想不從整體最優(yōu)上考慮問(wèn)題，僅僅是在某種意義上的局部最優(yōu)求解。雖然貪心算法并不能得到所有問(wèn)題的整體最優(yōu)解，但是面對(duì)范圍相當(dāng)廣泛的許多問(wèn)題時(shí)，能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。由此可見(jiàn)，貪心算法只是追求某個(gè)范圍內(nèi)的最優(yōu)，可以稱之為“溫柔的貪婪”。
貪心算法從問(wèn)題的某一個(gè)初始解出發(fā)，逐步逼近給定的目標(biāo)，以便盡快求出更好的解。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，就停止算法，給出一個(gè)近似解。由貪心算法的特點(diǎn)和思路可看出，貪心算法存在以下3 個(gè)問(wèn)題。
① 不能保證最后的解是最優(yōu)的。
② 不能用來(lái)求最大或最小解問(wèn)題。
③ 只能求滿足某些約束條件的可行解的范圍。
貪心算法的基本思路如下。
① 建立數(shù)學(xué)模型來(lái)描述問(wèn)題。
② 把求解的問(wèn)題分成若干個(gè)子問(wèn)題。
③ 對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。
④ 把子問(wèn)題的局部最優(yōu)解合并成原來(lái)解問(wèn)題的一個(gè)解。
實(shí)現(xiàn)該算法的基本過(guò)程如下。
（1）從問(wèn)題的某一初始解出發(fā)。
（2）while能向給定總目標(biāo)前進(jìn)一步。
（3）求出可行解的一個(gè)解元素。
（4）由所有解元素組合成問(wèn)題的一個(gè)可行解。
4.8回溯法Recursive search
回溯法也叫試探法，試探法的處事方式比較委婉，它先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一進(jìn)行枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是正確的解時(shí)，就選擇下一個(gè)候選解。如果當(dāng)前候選解除了不滿足問(wèn)題規(guī)模要求外能夠滿足所有其他要求時(shí)，則繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。在試探算法中，放棄當(dāng)前候選解，并繼續(xù)尋找下一個(gè)候選解的過(guò)程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探的過(guò)程稱為向前試探。
使用試探算法解題的基本步驟如下所示。
① 針對(duì)所給問(wèn)題，定義問(wèn)題的解空間。
② 確定易于搜索的解空間結(jié)構(gòu)。
③ 以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。
試探法為了求得問(wèn)題的正確解，會(huì)先委婉地試探某一種可能的情況。在進(jìn)行試探的過(guò)程中，一旦發(fā)現(xiàn)原來(lái)選擇的假設(shè)情況是不正確的，立即會(huì)自覺(jué)地退回一步重新選擇，然后繼續(xù)向前試探，如此這般反復(fù)進(jìn)行，直至得到解或證明無(wú)解時(shí)才死心。
4.9分支限界法Branch and Bound Method
分支限界法類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解的算法，但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間樹(shù)中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。
由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹(shù)上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。
分支限界法的搜索策略：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。
分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。問(wèn)題的解空間樹(shù)是表示問(wèn)題解空間的一棵有序樹(shù)，常見(jiàn)的有子集樹(shù)和排列樹(shù)。在搜索問(wèn)題的解空間樹(shù)時(shí)，分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止。
回溯法深度優(yōu)先搜索堆?；罱Y(jié)點(diǎn)的所有可行子結(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿足約束條件的所有解。
分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列、優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)找出滿足約束條件的一個(gè)解或特定意義下的最優(yōu)解。
