數(shù)據(jù)結(jié)構(gòu)與算法10

1、第10章 算法設(shè)計(jì)策略及應(yīng)用實(shí)例（4課時(shí)）本章介紹了算法設(shè)計(jì)策略和應(yīng)用實(shí)例，主要目的有兩個(gè):首先，讓讀者知道每種算法的適用條件，即何時(shí)可以使用和何時(shí)不能使用某種算法設(shè)計(jì)策略；其次，讓讀者學(xué)習(xí)基本的算法設(shè)計(jì)策略，即掌握如何描述自己的問題和高效、快速地解決問題。本章將進(jìn)一步介紹五種常用算法設(shè)計(jì)策略的基本思想和實(shí)現(xiàn)方法，這些策略包括分治策略、貪心策略、動(dòng)態(tài)規(guī)劃策略、回溯策略和分支限界策略，以及它們的具體應(yīng)用實(shí)例。10.1.1 概述概述10.1.2 算法設(shè)計(jì)步驟和程序模式算法設(shè)計(jì)步驟和程序模式10.1.3 分治策略應(yīng)用實(shí)例分治策略應(yīng)用實(shí)例 分治策略是一類算法設(shè)計(jì)策略，它將原問題分解成若干部分，從而產(chǎn)生

2、若干子問題，這些子問題互相獨(dú)立且與原問題類型相同，然后解決這些子問題，最后把這些子問題的解合并成原問題的解。 分治策略所能解決的問題，一般具有以下三個(gè)特征：n原問題可以分解成規(guī)模較小、相互獨(dú)立和類型相同的子問題；n子問題的規(guī)模縮小到一定的程度，就不需要再分解，可以很容易地求解；n所有子問題的解能夠合并成原問題的解。10.1.1 概述概述如圖10-1所示，采用分治策略的算法設(shè)計(jì)都包括分解、求解和合并三個(gè)步驟：（1）分解：將原問題分解為若干個(gè)規(guī)模較小、相互獨(dú)立、與原問題類型相同或相似的子問題；（2）求解：若子問題縮小到容易解決的規(guī)模，則直接求解，否則遞歸地求解子問題；（3）合并：將各個(gè)子問題的解合

3、并為原問題的解。10.1.2 算法設(shè)計(jì)步驟和程序模式算法設(shè)計(jì)步驟和程序模式原原問問題題問問題題分分解解子子問問題題子子問問題題子子問問題題求求解解子子問問題題求求解解子子問問題題求求解解子子問問題題子子問問題題解解子子問問題題解解子子問問題題解解合合并并子子解解原原問問題題的的解解圖10-1 分治策略示意圖【例10-1】矩陣乘積問題。因?yàn)榫仃嚳梢苑奖愕乇硎緝蓚€(gè)集合中元素之間的關(guān)系，所以被用于通信網(wǎng)絡(luò)和交通運(yùn)輸系統(tǒng)等模型，在這些模型中經(jīng)常用到矩陣的乘法。根據(jù)矩陣乘積的定義，兩個(gè)n階矩陣乘積的時(shí)間復(fù)雜度為O(n3)。Strassen根據(jù)分治策略設(shè)計(jì)矩陣乘積的算法，降低時(shí)間復(fù)雜度。假設(shè)n為2的整數(shù)冪

4、，A、B、C都是n階的矩陣，每個(gè)矩陣可以分解成4個(gè)n/2階的矩陣。Strassen計(jì)算如下7個(gè)矩陣。10.1.3 分治策略應(yīng)用實(shí)例分治策略應(yīng)用實(shí)例111211121112212221222122CCAABBCCAABBStrassen計(jì)算如下7個(gè)矩陣。 最后，矩陣乘積的結(jié)果由7個(gè)矩陣得出。10.1.3 分治策略應(yīng)用實(shí)例分治策略應(yīng)用實(shí)例1112211222212211311122242221115111222621111112712222122()()()()()()()()()()MAABBMAABMABBMABBMAABMAABBMAABB分析：按照矩陣的定義，兩個(gè)n階矩陣乘積中有n2個(gè)元素

