華南理工大學(xué)廣州學(xué)院算法設(shè)計(jì)與分析期末考試復(fù)習(xí)

復(fù)習(xí)考試題型：選擇題（算法類型、時(shí)間復(fù)雜度，共15題，30分）簡(jiǎn)答題（設(shè)計(jì)思想，共2題，12分）應(yīng)用題（解題步驟、搜索空間樹等，共4題，48分）編程題（上機(jī)實(shí)驗(yàn)題，作業(yè)題等，共1題，10分）復(fù)習(xí)2023/9/1復(fù)習(xí)Page32023/9/1Page3算法的幾種描述方法（重點(diǎn)掌握偽代碼和C++語言，會(huì)使用偽代碼寫算法）；理解大O符號(hào)的含義；算法的幾個(gè)重要特性：輸入、輸出、有窮性、確定性、可行性。第一章、第二章⑴自然語言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想

注意事項(xiàng)：避免寫成自然段算法的幾種描述方法（重點(diǎn)掌握偽代碼和C++語言，會(huì)使用偽代碼寫算法）；⑵流程圖

優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次⑶程序設(shè)計(jì)語言優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：盡量將算法寫成子函數(shù)⑷偽代碼——算法語言偽代碼（Pseudocode）：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解理解大O符號(hào)的含義；時(shí)間復(fù)雜度算法的五大特性：2023/9/1第1章算法設(shè)計(jì)基礎(chǔ)Page9輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。算法的有窮性意味著不是所有的計(jì)算機(jī)程序都是算法.確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出。可行性：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)（每步可執(zhí)行）。2023/9/1復(fù)習(xí)Page102023/9/1Page10蠻力法的基本思想（重要?。?蠻力法依賴的基本技術(shù)——掃描技術(shù)，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解;關(guān)鍵——依次處理所有元素。第三章蠻力法2023/9/1復(fù)習(xí)Page112023/9/1Page11熟記哪些問題使用了蠻力法進(jìn)行解決：順序查找、串匹配（KMP,BM,BF），選擇排序，冒泡排序，生成排列對(duì)象，生成子集，0/1背包，任務(wù)分配，哈密頓回路，TSP，最近對(duì)問題，凸包問題，7-11問題，百錢買百雞問題；并熟記這些問題的時(shí)間復(fù)雜度；第三章蠻力法2023/9/1復(fù)習(xí)Page122023/9/1Page12其中：BF：依次掃描，對(duì)比，O(n+m)；KMP：依次掃描，對(duì)比（雖然這個(gè)“依次”已經(jīng)是按照一定的規(guī)律，效率較高），O(n+m)，注意：對(duì)于KMP算法，必須求出next數(shù)組；選擇排序：掃描整個(gè)序列，找到整個(gè)序列的最小記錄和序列中的第一個(gè)記錄交換位置，再掃第二小，依此類推…，O(n2)；第三章蠻力法2023/9/1復(fù)習(xí)Page132023/9/1Page13其中：冒泡排序：掃描整個(gè)序列，在掃描過程中兩兩比較相鄰記錄，如果反序則交換，直到n-1趟掃描后，即排好序，O(n2)

；TSP：把所有可能的回路都找出來，就可以得到最短路徑，O(n!)；7-11：把所有可能都計(jì)算一遍，就能得到正確的解；百錢買百雞：把所有可能都計(jì)算一遍，就能得到正確的解。第三章蠻力法2023/9/1復(fù)習(xí)Page142023/9/1Page14冒泡排序、選擇排序、TSP問題的設(shè)計(jì)思想和偽代碼（可能出簡(jiǎn)答題）7-11問題、百錢買百雞問題的代碼實(shí)現(xiàn)（猜測(cè)是編程題）第三章蠻力法冒泡排序設(shè)計(jì)思想選擇排序設(shè)計(jì)思想TSP問題設(shè)計(jì)思想

TSP問題：旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長(zhǎng)度最短的簡(jiǎn)單回路。8abdc23571序號(hào)路徑路徑長(zhǎng)度是否最短1a→b→c→d→a18

否2a→b→d→c→a11

是3a→c→b→d→a23

否4a→c→d→b→a11

是5a→d→b→c→a23

否6a→d→c→b→a18

否

