[教育]約制、放寬方法在解題中的應(yīng)用

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

2、放寬”方法,,,加強(qiáng)聯(lián)系,簡化關(guān)系,,[例題]消防站（POJ2152）,LTC國有n個城市。城市間連著公路。每兩個城市間有且只有一條通路。由于常發(fā)生火災(zāi)，LTC決定在某些城市建消防站。在城市k建一個消防站需要W(k)的費(fèi)用。每個城市k在距離D(k)范圍內(nèi),必須選擇最近的消防站作為負(fù)責(zé)站。LTC想用最少的費(fèi)用來滿足以上要求。,,,,①(W:2;D:3),②(W:2;D:1),③(W:2;D:1),④(W:2;D:1),3,3,3,,

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

4、試與探索,首先,確定狀態(tài)。 一般地，狀態(tài)有參數(shù)Root—— 表示研究對象為Root的子樹。如果只用Besti表示在i的子樹中修 建滿足要求的消防站的最少費(fèi)用，,狀態(tài)轉(zhuǎn)移方程？？,嘗試與探索,,① (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

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

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

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

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

9、添限制 —— 令P1到負(fù)責(zé)站Pm的路徑為P1 P2 P3……Pm，則任意Pi的負(fù)責(zé)站都為Pm。,“約制”方法,P1——P2——P3——P4……Pm,,,,,“約制”方法,下面通過構(gòu)造證明至少存在一個最優(yōu)解滿足該性質(zhì)——P1到負(fù)責(zé)站Pm的路徑P1 P2……Pm中任意Pi的負(fù)責(zé)站都為Pm。,“約制”方法,證明：假設(shè)某最優(yōu)解不滿足這性質(zhì)。Ⅰ構(gòu)造：⑴增加結(jié)點(diǎn)s，在s和有消防 站的結(jié)點(diǎn)間連一條權(quán)為0的邊。

10、 ⑵以s為源點(diǎn)做Dijkstra，記 錄下前驅(qū)結(jié)點(diǎn)。 ⑶如果結(jié)點(diǎn)上有消防站則選擇它為負(fù)責(zé)站，否則選擇前驅(qū)結(jié)點(diǎn)的負(fù)責(zé)站為負(fù)責(zé)站。,“約制”方法,最小費(fèi)用=2,,②(W:1;D:2),1,,③(W:1;D:1),1,①(W:1;D:2),,④(W:1;D:1),1,,,,,s,,,,,0,0,“約制”方法,Ⅱ此方案滿足上述性質(zhì)和必要限制： 1、設(shè)任意一個結(jié)點(diǎn)到源點(diǎn)的最短路為P1 P2 P3

11、……Pm s；　即任意Pi的負(fù)責(zé)站都為Pm。,P1……Pm-2——Pm-1—— Pm——s,,,,,“約制”方法,2、結(jié)點(diǎn)都選擇最近消防站，所以到負(fù)責(zé)站的距離不超過D(這結(jié)點(diǎn))； 3、構(gòu)造選取的消防站與最優(yōu)解一樣，所以總費(fèi)用最少。Ⅲ 綜上所述，總存在一個最優(yōu)解 (構(gòu)造出來的方案)滿足上述的性質(zhì)。如今這限制可以安全地增添上了。,轉(zhuǎn)移方程,首先確定下Best的轉(zhuǎn)移方程下面對F進(jìn)行分析： ①當(dāng)dis(i,j)&

12、gt;D(i)時,令 =+∞ ， 這表示不存在此狀態(tài) 。 ②當(dāng)dis(i,j) D(i)時,,,轉(zhuǎn)移方程,(1) 當(dāng)j在i的子樹外時， (2)當(dāng)i=j時, (3)當(dāng)j不等于i并且在i的子樹內(nèi)時, 令j在i的兒子child的子樹內(nèi),,復(fù)雜度分析,時間復(fù)雜度為空間復(fù)雜度為編程復(fù)雜度低,,小結(jié),原始模型,,,“放寬”方法,,確定狀態(tài),,,確定轉(zhuǎn)移方程,“約制”方法,,,解決問題,總

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

14、 (1)當(dāng)j在i的子樹外時， i的兒子k有兩個選擇： 選擇k的子樹內(nèi)或外 的消防站為負(fù)責(zé)站。返回,,當(dāng)選擇樹內(nèi)的為負(fù)責(zé)站時，所需的最少費(fèi)用為 ，,當(dāng)選擇樹外的為負(fù)責(zé)站時，根據(jù)新添的限制必須選擇j上的消防站作為負(fù)責(zé)站。所需的最少費(fèi)用為 。,j / i /k,,,轉(zhuǎn)移方程,②當(dāng)dis(i,j) D(i)時,

15、 (2)當(dāng)i=j時, i的兒子的選擇情況與⑴ 一樣。此時還要加上 建j上的消防站的費(fèi)用。返回,,i(i=j) /k,,,轉(zhuǎn)移方程,②當(dāng)dis(i,j) D(i)時, (3)當(dāng)j不等于i并且在i的子樹內(nèi)時 , 此時j必存在于以i的某個兒子 child為根的子樹里返回,,如果i的兒子k不等于child,則其選擇情況與⑴中一樣,

16、child根據(jù)新添的限制它只能選擇j上的消防站作為負(fù)責(zé)站,i \ child \ j,i \ child \ j,i / \k child \ j,,,,,時間復(fù)雜度分析,對于每一個確定的j,計(jì)算Fi,j需要Ｏ(i的兒子數(shù))的時間,所以計(jì)算F1, j、F2, j……

17、Fn, j 總共需要O(總兒子數(shù))=O(n)的時間。因此，總的時間復(fù)雜度為,一張一弛,在保證能找到答案的前提下，對過于寬松而茫無頭緒的條件、限制進(jìn)行約制;對于過于嚴(yán)格而阻撓前進(jìn)的條件、限制進(jìn)行放寬。 一張一弛不僅是文武之道，也是解題之道。,一張一馳——,,能應(yīng)用“約制”方法的題目: POI2005《knights》 CEOI《鋸木廠》《高斯消元解多元一次方程》……能應(yīng)用“放寬”方法的題目： WC2005《友好的