5、，計(jì)算每個(gè)元素需要n次乘法和(n-1)次加法，所以需要n3次乘法和n2(n-1)次加法，其時(shí)間復(fù)雜度為O(n3)，而通過分治策略設(shè)計(jì)的矩陣乘積算法可以降低時(shí)間復(fù)雜度為O(n2.81)。10.1.3 分治策略應(yīng)用實(shí)例分治策略應(yīng)用實(shí)例14573511122413262122MMMMMMCCCMMMMMMCC【例10-2】計(jì)算一個(gè)數(shù)列的逆序數(shù)量。例如，已知一個(gè)數(shù)列3、1、2、5、4，則其中存在三個(gè)逆序：（3，1），（3，2），（5，4），如圖10-2所示。窮舉法的用時(shí)為O(n2)，而采用分治策略設(shè)計(jì)的算法時(shí)間復(fù)雜度為O(nlogn)。采用分治策略計(jì)算逆序數(shù)量的基本思想：假設(shè)數(shù)列保存在數(shù)組a中，將數(shù)組

6、a中的元素劃分成大致相等的前后兩部分a1和a2，然后分別計(jì)算a1和a2中逆序的數(shù)量，最后計(jì)算逆序?qū)Γ╝i,aj）的數(shù)量，其中ai是a1中的元素，aj是a2中的元素。10.1.3 分治策略應(yīng)用實(shí)例分治策略應(yīng)用實(shí)例貪心策略是比較容易的算法設(shè)計(jì)策略，雖然它看上去既直觀又簡單，但是它卻可以廣泛地應(yīng)用于很多問題的求解，如最短路徑問題、最小生成樹、Huffman編碼、作業(yè)調(diào)度問題等。本節(jié)主要介紹貪心策略的基本知識(shí)，然后給出了貪心策略應(yīng)用實(shí)例。10.2.1 最優(yōu)化問題與最優(yōu)化原理最優(yōu)化問題與最優(yōu)化原理10.2.3算法設(shè)計(jì)步驟及程序模式算法設(shè)計(jì)步驟及程序模式10.2.2貪心策略概述貪心策略概述10.2.4貪心

7、策略應(yīng)用實(shí)例貪心策略應(yīng)用實(shí)例1.最優(yōu)化問題最優(yōu)化問題最優(yōu)化問題是在滿足一定的限制條件下，對(duì)于一個(gè)給定的優(yōu)化函數(shù)，尋找一組參數(shù)值，使得函數(shù)值最大或最小。每個(gè)最優(yōu)化問題都包含一組限制條件和一個(gè)優(yōu)化函數(shù)，符合限制條件的求解方案稱為可行解，使優(yōu)化函數(shù)取得最大（?。┲档目尚薪夥Q為最優(yōu)解。10.2.1 最優(yōu)化問題與最優(yōu)化原理最優(yōu)化問題與最優(yōu)化原理 建運(yùn)動(dòng)場的問題可以抽象為最優(yōu)化問題： （1）限制條件是建筑材料為300米。設(shè)x和y分別是矩形的長和寬，限制條件為：x+2y0，y0。 （2）代表問題解的優(yōu)劣是矩形面積，即優(yōu)化函數(shù)表示：f(x,y)=xy。 任何一組滿足限制條件“x+2y=300”的x和y都是可行

8、解，而使“xy”最大的是最優(yōu)解。10.2.1 最優(yōu)化問題與最優(yōu)化原理最優(yōu)化問題與最優(yōu)化原理n圖10-3 擬建運(yùn)動(dòng)場示意圖 2. 2.最優(yōu)化原理最優(yōu)化原理 1951年，美國數(shù)學(xué)家R.E.Bellman等人根據(jù)多階段決策問題的特點(diǎn)，提出了解決這類問題的最優(yōu)化原理(Principle of optimality)。 最優(yōu)化原理的數(shù)學(xué)語言描述為：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1、D2、Dn。如果這個(gè)決策序列是最優(yōu)的，那么對(duì)于任何一個(gè)整數(shù)k（1 k n），則Dk+1、Dk+2、Dn也是最優(yōu)的，因?yàn)椴徽撉懊鎘個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于前面決策所確定的當(dāng)前狀態(tài)。10.2.1 最

