消防站解題報(bào)告

1、消防站解題報(bào)告廣東中山紀(jì)念中學(xué) 陳啟峰【問題描述】Z國有n個(gè)城市，從1到n給這些城市編號(hào)。城市之間連著高速公路，并且每兩個(gè)城市之間有且只有一條通路。不同的高速公路可能有不同的長度。最近Z國經(jīng)常發(fā)生火災(zāi)，所以當(dāng)?shù)卣疀Q定在某些城市修建一些消防站。在城市k修建一個(gè)消防站須要花費(fèi)大小為的費(fèi)用。函數(shù)W對(duì)于不同的城市可能有不同的取值。如果在城市k沒有消防站，那么它到離它最近的消防站的距離不能超過。每個(gè)城市在不超過距離的前提下，必須選擇最近的消防站作為負(fù)責(zé)站。函數(shù)D對(duì)于不同的城市可能有不同的取值。為了節(jié)省錢，當(dāng)?shù)卣Ｍ阌米钌俚目傎M(fèi)用修建一些消防站，并且使得這些消防站滿足上述的要求?！締栴}分析】【數(shù)學(xué)模

2、型】首先，以n個(gè)城市為結(jié)點(diǎn)、高速公路為邊，高速公路長為邊權(quán)構(gòu)造成一個(gè)圖。由性質(zhì)“每兩個(gè)城市之間有且只有一條通路可知這個(gè)圖是一棵樹。令為結(jié)點(diǎn)和結(jié)點(diǎn)之間的距離。任務(wù)是找出一個(gè)01序列，使得對(duì)于,都有并且使得目標(biāo)函數(shù)最小化?！舅惴Ｐ头治觥坑捎谶@題涉及到距離和圖論等方面，便可猜測這是一道用圖論算法解決的問題?？墒窃趪L試過許多圖論算法之后卻發(fā)現(xiàn)這種猜測是走不通的。這時(shí)就要充分地利用問題的特殊性。我們知道這圖是一棵樹，并且這題是求目標(biāo)函數(shù)最小化的問題。根據(jù)這些特性，我們根本上可以肯定這題的算法是樹型動(dòng)態(tài)規(guī)劃?！敬_定動(dòng)態(tài)規(guī)劃時(shí)的矛盾】用動(dòng)態(tài)規(guī)劃算法解題首先要做的是確定好狀態(tài)，這應(yīng)該是不容置疑的，因?yàn)闋顟B(tài)表

3、示是動(dòng)態(tài)規(guī)劃中的重中之重。一般地，樹型動(dòng)態(tài)規(guī)劃的狀態(tài)中會(huì)有一個(gè)參數(shù),表示此狀態(tài)的研究對(duì)象是以為根的子樹。但是，如果僅用表示在以為根的子樹中，修建符合要求(子樹中的所有結(jié)點(diǎn)到最近消防站的距離不超過其對(duì)應(yīng)的函數(shù)D值)的消防站的最小費(fèi)用即狀態(tài)只用上述的一個(gè)參數(shù)，那么狀態(tài)轉(zhuǎn)移方程是無法找到的。因?yàn)檫@種狀態(tài)表示無法反映出在哪里修建了消防站、離最近的消防站的詳細(xì)情況。為了解決這種情況，我們通常會(huì)增加一個(gè)參數(shù)，可稱作增加一維。這時(shí)應(yīng)該增加的參數(shù)既可以是到最近消防站的距離，又可以是的最近消防站的編號(hào)，也可以是樹內(nèi)的最近消防站的編號(hào)，同樣可以是樹外的最近消防站的編號(hào)。到底更加哪個(gè)參數(shù)是可行的呢？可是事與愿違！所

4、有的這些狀態(tài)表示都無法找到動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程。難道狀態(tài)還要增加一個(gè)參數(shù)嗎？還是這題本身是NP完全性問題、而不是用動(dòng)態(tài)規(guī)劃題目？別急，先來做個(gè)分析吧?！境醪椒治觥糠治錾厦嬲也坏綘顟B(tài)轉(zhuǎn)移方程的原因。在分析中便會(huì)發(fā)現(xiàn)產(chǎn)生這些矛盾的主要原因是，在狀態(tài)轉(zhuǎn)移時(shí)不能保證到最近消防站的距離或編號(hào)與定義的一致?lián)Q句話說，就是狀態(tài)的定義太嚴(yán)格了再換句話說，題目的要求太嚴(yán)格了。所以，此時(shí)當(dāng)務(wù)之急是放寬題目的要求?！尽胺艑挿椒ㄞD(zhuǎn)化限制】 現(xiàn)在面對(duì)的主要障礙無疑是，“每個(gè)城市在不超過距離的前提下，必須選擇最近的消防站作為負(fù)責(zé)站這一嚴(yán)格限制在狀態(tài)轉(zhuǎn)移中起著干擾作用。其實(shí)，我們并不須要知道最近的消防站是哪個(gè)，而只要保證在距離內(nèi)

5、至少有一個(gè)消防站就足夠了。于是可以嘗試放寬這個(gè)限制：把這個(gè)限制轉(zhuǎn)化為“每個(gè)城市在不超過距離的前提下，可以選擇任意一個(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é)站

6、；的最少總費(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í)的限制過于寬松?！尽凹s制方法增添限制】動(dòng)態(tài)規(guī)劃算法講求拓?fù)漤樞蚝蜔o后效性。然而現(xiàn)在每個(gè)城市對(duì)負(fù)責(zé)站的選取是任意的，于是就不妨對(duì)策略選取增添限制假設(shè)城市選取城市的上消防站作為負(fù)責(zé)站，令到的路徑為，那么對(duì)于任意都有的負(fù)責(zé)站為。如果我們證明總是在一個(gè)最

7、優(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ì)和必要限制：1、 設(shè)任意一個(gè)結(jié)點(diǎn)到源點(diǎn)的路徑為,易知任意都有為的前驅(qū)，而的負(fù)責(zé)站為的負(fù)責(zé)站為的負(fù)責(zé)站為，所以任意都有的負(fù)責(zé)站為。2、 由于每個(gè)結(jié)點(diǎn)都選擇最近的消防站，所以它與負(fù)責(zé)站的距離不超過。3、 而構(gòu)造選取的消防站與最優(yōu)解是一樣的

8、，所以總費(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é)站。中選擇以為根的子樹內(nèi)的消防站為負(fù)責(zé)站時(shí)，其子樹所需的最少費(fèi)用為，中選擇以為根的子樹外的消防站為負(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ǔ)充。它們各自可以在