注意到，在圖中有3對(duì)不同的路徑，對(duì)每對(duì)路徑來說，不同的只是路徑的方向，因此，可以將這個(gè)數(shù)量減半，則可能的解有(n-1)!/2個(gè)。這是一個(gè)非常大的數(shù)，隨著n的增長(zhǎng)，TSP問題的可能解也在迅速地增長(zhǎng)。用蠻力法求解TSP問題，其時(shí)間復(fù)雜性為O(n!)，只能解決問題規(guī)模很小的實(shí)例。一個(gè)簡(jiǎn)單的例子——百元買百雞問題已知公雞5元一只，母雞3元一只，小雞1元三只，用100元錢買100只雞，問公雞、母雞、小雞各多少只？voidchicken(){intx,y,z;for(x=0;x<=20;x++){for(y=0;y<=33;y++){z=100-x-y; if((z%3==0)&&(5*x+3*y+z/3==100)){cout<<"公雞:"<<x<<"母雞:"<<y<<"小雞:"<<z<<endl;}}}}（編程，代碼要記牢）7-11問題（編程，代碼要記牢）設(shè)計(jì)蠻力算法找出四件物品的價(jià)格各是什么？

#include<iostream.h>voidmain(){ inta,b,c,d; for(a=1;a<=711;a++){ for(b=1;b<=711;b++){ for(c=1;c<=711;c++){ d=711-a-b-c; if(a*b*c*d==711){ cout<<a/100.0<<'\t'<<b/100.0<<'\t'<<c/100.0<<'\t'<<d/100.0<<endl; return; } } } }2023/9/1復(fù)習(xí)Page222023/9/1Page22分治法的基本思想（重要！自底向上，理解+應(yīng)用）：將要求解的原問題劃分成k個(gè)較小規(guī)模的子問題，對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再將每個(gè)子問題劃分為k個(gè)規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小，很容易求出其解為止，再將子問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原問題的解。步驟：（1）劃分

（2）求解子問題

（3）合并第四章分治法2023/9/1復(fù)習(xí)Page232023/9/1Page23分治法的基本思想（自底向上，理解+應(yīng)用）：第四章分治法

子問題1的規(guī)模是n/2

子問題1的解

子問題2的解

子問題2的規(guī)模是n/2

原問題的解

原問題的規(guī)模是n2023/9/1復(fù)習(xí)Page242023/9/1Page24熟記哪些問題使用了分治法進(jìn)行解決：歸并排序，快速排序，最大子段和，棋盤覆蓋，循環(huán)賽日程安排，最近對(duì)問題，凸包問題；并熟記這些問題的時(shí)間復(fù)雜度：第四章分治法2023/9/1復(fù)習(xí)Page252023/9/1Page25其中：歸并排序：劃分成等長(zhǎng)子序列

分別對(duì)兩子序列歸并排序

將排完的有序子序列合并成一個(gè)有序序列，O(nlog2n)；快速排序：用一個(gè)軸值劃分成兩個(gè)子序列

分別對(duì)兩個(gè)子序列遞歸地快速排序，O(nlog2n)；最大子段和：劃分成等長(zhǎng)子序列

針對(duì)3種情況分別處理求子序列最大子段和

合并3種情況下的最大子段和，O(nlog2n)。第四章分治法2023/9/1復(fù)習(xí)Page262023/9/1Page26歸并排序、快速排序、最大子段和問題的設(shè)計(jì)思想和偽代碼；（可能出簡(jiǎn)答題）用快速排序和歸并排序算法對(duì)數(shù)字序列排序。第四章分治法歸并排序設(shè)計(jì)思想

二路歸并排序的分治策略是：（1）劃分：將待排序序列r1,r2,…,rn劃分為兩個(gè)長(zhǎng)度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子問題：分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子序列；（3）合并：將這兩個(gè)有序子序列合并成一個(gè)有序序列。二路歸并排序在合并過程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此其空間復(fù)雜性為O(n)。

r1……rn/2

rn/2＋1……rn

劃分r‘1<……<r’n/2r’n/2＋1<……<r’n

遞歸處理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

r1……rn/2

rn/2＋1……rn

劃分r‘1<……<r’n/2r’n/2＋1<……<r’n

遞歸處理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

