數(shù)學(xué)建模常用技巧第一頁，共三十頁，2022年，8月28日常用技巧計算復(fù)雜性分析算法設(shè)計

精確算法近似算法算法計算量估計、算法優(yōu)劣比較第二頁，共三十頁，2022年，8月28日比較算法的好壞，從不同的角度出發(fā)，有各種不同的標(biāo)準(zhǔn)。在這里，我們僅就算法的計算速度作一個十分粗略的比較。

例1

（整理問題）給定n個實數(shù)a1,a2,…,an，要求將它整理成由小到大排列（或由大到小排列）的順序：b1,b2,…,bn，b1≤b2≤…≤bn。（算法1）取出a1,a2,…,an中的最小者，令其為b1。從a1,a2,…,an中去除b1，在余下的n—1個數(shù)中選出最小者，令其為b2，…，直至得到b1,b2,…,bn。容易看出，為了排出b1,b2,…,bn，算進(jìn)行了n(n-1)/2次比較。（算法2）步0b1←a1

步1設(shè)已有b1,…,bk(1≤k<n)，將按兩分法比較的方式把a(bǔ)k+1排入其中：若b1≤…≤bi≤ak+1≤bi+1≤…≤bk，令（b1,b2,…,bk,bk+1）←（b1,…,bi,ak+1,bi+1,…,bk）。若k+1<n，令k←k+1，返回步1。計算復(fù)雜性第三頁，共三十頁，2022年，8月28日我們來分析一下算法2的計算量：排出b1不必作比較，排出b2只需作一次比較，…，一般，在排ak+1時，設(shè)2r－1≤k＜2r，則只需作r次比較即可將ak+1安排在它應(yīng)排的位置上。例如在排a8時，k=7，先和b4比，若a8>b4，可再和b6比（若a8<b4則和b2比），易見，只要比3次即可排入a8，由于r≤log2k+1，算法的比較次數(shù)不超過令，，設(shè)計算機(jī)每秒可作C次比較，則算法1與算法2整理a1,a2,…,an所用的時間分別為

若n=100萬，C=100萬次/秒，則t1≈5.8天，而t2≈20秒?？梢娫谳^大規(guī)模的整理問題時，算法2明顯優(yōu)于算法1。

第四頁，共三十頁，2022年，8月28日現(xiàn)設(shè)一臺每小時能作M次運算的計算機(jī)，并設(shè)求解某一問題已有了兩個不同的算法。算法A對規(guī)模為n的實例約需作n2次運算而算法B則約需作2n次運算。于是，運用算法A在一小時內(nèi)可解一個規(guī)模為的實例，而算法B則只能解一個規(guī)模為log2M的實例。兩者的差別究竟有多大呢？讓我們來對比一下。假如計算機(jī)每秒可作100萬次運算，則算法A一小時大約可解一個規(guī)模為n=60000的實例，而算法B在一小時內(nèi)只能解一個規(guī)模的實例且n每增加1，算法B求解時所化的時間就將增加1倍。例如算法B求解一個n=50的實例將連續(xù)運算357年多。現(xiàn)設(shè)計算速度提高了100倍，這對計算機(jī)來講已是一個相當(dāng)大的改進(jìn)。此時算法A可解問題的規(guī)模增大了10倍，而算法B可解問題的規(guī)模只增加了log2100<7。前者可解問題的規(guī)模成倍成倍地增加而后者則幾乎沒有什么改變，今天無法求解的問題將來也很少有希望解決。

