約制放寬方法在解題中的應(yīng)用

1、“約制、放寬”方法在解題中的應(yīng)用 “約制、放寬”方法的簡單定義“約制約制”方法方法添增添增一些一些約束約束的的條條件、限制件、限制，并，并保證保證在這些條件和限在這些條件和限制下依然能制下依然能找到解找到解。“約制、放寬”方法的簡單定義“放寬放寬”方法方法減除、放寬減除、放寬一些一些條條件、限制件、限制，并，并保證保證在這些條件和限在這些條件和限制下依然能制下依然能找到解找到解。引言 在分析問題、設(shè)計(jì)算法時(shí)，我們常在分析問題、設(shè)計(jì)算法時(shí)，我們常常覺得條件、限制常覺得條件、限制過于過于繁雜繁雜過于過于嚴(yán)格嚴(yán)格過于過于寬松寬松過于過于獨(dú)立獨(dú)立“約制約制”方法方法“放寬放寬”方法方法加強(qiáng)聯(lián)系加強(qiáng)聯(lián)系

2、簡化關(guān)系簡化關(guān)系例題消防站（poj2152） ltc國有國有n個(gè)城市。城市間連著個(gè)城市。城市間連著公路。公路。每兩個(gè)城市間有且只有一條每兩個(gè)城市間有且只有一條通路。通路。由于常發(fā)生火災(zāi)，由于常發(fā)生火災(zāi)，ltc決定決定在某些城市建消防站。在某些城市建消防站。在城市在城市k建建一個(gè)消防站需要一個(gè)消防站需要w(k)的費(fèi)用。每的費(fèi)用。每個(gè)城市個(gè)城市k在距離在距離d(k)范圍內(nèi)范圍內(nèi),必須選必須選擇最近的消防站作為負(fù)責(zé)站擇最近的消防站作為負(fù)責(zé)站。ltc想用最少的費(fèi)用來滿足以上要求。想用最少的費(fèi)用來滿足以上要求。(w:2;d:3) (w:2;d:1) (w:2;d:1) (w:2;d:1)333 (w:2

3、:d:3) (w:2;d:3) (w:2;d:3) (w:2;d:3)333最少費(fèi)用最少費(fèi)用=6最少費(fèi)用最少費(fèi)用=2數(shù)學(xué)模型以城市為結(jié)點(diǎn)以城市為結(jié)點(diǎn),公路為邊公路為邊, 路長為路長為邊權(quán)構(gòu)樹。令邊權(quán)構(gòu)樹。令dis(i,j)為結(jié)點(diǎn)為結(jié)點(diǎn)i、j間的距離。任務(wù)是建一些消防站，間的距離。任務(wù)是建一些消防站，使得任意結(jié)點(diǎn)使得任意結(jié)點(diǎn)i,都有都有 并得使得目標(biāo)函數(shù)并得使得目標(biāo)函數(shù) 最小化。最小化。d(i)j |j)mindis(i,上有消防站上有消防站iiwz)(算法模型分析 搜索搜索?圖論算法？圖論算法？樹型動態(tài)規(guī)劃樹型動態(tài)規(guī)劃?time limit exceed想不到好算法想不到好算法嘗試與探索首先首

4、先,確定狀態(tài)。確定狀態(tài)。 一般地，狀態(tài)有參數(shù)一般地，狀態(tài)有參數(shù)root 表示研究對象為表示研究對象為root的子樹。的子樹。如果只用如果只用besti表示在表示在i的子樹中修的子樹中修 建滿足要求的消防站的最少費(fèi)用，建滿足要求的消防站的最少費(fèi)用，嘗試與探索 (w:1;d:1;best:?) (w:1;d:1;best:1)1(w:1;d:1;best:1)1第一種情況第一種情況:消防站在消防站在best1=d(2)=1第二種情況第二種情況:消防站在消防站在best1=d(1)+d(3)=2bestbest2 2,best,best3 3已定已定, ,求求bestbest1 1有兩種情況有兩種情

5、況嘗試與探索為了解決這種情況，我們通常會為了解決這種情況，我們通常會增加一個(gè)參數(shù)增加一個(gè)參數(shù) 最近消防站的距離或編號？最近消防站的距離或編號？ 樹內(nèi)或外的最近消防站的編號？樹內(nèi)或外的最近消防站的編號？難以找到好的轉(zhuǎn)移方程難以找到好的轉(zhuǎn)移方程!初步分析 在分析中發(fā)現(xiàn)：在分析中發(fā)現(xiàn)： 在狀態(tài)轉(zhuǎn)移時(shí)，難以保證最近消防在狀態(tài)轉(zhuǎn)移時(shí)，難以保證最近消防站的距離或編號與定義的一致站的距離或編號與定義的一致 換句話說，就是換句話說，就是狀態(tài)定義太嚴(yán)狀態(tài)定義太嚴(yán)格、題目要求太苛刻格、題目要求太苛刻。主要障礙主要障礙“結(jié)點(diǎn)結(jié)點(diǎn)i在在d(i)范圍內(nèi)范圍內(nèi),必必須須選擇選擇最近的消防站最近的消防站作為負(fù)責(zé)站作為負(fù)責(zé)站

6、 ”“放寬”方法 “放寬”方法其實(shí)我們無須知道最近的消防站在其實(shí)我們無須知道最近的消防站在哪，而只要在哪，而只要在d范圍內(nèi)有消防站就范圍內(nèi)有消防站就行了。行了。 限制限制:“結(jié)點(diǎn)結(jié)點(diǎn)i在在d(i)范圍內(nèi)范圍內(nèi),必須必須選選擇擇最近的消防站最近的消防站作為負(fù)責(zé)站作為負(fù)責(zé)站 ”“結(jié)點(diǎn)結(jié)點(diǎn)i在在d(i)范圍內(nèi)范圍內(nèi),可以選擇可以選擇任意的消防站任意的消防站作為負(fù)責(zé)站作為負(fù)責(zé)站 ”可以放寬為可以放寬為 最近消防站最近消防站 轉(zhuǎn)化轉(zhuǎn)化 任意消防站任意消防站“放寬”方法現(xiàn)在結(jié)點(diǎn)享有一定現(xiàn)在結(jié)點(diǎn)享有一定“自由權(quán)自由權(quán)”了，了，此時(shí)就有必要定義新狀態(tài)。此時(shí)就有必要定義新狀態(tài)?！胺艑挕狈椒盍?表示表示 1、在

7、、在i的子樹建一些消防站；的子樹建一些消防站； 2、在、在j上上必須必須建一個(gè)消防站；建一個(gè)消防站； 3、i的子樹結(jié)點(diǎn)選擇的子樹結(jié)點(diǎn)選擇樹內(nèi)或樹內(nèi)或j上上 的可選消防站為負(fù)責(zé)站；的可選消防站為負(fù)責(zé)站； 4、i必須選擇必須選擇j上消防站上消防站為負(fù)責(zé)站；為負(fù)責(zé)站； 的最少總費(fèi)用的最少總費(fèi)用(j在在i的子樹外則不算在內(nèi)的子樹外則不算在內(nèi))jif,“放寬”方法 (w:2;d:1) (w:1;d:1) (w:2;d:1) (w:4;d:2)11264, 1fbest1=2 !求求f1,4“放寬”方法(w:100;d:1) (w:1:d:1) (w:1;d:2) (w:1;d:1)111 (w:100;

8、d:3)2)4()2(5 , 1wwf1求求f1,5“放寬”方法這樣定義的好處是，這樣定義的好處是， “最近的消防最近的消防站站”在定義中消失了。在定義中消失了。這種自由為轉(zhuǎn)移方程提供了很大方這種自由為轉(zhuǎn)移方程提供了很大方便。便。進(jìn)一步分析 然而，此時(shí)要定下轉(zhuǎn)移方程還是遇然而，此時(shí)要定下轉(zhuǎn)移方程還是遇到了一點(diǎn)點(diǎn)困難，總覺得結(jié)點(diǎn)間相到了一點(diǎn)點(diǎn)困難，總覺得結(jié)點(diǎn)間相對獨(dú)立。對獨(dú)立。原因：策略選取的任意性導(dǎo)致原因：策略選取的任意性導(dǎo)致“約制”方法動態(tài)規(guī)劃講求拓?fù)漤樞蚝蜔o后效性。動態(tài)規(guī)劃講求拓?fù)漤樞蚝蜔o后效性。于是不妨對策略增添限制于是不妨對策略增添限制 令令p1到負(fù)責(zé)站到負(fù)責(zé)站pm的路徑為的路徑為p1