快速排序設(shè)計(jì)思想以第一個(gè)記錄作為軸值，對(duì)待排序序列進(jìn)行劃分的過程為：（1）初始化：取第一個(gè)記錄作為基準(zhǔn)，設(shè)置兩個(gè)參數(shù)i，j分別用來指示將要與基準(zhǔn)記錄進(jìn)行比較的左側(cè)記錄位置和右側(cè)記錄位置，也就是本次劃分的區(qū)間；（2）右側(cè)掃描過程：將基準(zhǔn)記錄與j指向的記錄進(jìn)行比較，如果j指向記錄的關(guān)鍵碼大，則j前移一個(gè)記錄位置。重復(fù)右側(cè)掃描過程，直到右側(cè)的記錄小（即反序），若i＜j，則將基準(zhǔn)記錄與j指向的記錄進(jìn)行交換；（3）左側(cè)掃描過程：將基準(zhǔn)記錄與i指向的記錄進(jìn)行比較，如果i指向記錄的關(guān)鍵碼小，則i后移一個(gè)記錄位置。重復(fù)左側(cè)掃描過程，直到左側(cè)的記錄大（即反序），若i＜j，則將基準(zhǔn)記錄與i指向的記錄交換；（4）重復(fù)（2）（3）步，直到i與j指向同一位置，即基準(zhǔn)記錄最終的位置。最大子段和問題設(shè)計(jì)思想復(fù)習(xí)減治法的基本思想（理解+應(yīng)用）：原問題的解只存在于其中一個(gè)較小規(guī)模的子問題中，所以，只需求解其中一個(gè)較小規(guī)模的子問題就可以得到原問題的解。熟記哪些問題使用了減治法進(jìn)行解決：折半查找，二叉樹查找，插入排序，堆排序，選擇問題，淘汰賽冠軍問題，假幣問題（8枚硬幣不知道假幣輕重）；并熟記這些問題的時(shí)間復(fù)雜度：第五章減治法2023/9/1復(fù)習(xí)Page332023/9/1Page33其中：折半查找：在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找，O(log2n)。插入排序：依次將待排序序列中的每一個(gè)記錄插入到一個(gè)已排好序的序列中，直到全部記錄都排好序，O(n2)第五章減治法2023/9/1復(fù)習(xí)Page342023/9/1Page34其中：選擇問題：考慮快速排序中的劃分過程，選定一個(gè)軸值將序列ri

～rj進(jìn)行劃分，使得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位于軸值的右側(cè)，假定軸值的最終位置是s，則：（1）若k=s，則rs就是第k小元素；（2）若k<s，則第k小元素一定在軸值前半?yún)^(qū)中；（3）若k>s，則第k小元素一定在軸值后半?yún)^(qū)中；第五章減治法2023/9/1復(fù)習(xí)Page352023/9/1Page35其中：假幣問題（8枚硬幣不知道假幣輕重）：從八枚硬幣中任取六枚a，b，c，d，e，f，在天平兩端各放三枚進(jìn)行比較。假設(shè)a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出現(xiàn)三種比較結(jié)果（再根據(jù)三種比較結(jié)果進(jìn)行分析）⑴a＋b＋c>d＋e＋f⑵a＋b＋c＝d＋e＋f⑶a＋b＋c<d＋e＋f第五章減治法2023/9/1復(fù)習(xí)Page362023/9/1Page36折半查找問題的設(shè)計(jì)思想和偽代碼（可能出簡(jiǎn)答題）給一個(gè)數(shù)字序列，要求采用折半查找，找某個(gè)數(shù)，寫出求解的過程。第五章減治法折半查找問題設(shè)計(jì)思想在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。

[r1………rmid-1]rmid[rmid+1………rn]（mid=(1+n)/2）如果k<rmid查找這里如果k>rmid查找這里

k2023/9/1第5章減治法Page38例：查找值為14的記錄的過程：

0123456789101112137141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14查找成功！選擇下列數(shù)字序列中的第3小的元素12,5,8,44,23,7,9,22023/9/1復(fù)習(xí)Page402023/9/1Page40動(dòng)態(tài)規(guī)劃法的基本思想（重要！自底向上，理解+應(yīng)用）：將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對(duì)應(yīng)決策過程的一個(gè)階段，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解。第六章動(dòng)態(tài)規(guī)劃法2023/9/1復(fù)習(xí)Page412023/9/1Page41動(dòng)態(tài)規(guī)劃法的求解過程：分成相互重疊的子問題；求解子問題，填表；自底向上計(jì)算出原問題的解。第六章動(dòng)態(tài)規(guī)劃法2023/9/1復(fù)習(xí)Page422023/9/1Page42熟記哪些問題使用了動(dòng)態(tài)規(guī)劃法進(jìn)行解決：TSP，多段圖的最短路徑問題，0/1背包，最長(zhǎng)公共子序列問題，最優(yōu)二叉查找樹，近似串匹配問題；并熟記這些問題的時(shí)間復(fù)雜度：多段圖的最短路徑問題：O(n+m)0/1背包問題：O(n×C)第六章動(dòng)態(tài)規(guī)劃法2023/9/1第6章動(dòng)態(tài)規(guī)劃法Page432120345678949387684756866537