由于這一原因，人們對算法作了如下的分類：第五頁，共三十頁，2022年，8月28日（多項式算法）設(shè)A是求解某一問題D的一個算法，對D的一個規(guī)模為n的實例，用fA(D,n)表示用算法A求解這一實例所作的初等運算的次數(shù)。若存在一個多項式P(n)和一個正整數(shù)N，當(dāng)n≥N時總有fA(D,n)≤P(n)（不論求解D的怎樣的實例，只要其規(guī)模為n），則稱算法A為求解問題D的一個多項式時間算法，簡稱多項式算法。（指數(shù)算法）設(shè)B是求解某一問題D的一個算法，fB(D,n)為用算法B求解D的一個規(guī)模為n的實例時所用的初等運算次數(shù)，若存在一個常數(shù)k>0，對任意正整數(shù)N，總可找到一個大于N的正整數(shù)n及D的一個規(guī)模為n的實例，對這一實例有fB(D,n)=O(2^kn)，則稱B為求解問題D的一個指數(shù)算法。多項式算法被稱為是“好”的算法即所謂有效算法，而指數(shù)算法則一般被認(rèn)為是“壞”算法，因為它只能求解規(guī)模極小的實例。第六頁，共三十頁，2022年，8月28日下面的表1列出了在規(guī)模大約為n時各類算法的計算量，而表2則反映了當(dāng)計算機(jī)速度提高10倍、100倍時，各類算法在1小時內(nèi)可求解的問題的模型的增長情況，（前三個是多項式時間的，后兩個是指數(shù)時間的）表1幾個多項式和指數(shù)時間復(fù)雜性函數(shù)增長情況算法要求的計算量規(guī)模n的近似值101001000n101001000nlogn336649966n31031061092n10241.27×10301.05×10301n!3628800101584×102567第七頁，共三十頁，2022年，8月28日表21小時內(nèi)可解的問題實例的規(guī)模算法要求的計算量用現(xiàn)在計算機(jī)用快10倍計算機(jī)用快100倍計算機(jī)nN110N1100N1nlognN28.2N267N2n3N32.15N34.64N32nN4N4+3.32N4+6.64n!N5≤N5+2≤N5+3由上可知4n2與2n2都是O(n2)，nlogn+3n是O(nlogn)，我們在以后分析時間復(fù)雜性函數(shù)時也往往忽略常系數(shù)和增長速度較慢的項，因為前者可通過提高計算機(jī)速度來提高效率，而后者增長速度最快的項才是決定效率的關(guān)鍵因素。下面介紹六個最初的NP難問題第八頁，共三十頁，2022年，8月28日（1）（3—滿足問題，簡記3—SAT問題）每一個句子都是一個三項式的SAT問題，稱為3—SAT問題。例如，就是3—SAT的一個實例。命題邏輯中合取范式(CNF)的可滿足性問題(SAT)是當(dāng)代理論計算機(jī)科學(xué)的核心問題,是一典型的NP完全問題.考慮CNF：A=C1∧?∧Ci∧?∧Cn(1)子句Ci具有如下形式：Pi,1∨Pi,2∨?∨Pi,ki∨┐Pri,1∨┐Pri,2∨?∨┐Pri,kri,其中Pi,1,Pi,2,?,Pi,ki,┐Pri,1,┐Pri,2,?,┐Pri,kri是兩兩不同的文字,Pi,j為命題變元集{P1,P2,?,Pm}中的一個變元,文字┐Pi表示變元Pi的非,m表示命題變元的個數(shù),n表示子句的個.一個SAT問題是指:對于給定的CNF是否存在一組關(guān)于命題變元的真值指派使得A為真.下面介紹六個最初的NP難問題第九頁，共三十頁，2022年，8月28日（1）（3—滿足問題，簡記3—SAT問題）每一個句子都是一個三項式的SAT問題，稱為3—SAT問題。例如，就是3—SAT的一個實例。下面介紹六個最初的NP難問題如果A為真,則CNF的每個子句中必有一個命題變元為1(真),將每個子句中的每個命題變元取反,則CNF的每個子句中必有一個命題變元為0(假),然后將∧看成加,將∨看成乘,將變元Pi看成實參數(shù)xi,則SAT問題就可以轉(zhuǎn)換為一個求相應(yīng)實函數(shù)最小值的優(yōu)化問題.令T表示這種轉(zhuǎn)換,它可遞歸地定義為T:A→Rm→R,T(C1∧?∧Ci∧?∧Cn)=T(C1)+?+T(Ci)+?+T(Cn),T(Ci)=T(Pi,1∨Pi,2∨?∨Pi,ki∨

┐Pri,1∨┐Pri,2∨?∨┐Pri,kri)

=T(Pi,1)T(Pi,2)?T(Pi,ki)T(┐Pri,1)T(┐Pri,2)?T(┐Pri,kri),i=1,?,n.T(Pi)=1-xi,T(┐Pi)=xi,xi∈[0,1],i=1,?,m,

T(T)=1,T(F)=0.