9、 p2 p3pm，則任意，則任意pi的負(fù)責(zé)站都為的負(fù)責(zé)站都為pm。 “約制”方法p1p2p3p4pm“約制”方法下面通過下面通過構(gòu)造構(gòu)造證明至少存在一個(gè)最證明至少存在一個(gè)最優(yōu)解滿足該性質(zhì)優(yōu)解滿足該性質(zhì)p1到負(fù)責(zé)站到負(fù)責(zé)站pm的路徑的路徑p1 p2pm中任意中任意pi的負(fù)責(zé)站都為的負(fù)責(zé)站都為pm?！凹s制”方法證明證明：假設(shè)某最優(yōu)解不滿足這性質(zhì)。：假設(shè)某最優(yōu)解不滿足這性質(zhì)。構(gòu)造構(gòu)造：增加結(jié)點(diǎn)增加結(jié)點(diǎn)s，在，在s和有消防和有消防 站的結(jié)點(diǎn)間連一條權(quán)為站的結(jié)點(diǎn)間連一條權(quán)為0的邊。的邊。 以以s為源點(diǎn)做為源點(diǎn)做dijkstra，記，記 錄下前驅(qū)結(jié)點(diǎn)。錄下前驅(qū)結(jié)點(diǎn)。 如果結(jié)點(diǎn)上有消防站則選如果結(jié)點(diǎn)上有消防