9、優(yōu)化問題與最優(yōu)化原理最優(yōu)化問題與最優(yōu)化原理 貪心策略通過一系列步驟來構(gòu)造問題的解，每一步都做出當(dāng)前來看最好的選擇，擴(kuò)展已知的部分解，直到獲得問題的完整解。這種“當(dāng)前來看最好的選擇”的策略就是該策略名稱的來源。 貪心策略求解的問題一般具有以下兩個(gè)重要的性質(zhì)n 最優(yōu)子結(jié)構(gòu)性當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問題滿足最優(yōu)化原理。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可以用貪心策略或者動(dòng)態(tài)規(guī)劃策略求解的關(guān)鍵特征。n 貪心選擇性若一個(gè)問題的全局最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來獲得，則稱該問題具有貪心選擇性。10.2.2貪心策略概述貪心策略概述 貪心選擇性可

10、從如下三個(gè)方面來理解：n可行性，即貪心選擇必須滿足問題的約束;n局部最優(yōu)性，即貪心選擇是當(dāng)前步驟中所有可行選擇中最佳的局部選擇;n不變性，即一旦做出選擇，在算法的后面步驟中就無法改變。10.2.2貪心策略概述貪心策略概述n總結(jié) 貪心策略求解的問題需要具備兩個(gè)性質(zhì)： 第一，最優(yōu)子結(jié)構(gòu)性質(zhì)； 第二，貪心選擇性質(zhì)。 第一條性質(zhì)是應(yīng)用貪心策略的基礎(chǔ)，而第二條性質(zhì)是決定使用貪心策略的關(guān)鍵。具備第一條性質(zhì)的問題，如果不具備貪心選擇性，而是具備子問題重疊性，則考慮用動(dòng)態(tài)規(guī)劃策略設(shè)計(jì)算法。10.2.2貪心策略概述貪心策略概述n 貪心策略的算法設(shè)計(jì)步驟一般分為四步：n 建立數(shù)學(xué)模型來描述問題;n 把求解的問題分

11、成若干個(gè)子問題;n 求解子問題，得到子問題的局部最優(yōu)解;n 通過貪心選擇，擴(kuò)展子問題的局部最優(yōu)解，直到構(gòu)成問題的完整解。10.2.3算法設(shè)計(jì)步驟及程序模式算法設(shè)計(jì)步驟及程序模式貪心策略的程序模式一般為：貪心策略的程序模式一般為：Greedy(C) /C是問題的輸入集合，即候選集合 S= ;/初始解集合為空集while (not Solution(S)/集合S沒有構(gòu)成問題的一個(gè)解 x=Select(C); /在候選集合C中做貪心選擇if Feasible(S, x) /判斷集合S中加入x后的解是否可行S=S+x;C=C-x; return S; 10.2.3算法設(shè)計(jì)步驟及程序模式算法設(shè)計(jì)步驟及程

12、序模式 【例10-3】用貪心策略求解活動(dòng)安排問題。設(shè)有n個(gè)活動(dòng)的集合E=1,2, ,n，其中每個(gè)活動(dòng)都要求使用同一資源，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si 和結(jié)束時(shí)間fi 且si B1-C1-D，其距離是12+13+11=36。此時(shí)，貪心策略就不能解決該問題了。10.3.1 概述概述圖10-6 貪心策略不適用的問題n多階段決策問題多階段決策問題n 如果一類活動(dòng)過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需做出決策(采取措施)，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動(dòng)路線，則稱它為多階段決策問題。

13、n最優(yōu)策略最優(yōu)策略n 對(duì)于多階段決策問題，各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使其在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。n動(dòng)態(tài)規(guī)劃的本質(zhì)動(dòng)態(tài)規(guī)劃的本質(zhì)n 動(dòng)態(tài)規(guī)劃本質(zhì)上是多階段決策過程。將問題的過程分成幾個(gè)相互聯(lián)系的階段，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求解。10.3.2動(dòng)態(tài)規(guī)劃策略的相關(guān)概念動(dòng)態(tài)規(guī)劃策略的相關(guān)概念n動(dòng)態(tài)規(guī)劃的基本術(shù)語動(dòng)態(tài)規(guī)劃的基本術(shù)語n 階段與階段變量：把一個(gè)問題的過程恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便按一定的次序去求解。階段是按問題的時(shí)間或空間的自然特征來劃分的，把

14、描述階段的變量稱為階段變量（使用字母k表示），階段變量可以是年、月、日、路段等。用動(dòng)態(tài)規(guī)劃方法解題，原問題必須能劃分為若干階段。n 狀態(tài)、狀態(tài)變量與狀態(tài)允許集合：狀態(tài)表示每個(gè)階段開始所處的自然狀況或客觀條件，通常一個(gè)階段有若干個(gè)狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量sk的取值集合稱為允許狀態(tài)集合，用Sk表示。在動(dòng)態(tài)規(guī)劃問題中，狀態(tài)是劃分階段的依據(jù)，狀態(tài)的變化就意味著階段的推移。因此，解題時(shí)首先應(yīng)明確每一階段開始時(shí)的一切可能狀態(tài)。n 決策、決策變量和決策允許集合：表示當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決

15、策。描述決策的變量，稱為決策變量，使用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。在實(shí)際問題中，決策變量的取值往往限制在一定范圍內(nèi)，此范圍稱為允許決策集合。使用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，則有uk(sk) Dk(sk)。10.3.2動(dòng)態(tài)規(guī)劃策略的相關(guān)概念動(dòng)態(tài)規(guī)劃策略的相關(guān)概念n動(dòng)態(tài)規(guī)劃的基本術(shù)語動(dòng)態(tài)規(guī)劃的基本術(shù)語n 狀態(tài)轉(zhuǎn)移方程：是確定過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。給定k階段狀態(tài)變量的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量也就完全確定。 n 指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)，最優(yōu)