一個(gè)多段圖用動(dòng)態(tài)規(guī)劃法解決多段圖的最短路徑問題，寫出求解過程（可能出應(yīng)用題）第六章動(dòng)態(tài)規(guī)劃法2023/9/1第6章動(dòng)態(tài)規(guī)劃法Page45

根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)×(C+1)的二維表V，V[i][j]表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。

實(shí)例：有5個(gè)物品，其重量分別是{2,2,6,5,4}，價(jià)值分別為{6,3,5,4,6}，背包的容量為10。

012345678910

0w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=65000000000000000006666666660669999999066999911111406699910111314066991212151515x5=1x4=0x3=0x2=1x1=1用動(dòng)態(tài)規(guī)劃法解決0/1背包問題，寫出求解過程。（可能出應(yīng)用題）物品容量2023/9/1復(fù)習(xí)Page462023/9/1Page46貪心法的基本思想（重要！局部最優(yōu)，理解+應(yīng)用）：貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個(gè)選擇都不會(huì)改變。第七章貪心法2023/9/1復(fù)習(xí)Page472023/9/1Page47熟記哪些問題使用了貪心法進(jìn)行解決：TSP，圖著色問題，最小生成樹問題（Prim算法、Kruskal算法），背包問題，活動(dòng)安排問題，多機(jī)調(diào)度問題，哈弗曼編碼；并熟記這些問題的時(shí)間復(fù)雜度：第七章貪心法2023/9/1復(fù)習(xí)Page482023/9/1Page48其中：背包問題：每次從物品集合中選擇單位重量?jī)r(jià)值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，O(nlog2n)。注意：背包問題要求裝滿整個(gè)背包，最后一個(gè)物體若裝不下一個(gè)整體，可以裝其中的一部分。第七章貪心法2023/9/1復(fù)習(xí)Page492023/9/1Page49背包問題的貪心算法設(shè)計(jì)思想和偽代碼；給定n種物品和一個(gè)容量為C的背包，物品i的重量是wi，其價(jià)值為vi，背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?4.用貪心法解決背包問題，寫出求解過程（第7章作業(yè)：先按單位價(jià)值重量比排序，再依次放置物品，最后求出總價(jià)值，寫出）（可能出應(yīng)用題）第七章貪心法背包問題（可能出簡(jiǎn)答題）設(shè)計(jì)思想有三種看似合理的貪心策略：（1）選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快地增加背包的總價(jià)值。但是，雖然每一步選擇獲得了背包價(jià)值的極大增長(zhǎng)，但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（2）選擇重量最輕的物品，因?yàn)檫@可以裝入盡可能多的物品，從而增加背包的總價(jià)值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價(jià)值卻沒能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（3）選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值增長(zhǎng)和背包容量消耗兩者之間尋找平衡。2023/9/1第7章貪心法Page51

12050背包180190200(a)三個(gè)物品及背包(b)貪心策略1(c)貪心策略2(d)貪心策略350301020203020/30201010/203010例如，有3個(gè)物品，其重量分別是{20,30,10}，價(jià)值分別為{60,120,50}，背包的容量為50，應(yīng)用三種貪心策略裝入背包的物品和獲得的價(jià)值如圖所示。2023/9/1復(fù)習(xí)Page532023/9/1Page53回溯法的基本思想（深度優(yōu)先搜索，理解+應(yīng)用）：從根結(jié)點(diǎn)出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，在搜索至樹中任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)對(duì)應(yīng)的部分解是否滿足約束條件，或者是否超出目標(biāo)函數(shù)的界，也就是判斷該結(jié)點(diǎn)是否包含問題的（最優(yōu)）解，如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的搜索，即所謂剪枝（Pruning）；否則，進(jìn)入以該結(jié)點(diǎn)為根的子樹，繼續(xù)按照深度優(yōu)先策略搜索。第八章回溯法2023/9/1復(fù)習(xí)Page542023/9/1Page54熟記哪些問題使用了回溯法進(jìn)行解決：圖m著色問題，哈密頓回路問題，八皇后問題（4皇后問題），批處理作業(yè)調(diào)度問題；第八章回溯法3.用回溯法解決m顏色圖著色問題，畫出搜索空間圖；

（可能出應(yīng)用題）

圖的m著色問題描述為：給定無向連通圖G=(V,E)和正整數(shù)m，判斷能否用m種顏色對(duì)G中的頂點(diǎn)著色，使得任意兩個(gè)相鄰頂點(diǎn)著色不同。