10、站則選擇它為負(fù)責(zé)站，否則選擇前擇它為負(fù)責(zé)站，否則選擇前驅(qū)結(jié)點(diǎn)的負(fù)責(zé)站為負(fù)責(zé)站。驅(qū)結(jié)點(diǎn)的負(fù)責(zé)站為負(fù)責(zé)站?！凹s制”方法最小費(fèi)用最小費(fèi)用=2 (w:1;d:2)1(w:1;d:1)1(w:1;d:2)(w:1;d:1)1s00“約制”方法此方案滿足上述性質(zhì)和必要限制：此方案滿足上述性質(zhì)和必要限制： 1、設(shè)任意一個(gè)結(jié)點(diǎn)到源點(diǎn)的最短、設(shè)任意一個(gè)結(jié)點(diǎn)到源點(diǎn)的最短路為路為p1 p2 p3pm s；即任意即任意pi的負(fù)責(zé)站都為的負(fù)責(zé)站都為pm。p1pm-2pm-1 pms“約制”方法 2、結(jié)點(diǎn)都選擇最近消防站，所以、結(jié)點(diǎn)都選擇最近消防站，所以到負(fù)責(zé)站的距離不超過到負(fù)責(zé)站的距離不超過d(這結(jié)點(diǎn)這結(jié)點(diǎn))； 3、構(gòu)

11、造選取的消防站與最優(yōu)解一、構(gòu)造選取的消防站與最優(yōu)解一樣，所以總費(fèi)用最少。樣，所以總費(fèi)用最少。 綜上所述，總存在一個(gè)最優(yōu)解綜上所述，總存在一個(gè)最優(yōu)解 ( (構(gòu)造出來的方案構(gòu)造出來的方案) )滿足上述的性質(zhì)。滿足上述的性質(zhì)。如今這限制可以安全地增添上了。如今這限制可以安全地增添上了。轉(zhuǎn)移方程首先確定下首先確定下best的轉(zhuǎn)移方程的轉(zhuǎn)移方程下面對下面對f進(jìn)行分析進(jìn)行分析： 當(dāng)當(dāng)dis(i,j)d(i)時(shí)時(shí),令令 =+ ， 這表示不存在此狀態(tài)這表示不存在此狀態(tài) 。 當(dāng)當(dāng)dis(i,j) d(i)時(shí)時(shí),jif,|min,的子樹中在ijfbestjii轉(zhuǎn)移方程 (1) 當(dāng)當(dāng)j在在i的子樹外時(shí)，的子樹外時(shí)，

