算法合集之“約制、放寬”方法在解題中的應(yīng)用-資料下載頁
2025-06-07 21:21本頁面
【正文】 過距離的前提下，可以選擇任意一個(gè)消防站作為負(fù)責(zé)站”。轉(zhuǎn)化后，求出的最優(yōu)解與轉(zhuǎn)化前的是一樣的。原因在于在轉(zhuǎn)化后，必定存在一個(gè)最優(yōu)解滿足性質(zhì)“每個(gè)城市在不超過距離的前提下，必須選擇最近的消防站作為負(fù)責(zé)站”?，F(xiàn)在每個(gè)城市都享有一定的“自由權(quán)”了，可以在自己的活動(dòng)范圍內(nèi)自由地選擇消防站作為負(fù)責(zé)站。此時(shí)就有必要把狀態(tài)表示重新定義一下——令表示① 在以為根的子樹里修建一些消防站；② 在結(jié)點(diǎn)必須修建一個(gè)消防站；③ 以為根的子樹內(nèi)的每個(gè)結(jié)點(diǎn)在不超過距離的前提下,選擇一個(gè)在子樹內(nèi)或結(jié)點(diǎn)上的消防站作為負(fù)責(zé)站；④ 結(jié)點(diǎn)必須選擇結(jié)點(diǎn)上的消防站作為負(fù)責(zé)站；的最少總費(fèi)用（如果在樹外則不算在內(nèi)）。自然而然地“最近的消防站”這幾個(gè)字在定義中消失了，這為以后確定動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程提供了很大的方便?！具M(jìn)一步分析】 經(jīng)過“放寬”方法放寬限制后，狀態(tài)表示基本上已經(jīng)定下來了。進(jìn)而要做的是確定動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程。但是此時(shí)要確定下轉(zhuǎn)移方程還是遇到了一點(diǎn)困難，總覺得欠缺一些性質(zhì)、關(guān)系之類的。相信聰明的讀者已經(jīng)挖掘出原因了，那就是此時(shí)的限制過于寬松。【“約制”方法增添限制】動(dòng)態(tài)規(guī)劃算法講求拓?fù)漤樞蚝蜔o后效性。然而現(xiàn)在每個(gè)城市對(duì)負(fù)責(zé)站的選取是任意的，于是就不妨對(duì)策略選取增添限制——假設(shè)城市選取城市的上消防站作為負(fù)責(zé)站，令到的路徑為……，那么對(duì)于任意都有的負(fù)責(zé)站為。如果我們證明總是在一個(gè)最優(yōu)解滿足上述的性質(zhì)，那么此限制就能被增添了。下面將證明必有一個(gè)最優(yōu)解滿足上述的性質(zhì)。證明：令某個(gè)最優(yōu)解對(duì)應(yīng)的01序列為。構(gòu)造：在01序列的布局下，首先增加一個(gè)結(jié)點(diǎn)，在和有消防站的結(jié)點(diǎn)之間連一條權(quán)值為0的邊。然后以為源點(diǎn)做一次Dijkstra，并記錄下前驅(qū)結(jié)點(diǎn)。對(duì)于每個(gè)結(jié)點(diǎn)，如果結(jié)點(diǎn)有消防站則選擇其上的消防站為負(fù)責(zé)站，否則選擇前驅(qū)的負(fù)責(zé)站為其負(fù)責(zé)站。滿足上述性質(zhì)和必要限制： 設(shè)任意一個(gè)結(jié)點(diǎn)到源點(diǎn)的路徑為……,易知任意都有為的前驅(qū)，而的負(fù)責(zé)站為的負(fù)責(zé)站為……的負(fù)責(zé)站為，所以任意都有的負(fù)責(zé)站為。 由于每個(gè)結(jié)點(diǎn)都選擇最近的消防站，所以它與負(fù)責(zé)站的距離不超過。 而構(gòu)造選取的消防站與最優(yōu)解是一樣的，所以總費(fèi)用是最少的。綜上所述，總是在一個(gè)最優(yōu)解(構(gòu)造出來的方案)滿足上述的性質(zhì)。證畢。如今，上述的限制終于可以被正確地增添上了?！敬_定動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程】經(jīng)過兩番轉(zhuǎn)化后，動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程已經(jīng)可以被確定下來了。為了轉(zhuǎn)移方便，先定義一個(gè)簡單的輔助狀態(tài)，表示在以為根的子樹中，修建合符要求(子樹中所有結(jié)點(diǎn)到其樹內(nèi)的負(fù)責(zé)站的距離不超過其對(duì)應(yīng)的函數(shù)D值)的消防站的最小費(fèi)用。明顯地下面對(duì)進(jìn)行分析：①當(dāng)時(shí)，∞，這表示不存在狀態(tài)；②當(dāng)時(shí)，⑴當(dāng)在以為根的子樹外時(shí)，對(duì)于的每個(gè)兒子都有兩種選擇：選擇以為根的子樹內(nèi)或外的消防站為負(fù)責(zé)站。當(dāng)選擇以為根的子樹內(nèi)的消防站為負(fù)責(zé)站時(shí)，其子樹所需的最少費(fèi)用為，當(dāng)選擇以為根的子樹外的消防站為負(fù)責(zé)站時(shí)，根據(jù)新添的限制易知只可以選擇上的消防站作為負(fù)責(zé)站，此時(shí)其子樹所需的最少費(fèi)用為。綜上得到⑵當(dāng)時(shí)，的每個(gè)兒子的選擇情況與⑴中的一樣。此時(shí)還要加上修建上的消防站的費(fèi)用。因此⑶當(dāng)并且在以為根的子樹內(nèi)時(shí)，此時(shí)必定在的某個(gè)兒子的子樹里。對(duì)于的每個(gè)不是的兒子其選擇情況與⑴中的一樣，而對(duì)于，根據(jù)新添的限制它只能選擇作為負(fù)責(zé)站。綜上得到復(fù)雜度分析：時(shí)間復(fù)雜度為,空間復(fù)雜度為?！拘〗Y(jié)】“放寬”方法和“約制”方法不總是互相排斥、矛盾的，它們往往會(huì)互相補(bǔ)充。它們各自可以在需要它們的方面發(fā)揮特長——應(yīng)用“放寬”方法確定狀態(tài)。應(yīng)用“約制”方法確定狀態(tài)轉(zhuǎn)移方程。在保證能找到答案的前提下，對(duì)于過于嚴(yán)格而阻撓前進(jìn)的條件、限制，我們對(duì)它進(jìn)行“放寬”；對(duì)于過于寬松而茫無頭緒的條件、限制，我們對(duì)它進(jìn)行“約制”——這就是所謂的一張一弛了。一張一弛不僅是文武之道，更是解題之道?？偨Y(jié)不管是“約制”方法還是“放寬”方法，其目的都是要簡化問題。在應(yīng)用這兩種方法的時(shí)候，首先要摸清這兩者的適用范圍、所起的作用和效果。一般而言，當(dāng)條件、限制過于寬松時(shí)就用“約制”方法來約制它們，當(dāng)條件、限制過于繁雜時(shí)就用“放寬”方法來放寬它們。一張一弛作為一種解題方法，是須要在思索、做題中慢慢形成的。除了實(shí)踐外，還有幾點(diǎn)是須要注意的：敢于創(chuàng)新、敢于猜想、敢于類比、敢于拓展。其中敢于創(chuàng)新顯得尤為重要,因?yàn)橹挥胁粩鄤?chuàng)新和實(shí)踐，才能“撥得云開見月明”?！靖兄x】衷心感謝向老師給我的指導(dǎo)和意見。衷心感謝長郡中學(xué)的郭化陽給我解答了例1。衷心感謝周戈林、郭化陽、楊沐給我提出寶貴意見。第 20 頁 共 20 頁
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1