第十頁，共三十頁，2022年，8月28日（1）（3—滿足問題，簡記3—SAT問題）每一個句子都是一個三項式的SAT問題，稱為3—SAT問題。例如，就是3—SAT的一個實例。下面介紹六個最初的NP難問題例如,

T((P1∨┐P2)∧(┐P1∨┐P2))=T(P1∨┐P2)+

T(┐P1∨┐P2)=T(P1)T(┐P2)+T(┐P1)T(┐Pv2)=(1-x1)x2+x1x2,用E(x1,x2,?,xm)表示T(A)在點(v(P1),?,v(Pm))的值,則有下面定理.定理1.賦值v為使A可滿足的充要條件是E(x1,x2,?,xm)達(dá)到最小值0.

于是一個SAT問題可以轉(zhuǎn)化為優(yōu)化模型求解:minE(x1,x2,?,xm)ST:xi=0,或1第十一頁，共三十頁，2022年，8月28日2）（三維匹配問題——3DM）X、Y、Z是三個不相交的集合，|X|=|Y|=|Z|=q，。問：M中是否包含一個匹配M，使得（等價問題是求最大三維匹配）。注：這里給出的是標(biāo)準(zhǔn)形式，一般可不必要求|X|=|Y|=|Z|，表示笛卡爾乘積。三維匹配問題是二維匹配（2DM）問題的推廣，2DM是P問題而3DM是NP完全的。一個匹配是指M的一個子集合{(xi,yi,zi)}，xi∈X，yi∈Y，zi∈Z，且當(dāng)下標(biāo)不同時，它們分別取三個集合中的不同元素。3DM可作如下形象的解釋：記一單身男人集合為X，一單身女人集合為Y，此外還有一個住房集合Z。其間存在一相容關(guān)系（例如有些人之間不愿組成家庭，或不愿住某一住房），這樣就給出了一個集合，M是由問題給出的，表示了所有可能組合。所求的匹配即組成的一組家庭（包括住房），其中不能有重婚，也不能讓不同的兩個家庭住進(jìn)同一住房。下面介紹六個最初的NP難問題第十二頁，共三十頁，2022年，8月28日（3）（劃分問題）給定一正整集合A={a1,a2,…,an}，問是否存在A的一個子集A’,使得，即是否可將A中的數(shù)分成總和相等的兩部分。（4）（頂點復(fù)蓋問題——VC）給定一個圖G=（V，E）及一個正整數(shù)K≤|V|，問G中是否有不超過K個頂點的復(fù)蓋。（一個頂點的子集稱為G的一個復(fù)蓋，若它至少包含G中任一邊的兩個端點之一）。下面介紹六個最初的NP難問題找出所有滿足xi=0或1，f=∑ai*xi=（∑A）/2的解練習(xí)：用MATLAB或LINGO實現(xiàn)劃分問題（5）（團(tuán)問題,控制集問題）給定圖G=（V，E）及一正整數(shù)K≤|V|，問是否存在圖G中的一個團(tuán)V’，|V’|≥K。（G的一個頂點的子集V’稱為G的一個團(tuán)，若V’中任意兩點間都有E中的邊相連）。

第十三頁，共三十頁，2022年，8月28日問題4,5的應(yīng)用之一:系統(tǒng)監(jiān)控模型設(shè)圖G=(V,E),KV如果圖G的每條邊都至少有一個頂點在K中,則稱K是G的一個點覆蓋.

若G的一個點覆蓋中任意去掉一個點后不再是點覆蓋,則稱此點覆蓋是G的一個極小點覆蓋.

頂點數(shù)最少的點覆蓋,稱為G的最小點覆蓋.例如,右圖中,{v0,v2,v3,v5,v6}等都是極小點覆蓋.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小點覆蓋.第十四頁，共三十頁，2022年，8月28日最大獨立點集

定義2設(shè)圖G=(V,E),IV如果I中任意兩個頂點在G中都不相鄰,則稱I是G的一個獨立點集.

若G的一個獨立點集中,任意添加一個點后不再是獨立點集,則稱此獨立點集是G的一個極大獨立點集.

頂點數(shù)最多的獨立點集,稱為G的最大獨立點集.例如,右圖中,{v1,v4}等都是極大獨立點集.{v1,v3,v5},{v2,v2,v6}是最大獨立點集.第十五頁，共三十頁，2022年，8月28日最小控制集

