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

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