




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、淺談最短徑路問(wèn)題中的分層思想,福建省泉州市第七中學(xué) 呂子鉷,引言,最短路徑問(wèn)題,分層思想,城市規(guī)劃 交通導(dǎo)航 網(wǎng)絡(luò)尋優(yōu) ,動(dòng)態(tài)規(guī)劃中的階段劃分 基于求阻塞流的最大流算法 ,強(qiáng)強(qiáng)聯(lián)合,主要內(nèi)容,利用分層思想建立模型 拯救大兵瑞恩 fence cow relay,應(yīng)用分層思想優(yōu)化算法 bic roads,例題一 拯救大兵瑞恩 (CTSC99),有一個(gè)長(zhǎng)方形的迷宮,被分成了N行M列,共NM個(gè)單元。 南北或東西方向相鄰的兩個(gè)單元之間可以互通,或者存在一扇鎖著的門(mén),又或者存在一堵不可逾越的墻。 迷宮中有一些單元存放著鑰匙,總共有P類(lèi)鑰匙,對(duì)應(yīng)P類(lèi)門(mén)。只有對(duì)應(yīng)的鑰匙才能打開(kāi)對(duì)應(yīng)的門(mén)。,例題一 拯救大兵瑞恩
2、 (CTSC99),從一個(gè)單元移動(dòng)到另一個(gè)相鄰單元的時(shí)間為1,拿取所在單元的鑰匙的時(shí)間以及用鑰匙開(kāi)門(mén)的時(shí)間忽略不計(jì)。 求從(1,1)到(N,M)的最短時(shí)間。 N,M不大于15,P不大于10。,分析簡(jiǎn)化問(wèn)題,忽略門(mén)和鑰匙。 把每個(gè)單元看成頂點(diǎn),相互連通的單元之間連一條邊權(quán)為1的邊。,分析分層,考慮鑰匙狀態(tài)對(duì)門(mén)的影響。 把圖分成2P層,分別對(duì)應(yīng)持有鑰匙的2P種狀態(tài)。,分析邊(1),根據(jù)鑰匙的狀態(tài)改造每層圖,使相鄰的連通節(jié)點(diǎn)間有長(zhǎng)度為1的邊。,分析邊(2),對(duì)于存有鑰匙的頂點(diǎn),向表示得到鑰匙后鑰匙狀態(tài)的層的對(duì)應(yīng)頂點(diǎn)連一條長(zhǎng)度為0的邊。,分析復(fù)雜度,使用寬度優(yōu)先搜索求最短路。 時(shí)間復(fù)雜度和空間復(fù)雜度均
3、為O(2PNM)。,小結(jié),將圖進(jìn)行分層是因?yàn)樵谕粚訄D上難以準(zhǔn)確地表現(xiàn)出圖在不同條件下的狀況或圖的其他因素。 分層的圖分別表示不同的條件,加強(qiáng)了圖的性質(zhì),使得在分層圖能夠使用基本的最短路算法求解原來(lái)的復(fù)雜問(wèn)題。,例題二 roads (CEOI98),n個(gè)城市有單向道路連接。 每條路有固定的長(zhǎng)度和費(fèi)用。 路徑上的費(fèi)用不大于k。 求從城市1出發(fā)到達(dá)城市n的最短路徑。,例題二 roads (CEOI98),費(fèi)用k是不大于10000的非負(fù)整數(shù) 城市數(shù)n是不大于100的正整數(shù) 道路數(shù)m是不大于10000的正整數(shù) 每條道路的長(zhǎng)度是不大于100的正整數(shù) 每條道路的通行稅是不大于100的非負(fù)整數(shù)。,分析圖,我
4、們把城市看成節(jié)點(diǎn),城市之間的道路看成邊。,本題與一般求最短路的問(wèn)題相比,不同之處在于邊上有費(fèi)用、距離兩個(gè)權(quán)值。,分析算法一分層,把圖拆分成k+1層,表示到達(dá)該層頂點(diǎn)所需的費(fèi)用分別為0到k。,分析算法一邊,每條邊拆成O(k)條邊,邊的兩個(gè)頂點(diǎn)的所在層的費(fèi)用之差表示費(fèi)用,邊的權(quán)值表示道路長(zhǎng)度。,分析算法一復(fù)雜度,由于道路長(zhǎng)度是正整數(shù),采用Dijkstra算法求最短路。 圖是稠密的,優(yōu)先隊(duì)列直接使用一維數(shù)組。 時(shí)間復(fù)雜度為O(k(kn2+m) 。,分析算法二,由于費(fèi)用是非負(fù)的,這意味著邊只能從一個(gè)節(jié)點(diǎn)指向同一層的節(jié)點(diǎn)或費(fèi)用更大的層的節(jié)點(diǎn)。 按照費(fèi)用從低到高的順序?qū)γ繉忧笞疃搪罚且淮涡詫?duì)所有點(diǎn)求最
5、短路。 每一層求最短路的時(shí)間復(fù)雜度為O(n2+m)。 時(shí)間復(fù)雜度降為O(k(n2+m)。,分析算法三,由于題目已經(jīng)給定費(fèi)用的最大值,所以我們很自然地直接以費(fèi)用的多少進(jìn)行分層。 但是我們忽略了一個(gè)條件:道路長(zhǎng)度是正整數(shù),而不僅是非負(fù)整數(shù)。 可以以道路長(zhǎng)度進(jìn)行分層,然后使用動(dòng)態(tài)規(guī)劃。,分析算法三轉(zhuǎn)移方程,令fi,j表示到達(dá)城市j長(zhǎng)度為i的所有路徑所花費(fèi)的最少費(fèi)用。,轉(zhuǎn)移方程為: f0,1=0 f0,j= (j=2 n) fi,j=maxfi-len,j0+fee (城市j0到城市j有一條長(zhǎng)度為len,費(fèi)用為fee的道路),分析算法三復(fù)雜度,設(shè)每條道路長(zhǎng)度的最大值為L(zhǎng)。 那么總共有O(nL)個(gè)階段,每個(gè)階段的轉(zhuǎn)移的復(fù)雜度O(m)。 算法三的時(shí)間復(fù)雜度為O(nLm),效率有所提高。,小結(jié),分層圖的層是我們構(gòu)建模型時(shí)復(fù)制的,許多圖的元素都是相同或相似的,不需要增加額外
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 教育信息化背景下的教師專(zhuān)業(yè)能力提升
- 醫(yī)療心理教育與提高醫(yī)療服務(wù)質(zhì)量的關(guān)系
- 南通職業(yè)大學(xué)《江南絲竹》2023-2024學(xué)年第一學(xué)期期末試卷
- 西藏職業(yè)技術(shù)學(xué)院《賽事模擬對(duì)抗》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣西體育高等專(zhuān)科學(xué)?!队變簣@綜合藝術(shù)活動(dòng)設(shè)計(jì)》2023-2024學(xué)年第一學(xué)期期末試卷
- 浙江長(zhǎng)征職業(yè)技術(shù)學(xué)院《形體與舞蹈(2)》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東警官學(xué)院《生物工藝學(xué)實(shí)驗(yàn)》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024-2025學(xué)年新疆伊寧市第七中學(xué)化學(xué)九年級(jí)第一學(xué)期期末綜合測(cè)試試題含解析
- 2024年遼寧省燈塔市數(shù)學(xué)七上期末學(xué)業(yè)水平測(cè)試試題含解析
- 油田青苗費(fèi)用管理辦法
- 2025年陜西、山西、青海、寧夏高考物理試卷真題(含答案解析)
- 2025年心理咨詢(xún)師資格考試試題及答案
- 2025年 呼倫貝爾農(nóng)墾集團(tuán)公司招聘筆試試卷附答案
- 基礎(chǔ)護(hù)理學(xué)練習(xí)題庫(kù)(含參考答案)
- 內(nèi)蒙古自治區(qū)赤峰市2023-2024學(xué)年高二下學(xué)期7月期末聯(lián)考數(shù)學(xué)試題 含解析
- 2022-2023學(xué)年廣東省廣州市番禺區(qū)四年級(jí)下學(xué)期期末語(yǔ)文真題及答案
- 葉酸培訓(xùn)考試題及答案
- 大慶護(hù)理面試題及答案
- 成人用品的購(gòu)買(mǎi)渠道分析
- 粉店合伙合同協(xié)議書(shū)范本
- 南京師范大學(xué)古代漢語(yǔ)教案
評(píng)論
0/150
提交評(píng)論