16、指標(biāo)函數(shù)記為fk(sk)，它表示從第k段狀態(tài)sk采用最優(yōu)策略到過程終止時(shí)的最佳效益。 10.3.2動(dòng)態(tài)規(guī)劃策略的相關(guān)概念動(dòng)態(tài)規(guī)劃策略的相關(guān)概念n動(dòng)態(tài)規(guī)劃策略的算法設(shè)計(jì)步驟一般分為五步動(dòng)態(tài)規(guī)劃策略的算法設(shè)計(jì)步驟一般分為五步n 建立數(shù)學(xué)模型描述問題n 劃分階段，選擇狀態(tài)，注意階段一定要是有序的n 確定決策，并寫出狀態(tài)轉(zhuǎn)移方程n 根據(jù)指標(biāo)函數(shù)和最優(yōu)值函數(shù)，寫出遞推方程，包括邊界條件n 計(jì)算最優(yōu)值的信息。如果需要，構(gòu)造問題的最優(yōu)解10.3.3算法設(shè)計(jì)步驟及程序模式算法設(shè)計(jì)步驟及程序模式 【例10-7】使用動(dòng)態(tài)規(guī)劃策略求解圖10-6的最短路徑問題。10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例 把

17、從A到D的全過程分成3個(gè)階段，用k表示階段變量，表10-4是各階段的初始狀態(tài)和可供選擇的道路。其中，可供選擇的道路描述了狀態(tài)轉(zhuǎn)移情況。10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例表10-4 階段劃分階段k初始狀態(tài)可選擇道路k=1AAB1、AB2k=2B1B1C1、B1C2、B1C3B2B2C1、B2C2、B2C3k=3C1C1DC2C2DC3C3D 用dk(xk，xk+1)表示在第k階段由初始狀態(tài)xk到下階段的初始狀態(tài)xk+1的路徑距離。fk(xk)表示從第k階段的xk到終點(diǎn)D的最短距離。則最優(yōu)指標(biāo)函數(shù)為：10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例111()m in()(,)

18、kkkkkkkfxfxdxx10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例 【例10-8】0-1背包問題：已知有n個(gè)物品和一個(gè)背包，物品i的重量是wi，價(jià)值為vi，背包的容量為c。物品i只能放入包中，或者留在包外，不能部分和多次放入包中。問題是在選擇的物品總重量不超過c的條件下，獲得最大的價(jià)值。 把對(duì)每件物品的取舍作為一個(gè)階段，那么選擇物品的過程分成n個(gè)階段。決策變量uk表示第k個(gè)物品是否被選擇。如果物品i被選擇，uk=1，否則uk=0。如果物品1被選擇（u1=1），那么原問題變成有n-1個(gè)物品、背包容量為c-w1的背包問題。 在做出u1、u2、ui個(gè)決策后，問題簡化為只需n-i次決策、