定義3設(shè)圖G=(V,E),DV如果v∈V,要么v∈D,要么v與D的某個點相鄰,則稱D是G的一個控制集.

若G的一個控制集中任意去掉一個點后不再是控制集,則稱此控制集是G的一個極小控制集.

頂點數(shù)最少的控制集,稱為G的最小控制集.例如,右圖中,{v1,v3,v5}是極小控制集,{v0}是最小控制集.第十六頁，共三十頁，2022年，8月28日系統(tǒng)監(jiān)控問題之二

假設(shè)下圖代表一指揮系統(tǒng),頂點v1,v2,…,v7表示被指揮的單位,邊表示可以直接下達(dá)命令的通信線路.欲在某些單位建立指揮站,以便可以通過指揮站直接給各單位下達(dá)命令,問至少需要建立幾個指揮站?

這就是要求最小控制集問題.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以至少需要在2個單位建立指揮站.

到目前為止,還沒有找到求最小控制集的有效算法.一種啟發(fā)式近似算法.第十七頁，共三十頁，2022年，8月28日最小點覆蓋、最大獨立點集和最小控制集的關(guān)系

定理1設(shè)無向圖G=(V,E)中無孤立點(不與任何邊關(guān)聯(lián)的點),若D是G中極大獨立點集,則D是G中極小控制集.

定理2設(shè)無向圖G=(V,E)中無孤立點,KV,則K是G的點覆蓋當(dāng)且僅當(dāng)Kc=V\K是G的獨立點集.

推論設(shè)無向圖G=(V,E)中無孤立點,KV,則K是G的最小(極小)點覆蓋當(dāng)且僅當(dāng)Kc=V\K是G的最大(極大)獨立點集.第十八頁，共三十頁，2022年，8月28日若圖G中的一個頂點和一條邊相互關(guān)聯(lián)，則稱它們相互覆蓋．覆蓋圖G的所有邊的一個頂點子集，稱為圖G的一個頂點覆蓋．類似，覆蓋圖G的所有頂點的一個邊子集稱為圖G的一個邊覆蓋．G的所有頂點覆蓋中頂點最少的數(shù)目稱為圖G的頂點覆蓋數(shù)，或者簡稱為點覆蓋記為α0一個圖G的邊覆蓋、最大邊覆蓋以及邊覆蓋數(shù)．并用α１來表示一個圖G的邊覆蓋數(shù)。分別用β０和β１來表示圖G的獨立數(shù)和匹配數(shù)。可知，關(guān)于一個階數(shù)為P的非平凡的連通圖的覆蓋數(shù)與獨立數(shù)具有如下關(guān)系：α０＋β０＝α１＋β１＝P由此結(jié)果容易看出，求一個圖G的最小覆蓋數(shù)等價于求這個圖的最大獨立集．而圖的最小覆蓋問題、圖的最小團(tuán)問題以及圖的最大獨立集問題兩兩等價第十九頁，共三十頁，2022年，8月28日設(shè)G＝(V,E)是一無向圖，其中V是圖中頂點集合，E是邊的集合．｜V｜表示圖中頂點的個數(shù)．｜E｜表示圖中的邊數(shù)．頂點覆蓋問題是找一V的子集S,找子集S，滿足（i,j)∈E,i和j至少有一個屬于S,即求解下列規(guī)劃模型：MINCXxi∈S,ST：∑(i=1..p)∑(j=i+1..P)aij(1-xi)(1-xj)=0C=[1,…1];X=[x1,x2…,xp];(aij)圖的鄰接矩陣Xi=1(vi∈S)否則為0；第二十頁，共三十頁，2022年，8月28日（6）（哈密頓圈問題——HC）包含G的每個頂點的軌叫做Hamilton(哈密頓)軌;閉的Hamilton軌叫做Hamilton圈或

圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種圖，即不重復(fù)地行遍所有的頂點再回到出發(fā)點。判斷某圖是否為哈密頓圖至今還是一個難題.總結(jié)判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法.1.觀察出哈密頓回路.第二十一頁，共三十頁，2022年，8月28日（6）（哈密頓圈問題——HC）1.觀察出哈密頓回路.下圖(周游世界問題)是哈密頓圖易知a

b

c

d

e

f

g

h

i

j

k

l

m

n

p

q

r

s

t

