算法合集之淺談最短徑路問(wèn)題中的分層思想(已修改)
2024-10-30 18:37 本頁(yè)面
【正文】 淺談最短徑路問(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列，共 N M個(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)。 例題一 拯救大兵瑞恩 (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)和鑰
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1