算法合集之淺談最短徑路問題中的分層思想(已修改)
2024-10-30 18:37 本頁面
【正文】 淺談最短徑路問題中的分層思想 福建省泉州市第七中學(xué) 呂子鉷 引言 最短路徑問題 分層思想 城市規(guī)劃 交通導(dǎo)航 網(wǎng)絡(luò)尋優(yōu) …… 動態(tài)規(guī)劃中的階段劃分 基于求阻塞流的最大流算法 …… 強(qiáng)強(qiáng)聯(lián)合 主要內(nèi)容 利用分層思想建立模型 拯救大兵瑞恩 fence cow relay 應(yīng)用分層思想優(yōu)化算法 bic roads 例題一 拯救大兵瑞恩 (CTSC99) 有一個長方形的迷宮，被分成了 N行 M列，共 N M個單元。 南北或東西方向相鄰的兩個單元之間可以互通，或者存在一扇鎖著的門，又或者存在一堵不可逾越的墻。 迷宮中有一些單元存放著鑰匙，總共有 P類鑰匙，對應(yīng) P類門。只有對應(yīng)的鑰匙才能打開對應(yīng)的門。 例題一 拯救大兵瑞恩 (CTSC99) 從一個單元移動到另一個相鄰單元的時間為 1，拿取所在單元的鑰匙的時間以及用鑰匙開門的時間忽略不計(jì)。 求從 (1,1)到 (N,M)的最短時間。 N,M不大于 15， P不大于 10。 分析 — 簡化問題 忽略門和鑰
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1