〖問題12〗歐幾里德貨郎擔(dān)問題和bitonic旅行路線問題

《〖問題12〗歐幾里德貨郎擔(dān)問題和bitonic旅行路線問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、〖問題12〗歐幾里德貨郎擔(dān)問題和Bitonic旅行路線問題——信息學(xué)NOI聯(lián)賽輔導(dǎo)專題NOI競賽輔導(dǎo)王建德教練講稿無后效性即一個問題被劃分階段后，階段I中的狀態(tài)只能由階段I-1中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與其他狀態(tài)沒有關(guān)系，特別是與未發(fā)生的狀態(tài)沒有關(guān)系，這就是無后效性。如果把問題中的狀態(tài)定義成圖中的頂點，兩個狀態(tài)之間的轉(zhuǎn)移定義為邊，轉(zhuǎn)移過程中的權(quán)值增量定義為邊的權(quán)值，則這個問題實際上就是在一個“有向無環(huán)加權(quán)圖”中尋找兩個頂點路徑的問題。因為無后效性，所以沒有環(huán)路（否則，無論如何劃分階段，都可以出現(xiàn)后效性）。即這個圖可以進(jìn)行“拓?fù)渑判颉保梢砸酝負(fù)渑判虻捻樞騽澐蛛A段。

2、〖問題12〗歐幾里德貨郎擔(dān)問題和Bitonic旅行路線問題歐幾里德貨郎擔(dān)問題是對平面給定的n個點確定一條連結(jié)各點的、閉合的游歷路線問題。下圖(a)給出了七個點問題的解。Bitonic旅行路線問題是歐幾里德貨郎擔(dān)問題的簡化，這種旅行路線先從最左邊開始，嚴(yán)格地由左至右到最右邊的點，然后再嚴(yán)格地由右至左到出發(fā)點，求路程最短的路徑長度。下圖（b）給出了七個點問題的解。把兩條路中起始頂點相同的狀態(tài)歸于一個階段，設(shè)為階段[P1,P2]。Bitonic旅行路線問題設(shè)Dis[i，j]—階段（i，j）中i至n和j至n的最短路長和；1.Dis[N,N]←0;{初始化動態(tài)規(guī)劃數(shù)組}2.Fo

3、rI←N-1Downto13.DoDis[I,N]←I點至I+1點的距離+Dis[I+1,N];4.Dis[N,I]←Dis[I,N];5.ForI←N-2Downto16.DoForJ←N-1DowntoI+1{遞推最小值}7.DoIfI+1

4、7}推出；而道路{2—3—6—7，4—5—7}屬于階段[2,4]，可由屬于階段[3,4]的道路{3—6—7，4—5—7}推出。如果以頂點表示階推出關(guān)系表示邊，那么，階段[3,4]與階段[2,4]對應(yīng)的關(guān)系就如圖所示解決“動態(tài)規(guī)劃”問題的基本方法與步驟：1：確定問題的研究對象，即確定狀態(tài)。2：劃分階段，確定階段之間的狀態(tài)轉(zhuǎn)移方程。3：考察此問題現(xiàn)在可否用“動態(tài)規(guī)劃”來解決：①：考察此問題是否具有“最優(yōu)子結(jié)構(gòu)”。②：考察此問題是否為“無后效性”。4：如果發(fā)現(xiàn)此問題目前不能用“動態(tài)規(guī)劃”來解決，則應(yīng)該調(diào)整相應(yīng)的定義與劃分，以達(dá)到可以用“動態(tài)規(guī)劃”來解決。