D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a)一個(gè)無向圖(b)回溯法搜索空間圖8.8回溯法求解圖著色問題示例4.畫出用回溯法求解8皇后或4皇后問題的搜索過程（課本P161）

（可能出應(yīng)用題）

八皇后問題是十九世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。問題是：在8×8的棋盤上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。可以把八皇后問題擴(kuò)展到n皇后問題，即在n×n的棋盤上擺放n個(gè)皇后，使任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。回溯法求解4皇后問題的搜索過程2023/9/1復(fù)習(xí)Page572023/9/1Page57分支限界法的基本思想：首先確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]；按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點(diǎn)上，依次搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值；如果某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)可能取得的值超出目標(biāo)函數(shù)的界，則將其丟棄；否則，將其加入待處理結(jié)點(diǎn)表（以下簡(jiǎn)稱表PT）中；依次從表PT中選取使目標(biāo)函數(shù)的值取得極值的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)；重復(fù)上述過程，直到找到最優(yōu)解。第九章分支限界法2023/9/1復(fù)習(xí)Page582023/9/1Page58分支限界法的基本思想：

⑥當(dāng)搜索到一個(gè)葉子結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)的目標(biāo)函數(shù)值是表PT中的極值（對(duì)于最小化問題，是極小值；對(duì)于最大化問題，是極大值），則該葉子結(jié)點(diǎn)對(duì)應(yīng)的解就是問題的最優(yōu)解；

⑦否則，根據(jù)這個(gè)葉子結(jié)點(diǎn)調(diào)整目標(biāo)函數(shù)的界（對(duì)于最小化問題，調(diào)整上界；對(duì)于最大化問題，調(diào)整下界），依次考察表PT中的結(jié)點(diǎn)，將超出目標(biāo)函數(shù)界的結(jié)點(diǎn)丟棄，然后從表PT中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展。第九章分支限界法2023/9/1復(fù)習(xí)Page592023/9/1Page59熟記哪些問題使用了分支限界法進(jìn)行解決：TSP，多段圖的最短路徑問題，任務(wù)分配問題，批處理作業(yè)調(diào)度問題，0/1背包；并熟記這些問題的時(shí)間復(fù)雜度；用分支限界法解決任務(wù)分配問題，畫出搜索空間。（可能出應(yīng)用題）用分支限界法解決0/1背包問題，畫出搜索空間。（可能出應(yīng)用題）第九章分支限界法2023/9/1第9章分支限界法Page60任務(wù)分配問題要求把n項(xiàng)任務(wù)分配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖9.10所示是一個(gè)任務(wù)分配的成本矩陣。

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d圖9.10任務(wù)分配問題的成本矩陣任務(wù)分配問題（可能出應(yīng)用題）

2023/9/1第9章分支限界法Page61求最優(yōu)分配成本的上界和下界考慮任意一個(gè)可行解，例如：矩陣中的對(duì)角線是一個(gè)合法的選擇，表示將任務(wù)1分配給人員a、任務(wù)2分配給人員b、任務(wù)3分配給人員c、任務(wù)4分配給人員d，其成本是9+4+1+4=18；或者應(yīng)用貪心法求得一個(gè)近似解：將任務(wù)2分配給人員a、任務(wù)3分配給人員b、任務(wù)1分配給人員c、任務(wù)4分配給人員d，其成本是2+3+5+4=14。顯然，14是一個(gè)更好的上界。為了獲得下界，考慮人員a執(zhí)行所有任務(wù)的最小代價(jià)是2，人員b執(zhí)行所有任務(wù)的最小代價(jià)是3，人員c執(zhí)行所有任務(wù)的最小代價(jià)是1，人員d執(zhí)行所有任務(wù)的最小代價(jià)是4。因此，將每一行的最小元素加起來就得到解的下界，其成本是2+3+1+4=10。需要強(qiáng)調(diào)的是，這個(gè)解并不是一個(gè)合法的選擇（3和1來自于矩陣的同一列），它僅僅給出了一個(gè)參考下界，這樣，最優(yōu)值一定是[10,14]之間的某個(gè)值。2023/9/1第9章分支限界法Page62圖9.11分支限界法求解任務(wù)分配問題示例(×表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=203→clb=134→dlb=1323567891213111××××搜索空間分支限界法求解0/1背包問題（可能出應(yīng)用題）

例：0/1背包問題。假設(shè)有4個(gè)物品，其重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量?jī)r(jià)值從大到小排序，結(jié)果如下：物品重量(w)價(jià)值(v)價(jià)值/重量(v/w)1440102742635255431242023/9/1第9章分支限界法Page64

應(yīng)