19、背包容量為的問題。因此，無論決策變量u1、 u2、ui是多少，剩余的決策一定是簡化后的背包問題的最優(yōu)解，故0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例 如果考慮只能選擇前i個(gè)物品（）、背包容量為j（）的簡化背包問題，設(shè)m(i,j)為該簡化問題的最優(yōu)解，即能夠放進(jìn)容量為j背包中，前i個(gè)物品的最大價(jià)值子集。放進(jìn)容量為j背包中前i個(gè)物品的子集可以根據(jù)是否包括第i個(gè)物品分成兩種情況： 第一、子集中不包括第i個(gè)物品； 第二、子集中包括第i個(gè)物品。 分情況得到如下結(jié)論：n 如果子集不包括第i個(gè)物品，則最優(yōu)子集的價(jià)值為m(i-1,j)。n 如果子集中包括第i個(gè)物品，

20、則最優(yōu)子集的價(jià)值為vi+m(i-1,j-wi)，即最優(yōu)子集是由第i個(gè)物品和前i-1個(gè)能夠放進(jìn)容量為j-wi的背包最優(yōu)子集構(gòu)成。 因此，前i個(gè)物品中最優(yōu)子集的總價(jià)值等于兩種情況下子集價(jià)值中的較大者。10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例 0-1背包問題的遞歸方程背包問題的遞歸方程10.3.4動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例動(dòng)態(tài)規(guī)劃策略應(yīng)用實(shí)例000( ,)(1,)0m ax(1,),(1,)0iiiiijm ijm ijijwm ijvm ijwijw或且且 本節(jié)和下一節(jié)將介紹兩種算法設(shè)計(jì)策略：回溯策略和分支界限策略。這兩種策略都可以看作是對(duì)窮舉法的改進(jìn)，用于求解某些組合問題。 “回溯”這個(gè)術(shù)

21、語最早由D.H.Lehmer在20世紀(jì)50年代提出。R.J.Walker是回溯策略的早期研究者之一，在1960年給出了回溯算法的描述。后來，S.Golomb和L.Baumert給出回溯策略的基本描述以及各種應(yīng)用。本節(jié)主要介紹回溯策略的基本知識(shí)，并給出了回溯策略的應(yīng)用實(shí)例。10.4.1 概述概述10.4.2回溯策略算法設(shè)計(jì)步驟及程序模式回溯策略算法設(shè)計(jì)步驟及程序模式10.4.3回溯策略應(yīng)用實(shí)例回溯策略應(yīng)用實(shí)例 通過搜索問題的所有候選解以找到問題的解的方法稱為搜索法，也稱為枚舉法。當(dāng)一個(gè)問題的所有候選解數(shù)量有限，或只需要檢查部分候選解就可以找到問題的解時(shí)，搜索法是可行的。但由于實(shí)際問題候選解的數(shù)量

22、往往很大，計(jì)算機(jī)搜索候選解的時(shí)間會(huì)很長，所以，搜索法在實(shí)際應(yīng)用中很少使用。 回溯策略是一種選優(yōu)搜索法，通過對(duì)候選解進(jìn)行系統(tǒng)的搜索，使問題的求解時(shí)間大大減少，同時(shí)保證在算法運(yùn)行結(jié)束時(shí)能夠找到所需要的解。 10.4.1 概述概述n回溯法的基本思想是n 在搜索過程中，當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先的選擇不是最優(yōu)或達(dá)不到目標(biāo)，就退回到上一步重新選擇?；厮莘ㄖ饕脕斫鉀Q一些要經(jīng)過許多步驟才能完成、并且每一步都有若干種可能的分支的問題。 n若問題的解需要窮舉搜索大量、有限的可能解空間才能獲取，那么該問題被稱為組合問題?；厮莶呗郧蠼獾膯栴}一般是困難的組合問題，這些問題可能存在精確解，但是無法用高效的算法求解。另

