消防站解題報告

消防站解題報告廣東中山紀念中學(xué)陳啟峰【問題描述】Z國有n個個城市，從從1到nn給這些些城市編編號。城城市之間間連著高高速公路路，并且且每兩個個城市之之間有且且只有一一條通路路。不同同的高速速公路可可能有不不同的長長度。最最近Z國國經(jīng)常發(fā)發(fā)生火災(zāi)災(zāi)，所以以當(dāng)?shù)卣疀Q定定在某些些城市修修建一些些消防站站。在城城市k修修建一個個消防站站須要花花費大小小為的費費用。函函數(shù)W對對于不同同的城市市可能有有不同的的取值。如如果在城城市k沒沒有消防防站，那那么它到到離它最最近的消消防站的的距離不不能超過過。每個個城市在在不超過過距離的的前提下下，必須須選擇最最近的消消防站作作為負責(zé)責(zé)站。函函數(shù)D對對于不同同的城市市可能有有不同的的取值。為為了節(jié)省省錢，當(dāng)當(dāng)?shù)卣Ｍ隳阌米钌偕俚目傎M費用修建建一些消消防站，并并且使得得這些消消防站滿滿足上述述的要求求?！締栴}分析析】【數(shù)學(xué)模型型】首先，以nn個城市市為結(jié)點點、高速速公路為為邊，高高速公路路長為邊邊權(quán)構(gòu)造造成一個個圖。由由性質(zhì)“每兩個個城市之之間有且且只有一一條通路路”可知這這個圖是是一棵樹樹。令為結(jié)點和和結(jié)點之之間的距距離。任任務(wù)是找找出一個個01序序列，使使得對于于,都有有并且使得目目標(biāo)函數(shù)數(shù)最小化。【算法模型型分析】由于這題涉涉及到距距離和圖圖論等方方面，便便可猜想想這是一一道用圖圖論算法法解決的的問題?？煽墒窃趪L嘗試過許許多圖論論算法之之后卻發(fā)發(fā)現(xiàn)這種種猜想是是走不通通的。這時就要充充分地利利用問題題的特殊殊性。我我們知道道這圖是是一棵樹樹，并且且這題是是求目標(biāo)標(biāo)函數(shù)最最小化的的問題。根根據(jù)這些些特性，我我們基本本上可以以肯定這這題的算算法是樹樹型動態(tài)態(tài)規(guī)劃?！敬_定動態(tài)態(tài)規(guī)劃時時的矛盾盾】用動態(tài)規(guī)劃劃算法解解題首先先要做的的是確定定好狀態(tài)態(tài)，這應(yīng)應(yīng)該是不不容置疑疑的，因因為狀態(tài)態(tài)表示是是動態(tài)規(guī)規(guī)劃中的的重中之之重。一一般地，樹樹型動態(tài)態(tài)規(guī)劃的的狀態(tài)中中會有一一個參數(shù)數(shù),表示此此狀態(tài)的的研究對對象是以以為根的的子樹。但是，如果果僅用表表示在以以為根的的子樹中中，修建建符合要要求(子子樹中的的所有結(jié)結(jié)點到最最近消防防站的距距離不超超過其對對應(yīng)的函函數(shù)D值值)的消消防站的的最小費費用———即狀態(tài)態(tài)只用上上述的一一個參數(shù)數(shù)，那么么狀態(tài)轉(zhuǎn)轉(zhuǎn)移方程程是無法法找到的的。因為為這種狀狀態(tài)表示示無法反反映出在在哪里修修建了消消防站、離離最近的的消防站站的詳細細情況。為了解決這這種情況況，我們們通常會會增加一一個參數(shù)數(shù)，可稱稱作增加加一維。這這時應(yīng)該該增加的的參數(shù)既既可以是是到最近近消防站站的距離離，又可可以是的的最近消消防站的的編號，也也可以是是樹內(nèi)的的最近消消防站的的編號，同同樣可以以是樹外外的最近近消防站站的編號號。到底底更加哪哪個參數(shù)數(shù)是可行行的呢？？可是事與愿愿違！所所有的這這些狀態(tài)態(tài)表示都都無法找找到動態(tài)態(tài)規(guī)劃轉(zhuǎn)轉(zhuǎn)移方程程。難道道狀態(tài)還還要增加加一個參參數(shù)嗎？？還是這這題本身身是NPP完全性性問題、而而不是用用動態(tài)規(guī)規(guī)劃題目目？別急急，先來來做個分分析吧?！境醪椒治鑫觥糠治錾厦嬲艺也坏綘顮顟B(tài)轉(zhuǎn)移移方程的的原因。在在分析中中便會發(fā)發(fā)現(xiàn)產(chǎn)生生這些矛矛盾的主主要原因因是，在在狀態(tài)轉(zhuǎn)轉(zhuǎn)移時不不能保證證到最近近消防站站的距離離或編號號與定義義的一致致——換句句話說，就就是狀態(tài)態(tài)的定義義太嚴格格了———再換句句話說，題題目的要要求太嚴嚴格了。所以，此時時當(dāng)務(wù)之之急是放放寬題目目的要求求?！尽胺艑挕狈椒ㄞD(zhuǎn)轉(zhuǎn)化限制制】現(xiàn)現(xiàn)在面對對的主要要障礙無無疑是，“每個城市在不超過距離的前提下，必須選擇最近的消防站作為負責(zé)站”這一嚴格限制在狀態(tài)轉(zhuǎn)移中起著干擾作用。其實，我們并不須要知道最近的消防站是哪個，而只要保證在距離內(nèi)至少有一個消防站就足夠了。于是可以嘗試放寬這個限制：把這個限制轉(zhuǎn)化為“每個城市在不超過距離的前提下，可以選擇任意一個消防站作為負責(zé)站”。轉(zhuǎn)化后，求求出的最最優(yōu)解與與轉(zhuǎn)化前前的是一一樣的。原原因在于于在轉(zhuǎn)化化后，必必定存在在一個最最優(yōu)解滿滿足性質(zhì)質(zhì)“每個城城市在不不超過距距離的前前提下，必必須選擇擇最近的的消防站站作為負負責(zé)站”?，F(xiàn)在每個城城市都享享有一定定的“自由權(quán)權(quán)”了，可可以在自自己的活活動范圍圍內(nèi)自由由地選擇擇消防站站作為負負責(zé)站。此此時就有有必要把把狀態(tài)表表示重新新定義一一下———令表示在以為根的的子樹里里修建一一些消防防站；在結(jié)點必須須修建一一個消防防站；以為根的子子樹內(nèi)的的每個結(jié)結(jié)點在不不超過距距離的前前提下,,選擇一一個在子子樹內(nèi)或或結(jié)點上上的消防防站作為為負責(zé)站站；結(jié)點必須選選擇結(jié)點點上的消消防站作作為負責(zé)責(zé)站；的最少總費費用（如如果在樹樹外則不不算在內(nèi)內(nèi)）。自自然而然然地“最近的的消防站站”這幾個個字在定定義中消消失了，這這為以后后確定動動態(tài)規(guī)劃劃轉(zhuǎn)移方方程提供供了很大大的方便便?！具M一步分分析】經(jīng)過“放寬寬”方法放寬寬限制后后，狀態(tài)態(tài)表示基基本上已已經(jīng)定下下來了。進進而要做做的是確確定動態(tài)態(tài)規(guī)劃轉(zhuǎn)轉(zhuǎn)移方程程。但是是此時要要確定下下轉(zhuǎn)移方方程還是是遇到了了一點困困難，總總覺得欠欠缺一些些性質(zhì)、關(guān)關(guān)系之類類的。相相信聰明明的讀者者已經(jīng)挖挖掘出原原因了，那那就是此此時的限限制過于于寬松?！尽凹s制”方法增增添限制制】動態(tài)規(guī)劃算算法講求求拓撲順順序和無無后效性性。然而而現(xiàn)在每每個城市市對負責(zé)責(zé)站的選選取是任任意的，于于是就不不妨對策策略選取取增添限限制———假設(shè)城城市選取取城市的的上消防防站作為為負責(zé)站站，令到到的路徑徑為………，那么么對于任任意都有有的負責(zé)責(zé)站為。如如果我們們證明總總是在一一個最優(yōu)優(yōu)解滿足足上述的的性質(zhì)，那那么此限限制就能能被增添添了。下下面將證證明必有有一個最最優(yōu)解滿滿足上述述的性質(zhì)質(zhì)。證明：令某個最優(yōu)優(yōu)解對應(yīng)應(yīng)的011序列為為。構(gòu)造：在001序列列的布局局下，首首先增加加一個結(jié)結(jié)點，在在和有消消防站的的結(jié)點之之間連一一條權(quán)值值為0的的邊。然然后以為為源點做做一次DDijkkstrra，并并記錄下下前驅(qū)結(jié)結(jié)點。對對于每個個結(jié)點，如如果結(jié)點點有消防防站則選選擇其上上的消防防站為負負責(zé)站，否否則選擇擇前驅(qū)的的負責(zé)站站為其負負責(zé)站。滿足上述性性質(zhì)和必必要限制制：設(shè)任意一個個結(jié)點到到源點的的路徑為為……,易易知任意意都有為的前驅(qū)驅(qū)，而的的負責(zé)站站為的負負責(zé)站為為……的負負責(zé)站為為，所以以任意都都有的負負責(zé)站為為。由于每個結(jié)結(jié)點都選選擇最近近的消防防站，所所以它與與負責(zé)站站的距離離不超過過。而構(gòu)造選取取的消防防站與最最優(yōu)解是是一樣的的，所以以總費用用是最少少的。綜上所述，總總是在一一個最優(yōu)優(yōu)解(構(gòu)構(gòu)造出來來的方案案)滿足足上述的的性質(zhì)。證畢。如今，上述述的限制制終于可可以被正正確地增增添上了了?！敬_定動態(tài)態(tài)規(guī)劃轉(zhuǎn)轉(zhuǎn)移方程程】經(jīng)過兩番轉(zhuǎn)轉(zhuǎn)化后，動動態(tài)規(guī)劃劃轉(zhuǎn)移方方程已經(jīng)經(jīng)可以被被確定下下來了。為為了轉(zhuǎn)移移方便，先先定義一一個簡單單的輔助助狀態(tài)，表示在在以為根根的子樹樹中，修修建合符符要求((子樹中中所有結(jié)結(jié)點到其其樹內(nèi)的的負責(zé)站站的距離離不超過過其對應(yīng)應(yīng)的函數(shù)數(shù)D值))的消防防站的最最小費用用。明顯顯地下面對進行行分析：：①當(dāng)時，∞∞，這表表示不存存在狀態(tài)態(tài)；②當(dāng)時，⑴當(dāng)在以為為根的子子樹外時時，對于于的每個個兒子都都有兩種種選擇：：選擇以以為根的的子樹內(nèi)內(nèi)或外的的消防站站為負責(zé)責(zé)站。當(dāng)當(dāng)選擇以以為根的的子樹內(nèi)內(nèi)的消防防站為負負責(zé)站時時，其子子樹所需需的最少少費用為為，當(dāng)選選擇以為為根的子子樹外的的消防站站為負責(zé)責(zé)站時，根根據(jù)新添添的限制制易知只只可以選選擇上的的消防站站作為負負責(zé)站，此此時其子子樹所需需的最少少費用為為。綜上上得到⑵當(dāng)時，的的每個兒兒子的選選擇情況況與⑴中的一一樣。此此時還要要加上修修建上的的消防站站的費用用。因此此⑶當(dāng)并且在在以為根根的子樹樹內(nèi)時，此此時必定定在的某某個兒子子的子樹樹里。對對于的每每個不是是的兒子子其選擇擇情況與與⑴中的一一樣，而而對于，根根據(jù)新添添的限制制它只能能選擇作作為負責(zé)責(zé)站。綜綜上得到到復(fù)雜度分析析：時間間復(fù)雜度度為,空空間復(fù)雜雜度為?！拘〗Y(jié)】“放寬”方方法和“約制”方法不不總是互互相排斥斥、矛盾盾的，它它們往往往會互相相補充。它它們各自自可以在在需要它它們的方方面發(fā)