a為圖中的一條哈密頓回路.第二十二頁，共三十頁，2022年，8月28日（6）（哈密頓圈問題——HC）設(shè)G是n階無向簡單圖，若對于任意不相鄰的頂點vi,vj，均有d(vi)+d(vj)

n1()則G中存在哈密頓通路.設(shè)G為n(n3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有

d(vi)+d(vj)

n

（）則G中存在哈密頓回路，從而G為哈密頓圖.2．滿足條件（）的圖是哈密頓圖.例

完全圖Kn(n3)中任何兩個頂點u,v，均有

d(u)+d(v)=2(n1)

n（n3），所以Kn為哈密頓圖.3．哈密頓回圖的實質(zhì)是能將圖中所有的頂點排在同一個圈中.第二十三頁，共三十頁，2022年，8月28日例2.（婚姻問題）在遙遠(yuǎn)的地方有一位酋長，他想把三個女兒嫁出去。假定三個女兒為A、B、C，三位求婚者為X、Y、Z。每位求婚者對A、B、C愿出的財禮數(shù)視其對她們的喜歡程度而定,（見下表）：

XYZA3526B271028C147

問酋長應(yīng)如何嫁女，才能獲得最多的財禮（從總體上講，他的女婿最喜歡他的女兒）?；橐鰡栴}------P問題第二十四頁，共三十頁，2022年，8月28日例2.顯然是指派問題的實例，但它也可以看成是兩分圖賦權(quán)匹配問題的實例。用三個點表示酋長的三個女兒，將它們放在一邊。再用三個點表示求婚者，將它們放在另一邊。在有可能結(jié)婚的兩人之間畫一條邊，并在邊上寫上求婚者對這種結(jié)婚愿付出的財禮數(shù)，得到左圖。左圖是一個特殊的圖，它的頂點可以分成兩個子集，只有分屬不同子集的點才可能有邊相連（但也可以無邊），這樣的圖稱為兩分圖。定義3.(匹配)

圖G的一個匹配是指邊集E的一個子集M，M中的任意兩條邊均不具有公共的頂點。容易看出，酋長要解的問題是在上面的兩分圖中找出一個具有最大權(quán)和的匹配，讀者不難由此得到一般兩分圖最大權(quán)匹配問題的數(shù)學(xué)模型。

以上舉的是一個P問題，下面來看一個NP難問題第二十五頁，共三十頁，2022年，8月28日用三個點表示酋長的三個女兒，將它們放在一邊。再用三個點表示求婚者，將它們放在另一邊。在有可能結(jié)婚的兩人之間畫一條邊，并在邊上寫上求婚者對這種結(jié)婚愿付出的財禮數(shù)，得到左圖。左圖是一個特殊的圖，它的頂點可以分成兩個子集，只有分屬不同子集的點才可能有邊相連（但也可以無邊），這樣的圖稱為兩分圖。定義3.(匹配)

圖G的一個匹配是指邊集E的一個子集M，M中的任意兩條邊均不具有公共的頂點。容易看出，酋長要解的問題是在上面的兩分圖中找出一個具有最大權(quán)和的匹配，讀者不難由此得到一般兩分圖最大權(quán)匹配問題的數(shù)學(xué)模型。

以上舉的是一個P問題，下面來看一個NP難問題第二十六頁，共三十頁，2022年，8月28日例3

（裝箱問題——Bin—packing）有一批待裝箱的物品J={p1,…,pn}，pj的長度為l(pj)?，F(xiàn)有一批容量為C的箱子（足夠數(shù)量），要求找到一種裝箱方法，使得所用的箱子數(shù)最少。

例3是一個一維的裝箱問題。例如，我們有一批具有相同長度的鋼材，如果想取出幾根已知長度的鋼料生產(chǎn)某種設(shè)備，當(dāng)然會希望少用幾根原始鋼材以減少浪費。此時，我們就遇到了一個一維的Bin—packing問題。當(dāng)我們想從購買來的三夾板上鋸出n塊已知長、寬的板來制作家具時，遇到的是二維Bin—packing問題。而當(dāng)我們真正想把一批已知長、寬、高的物體裝入具有相同尺寸的箱子時，又遇到了三維的。下面的定理告訴我們，即使是一維的Bin—packing問題也是NP完全的，故二維和三維的Bin—packing問題更不可能是P問題（它們也是NP完全的）。定理1.

（