12、 (2)當(dāng)當(dāng)i=j時(shí)時(shí), , (3)當(dāng)當(dāng)j不等于不等于i并且在并且在i的子樹內(nèi)時(shí)的子樹內(nèi)時(shí), , 令令j在在i的兒子的兒子child的子樹內(nèi)的子樹內(nèi),的兒子為ikjkkjifbestf,min,的兒子為ikjkkjifbestjwf,min)(,childkikjkkjchildjifbestff并且的兒子為,min,復(fù)雜度分析 時(shí)間復(fù)雜度時(shí)間復(fù)雜度為為空間復(fù)雜度為空間復(fù)雜度為編程復(fù)雜度低編程復(fù)雜度低)(2no)(2no小結(jié) 原始模型原始模型“放寬放寬”方法方法確定狀態(tài)確定狀態(tài)確定轉(zhuǎn)移方程確定轉(zhuǎn)移方程“約制約制”方法方法解決問題解決問題總結(jié)在應(yīng)用這兩種方法的時(shí)候，首先要在應(yīng)用這兩種方法的時(shí)候，

13、首先要摸清這兩者的適用范圍、所起的作摸清這兩者的適用范圍、所起的作用和效果。用和效果。 一張一弛一張一弛作為一種解題方法，是需作為一種解題方法，是需要在思索、做題中慢慢形成的。除要在思索、做題中慢慢形成的。除了實(shí)踐外，還有幾點(diǎn)是需要注意的：了實(shí)踐外，還有幾點(diǎn)是需要注意的：總結(jié) 敢于敢于創(chuàng)新創(chuàng)新 敢于敢于猜想猜想 敢于敢于類比類比 敢于敢于拓展拓展 其中敢于創(chuàng)新顯得尤為重要其中敢于創(chuàng)新顯得尤為重要,只有不只有不斷創(chuàng)新和實(shí)踐，才能斷創(chuàng)新和實(shí)踐，才能“撥得云開見撥得云開見月明月明”。e-mail:344368722qq.com轉(zhuǎn)移方程當(dāng)當(dāng)dis(i,j) d(i)時(shí)時(shí), (1)當(dāng)當(dāng)j在在i的子樹外時(shí)

14、，的子樹外時(shí)， i的兒子的兒子k有兩個(gè)選擇：有兩個(gè)選擇： 選擇選擇k的子樹的子樹內(nèi)或外內(nèi)或外 的消防站為負(fù)責(zé)站。的消防站為負(fù)責(zé)站。返回返回 的兒子為ikjkkjifbestf,min,當(dāng)選擇樹內(nèi)的為負(fù)責(zé)站時(shí)，當(dāng)選擇樹內(nèi)的為負(fù)責(zé)站時(shí)，所需的最少費(fèi)用為所需的最少費(fèi)用為 ，kbest當(dāng)選擇樹外的為負(fù)責(zé)站時(shí)，當(dāng)選擇樹外的為負(fù)責(zé)站時(shí)，根據(jù)新添的限制必須選擇根據(jù)新添的限制必須選擇j上的消防站作為負(fù)責(zé)站。上的消防站作為負(fù)責(zé)站。所需的最少費(fèi)用為所需的最少費(fèi)用為 。jkf, j / i /k轉(zhuǎn)移方程當(dāng)當(dāng)dis(i,j) d(i)時(shí)時(shí), (2)當(dāng)當(dāng)i=j時(shí)時(shí), i的兒子的選擇情況與的兒子的選擇情況與 一樣。此時(shí)還

15、要加上一樣。此時(shí)還要加上 建建j上的消防站的費(fèi)用。上的消防站的費(fèi)用。返回返回 的兒子為ikjkkjifbestjwf,min)(, i(i=j) /k轉(zhuǎn)移方程當(dāng)當(dāng)dis(i,j) d(i)時(shí)時(shí), (3)當(dāng)當(dāng)j不等于不等于i并且在并且在i的子樹內(nèi)的子樹內(nèi)時(shí)時(shí) , 此時(shí)此時(shí)j必存在于以必存在于以i的某個(gè)兒子的某個(gè)兒子 child為根的子樹里為根的子樹里返回返回 childkikjkkjchildjifbestff并且的兒子為,min,如果如果i的兒子的兒子k不等于不等于child,則則其選擇情況與中一樣其選擇情況與中一樣child根據(jù)新添的限制它只能根據(jù)新添的限制它只能選擇選擇j上的消防站作為負(fù)責(zé)站上的消防站作為負(fù)責(zé)站 i child j i child j i / k child j 時(shí)間復(fù)雜度分析對于每一個(gè)確定的對于每一個(gè)確定的j,計(jì)算計(jì)算fi,j需需要要(i的兒子數(shù)的兒子數(shù))的時(shí)間的時(shí)間,所以計(jì)所以計(jì)算算f1, j、f2, j fn, j 總共需要總共需要o(總兒子數(shù)總兒子數(shù))=o(n)的時(shí)間。的時(shí)間。因此，總的時(shí)間復(fù)雜度為因此，總的時(shí)間復(fù)雜度為)(2no一張一弛 在保證能找到答案在保證能找到答案的前提下，對過于寬松而茫無頭緒的前提下，對過于寬松