23、外，組合問題的解空間一般可以組織成一個(gè)樹，即問題的搜索樹。如果一個(gè)問題的解空間可以用樹表示，則可以使用回溯策略求解。10.4.1 概述概述n回溯策略的算法設(shè)計(jì)步驟一般分為五步：n 建立數(shù)學(xué)模型描述問題；n 定義問題的解空間，它包含問題的所有可能解；n 把問題的解空間組織成樹結(jié)構(gòu)；n 以深度優(yōu)先的方式搜索樹結(jié)構(gòu)的解空間，并在搜索的過程中判斷是否滿足約束條件；n 輸出問題的解。如果需要，構(gòu)造問題的解。10.4.2回溯策略算法設(shè)計(jì)步驟及程序模式回溯策略算法設(shè)計(jì)步驟及程序模式n回溯策略的程序根據(jù)實(shí)現(xiàn)方法可以分成遞歸和迭代兩種。n遞歸回溯策略的程序模式如下：10.4.2回溯策略算法設(shè)計(jì)步驟及程序模式回溯

24、策略算法設(shè)計(jì)步驟及程序模式n迭代回溯策略的程序模式如下：10.4.2回溯策略算法設(shè)計(jì)步驟及程序模式回溯策略算法設(shè)計(jì)步驟及程序模式 【例10-10】使用回溯策略求解n皇后問題。已知一個(gè)的棋盤，尋找所有能夠使得n個(gè)皇后沒有沖突的方案，即不能將兩個(gè)皇后置于同一行、列或者斜線上。假設(shè)n=4時(shí)，就是一個(gè)的棋盤，每一行中有4個(gè)位置，每行只能有一個(gè)皇后，這樣就有44種布局。每種布局可以用向量表示，其中xi表示第i行放置皇后的列號(hào)。當(dāng)?shù)趇行中還沒有放置皇后，則xi=0。例如，向量對(duì)應(yīng)的布局如圖10-7所示。實(shí)際上，由于兩個(gè)皇后不能在同一列，所以任何一個(gè)沒有沖突的布局方案都對(duì)應(yīng)于1、2、3、4的一個(gè)排列。10.

25、4.3回溯策略應(yīng)用實(shí)例回溯策略應(yīng)用實(shí)例圖10-7 四皇后問題的一個(gè)布局 為了使用回溯策略解決n皇后問題，將問題的解空間組織成一棵完全n叉樹，然后以深度優(yōu)先方式搜索。根節(jié)點(diǎn)表示沒有放置皇后，因?yàn)榈谝恍谢屎笥?個(gè)位置可以放置，所以根節(jié)點(diǎn)下有四個(gè)分支，分別對(duì)應(yīng)x1=1，2，3，4，即把皇后放置在第一行的第1，2，3，4列中，如圖10-8所示。每放置完一個(gè)皇后，由于約束條件的限制，以后的搜索空間大幅縮減?；厮莶呗詴?huì)找出n皇后問題的所有可行解。10.4.3回溯策略應(yīng)用實(shí)例回溯策略應(yīng)用實(shí)例圖10-8 四皇后問題的解空間樹結(jié)構(gòu) 分支限界策略是一個(gè)用途十分廣泛的算法設(shè)計(jì)策略，由Richard Manning

26、Karp在20世紀(jì)60年代發(fā)明，成功求解含有65個(gè)城市的旅行商問題。 分支限界法被用于解決各種各樣的優(yōu)化問題。比如，作業(yè)調(diào)度問題、分配問題、網(wǎng)絡(luò)問題、背包問題、旅行商問題。本節(jié)主要介紹分支限界策略的基本知識(shí)，并給出了分支限界策略的應(yīng)用實(shí)例。10.5.1 堆堆10.5.3算法設(shè)計(jì)步驟及程序模式算法設(shè)計(jì)步驟及程序模式10.5.4分支限界策略應(yīng)用實(shí)例分支限界策略應(yīng)用實(shí)例10.5.2 概述概述 因?yàn)榉种藿绮呗越?jīng)常使用堆，所有這里先簡單回顧一下7.3.2節(jié)中堆的一些概念。 堆分為大根堆和小根堆。對(duì)于大根堆，每個(gè)結(jié)點(diǎn)的鍵值都要大于或者等于其孩子結(jié)點(diǎn)的值，而對(duì)于小根堆，每個(gè)結(jié)點(diǎn)的鍵值都小于或者等于其孩子結(jié)

27、點(diǎn)的值。10.5.1 堆堆302520181219122515263019大根堆 小根堆 在回溯策略中，若無法從解空間樹的某個(gè)分支得到解，就不會(huì)搜索這個(gè)分支。這個(gè)思想在分支限界策略中得到強(qiáng)化。分支限界法包括兩個(gè)基本操作：n分支：把全部可行的解空間不斷分割為越來越小的子集；n限界：為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界。10.5.2 概述概述 分支限界策略與回溯策略的共同點(diǎn)是需要把問題表示成解空間樹，然后在樹中搜索問題的解。 分支限界策略與回溯策略的不同點(diǎn)有兩個(gè)：分支限界策略與回溯策略的不同點(diǎn)有兩個(gè)：n第一，分支限界策略沒有限制樹的搜索方法，可以是廣度優(yōu)先搜索，也可以是最小成本搜索，而回溯策略采

28、用的是深度優(yōu)先搜索n第二，分支限界策略只能用于優(yōu)化問題，而回溯策略可以用于非優(yōu)化問題，例如求問題的可行解10.5.2 概述概述 分支限界策略在設(shè)計(jì)算法時(shí)需要兩個(gè)額外的條件分支限界策略在設(shè)計(jì)算法時(shí)需要兩個(gè)額外的條件n第一，為解空間樹中的每個(gè)結(jié)點(diǎn)提供一種計(jì)算其邊界的方法；n第二，求出目前最優(yōu)解的值。如果一個(gè)結(jié)點(diǎn)的邊界值不滿足當(dāng)前最優(yōu)解值的范圍，就停止搜索這個(gè)結(jié)點(diǎn)。 因?yàn)閺倪@個(gè)結(jié)點(diǎn)得到的解，沒有一個(gè)比目前得到的最優(yōu)解更好。分支限界策略通過限界的方法避免搜索更多的分支。 分支限界策略求解的問題也是組合優(yōu)化問題。如果一個(gè)問題的解空間可以用樹表示，并且可以求出結(jié)點(diǎn)的邊界值和目前最優(yōu)解的值，則可以使用分支限

29、界策略求解。10.5.2 概述概述 分支限界策略的算法設(shè)計(jì)步驟一般以下幾步分支限界策略的算法設(shè)計(jì)步驟一般以下幾步n建立數(shù)學(xué)模型描述問題；n定義問題的解空間，它包含問題的所有可能解；n把問題的解空間組織成樹結(jié)構(gòu)；n以廣度優(yōu)先或最小成本的方式搜索樹結(jié)構(gòu)的解空間，并在搜索的過程中計(jì)算當(dāng)前最優(yōu)解的值和每個(gè)分支出來的結(jié)點(diǎn)的邊界值；n輸出問題的解。如果需要，構(gòu)造問題的解。10.5.3算法設(shè)計(jì)步驟及程序模式算法設(shè)計(jì)步驟及程序模式 【例10-12】使用分支限界策略求解任務(wù)分配問題。任務(wù)分配問題是把n項(xiàng)任務(wù)分配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的所需要的時(shí)間不同，一般用n階矩陣表示。要求分配給每個(gè)人一項(xiàng)任務(wù)，使完成n

30、項(xiàng)任務(wù)的總時(shí)間最少。把不同的任務(wù)分配給不同的人，就出現(xiàn)了很多不同的組合，求完成所有任務(wù)總時(shí)間最少的任務(wù)分配，這是一個(gè)組合優(yōu)化問題。 10.5.4分支限界策略應(yīng)用實(shí)例分支限界策略應(yīng)用實(shí)例 如何構(gòu)造任務(wù)分配問題的解空間樹？方法是把樹中的每一層對(duì)應(yīng)著一項(xiàng)任務(wù)的分配，該層的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一項(xiàng)任務(wù)被分配給不同的人員，如圖10-12所示 例如，圖10-12中的矩陣C是四位人員完成四項(xiàng)任務(wù)所用的時(shí)間表，當(dāng)任務(wù)都沒有分配時(shí)，四項(xiàng)任務(wù)的總完成時(shí)間不會(huì)小于矩陣C每一列中最小元素的和，即5+2+1+4=12。 10.5.4分支限界策略應(yīng)用實(shí)例分支限界策略應(yīng)用實(shí)例9278643758187694abC任 務(wù) 一任 務(wù) 二任 務(wù) 三任 務(wù) 四人 員人 員人 員 c人