分層圖思想及其在信息學競賽中的應用課件

“分層圖思想”及其

在信息學競賽中的應用天津市南開中學

肖天“分層圖思想”及其

在信息學競賽中的應用天津市南開中學1主要內(nèi)容這不是一個算法，而是一個建模思想通過一個例題介紹該思想，并小結該思想的特點應用該思想解決另一個例題，得到一個高效算法主要內(nèi)容這不是一個算法，而是一個建模思想2例1：拯救大兵瑞恩（CTSC’99）求從地圖左上角到右下角的最少步數(shù)入口大兵瑞恩例1：拯救大兵瑞恩（CTSC’99）求從地圖左上角到右下角的3例1：拯救大兵瑞恩（CTSC’99）幾點說明：地圖中共有P種鑰匙（門），P

≤10同種鑰匙（或門）可能有多個例1：拯救大兵瑞恩（CTSC’99）幾點說明：4問題的簡化先忽略鑰匙和門的問題Rescue（CTSC’99）問題轉(zhuǎn)化為在一個給定隱式圖中的最短路問題起點終點BFS!問題的簡化先忽略鑰匙和門的問題Rescue（CTSC’99）5分析加入鑰匙和門的因素不能再簡單地求最短路，因為通過某些邊是有條件的（拿到相應鑰匙）需要考慮鑰匙狀態(tài)：0：未拿到該鑰匙1：已拿到該鑰匙分析加入鑰匙和門的因素6圖的分層G(0,0)：無鑰匙G(1,0)：已拿到鑰匙1G(0,1)：已拿到鑰匙2G(1,1)：已拿到鑰匙1和2起點終點終點終點終點圖的分層G(0,0)：無鑰匙G(1,0)：已拿到鑰匙1G7小結：分層圖的特點分層消耗時間少所有層都極為相似所有的層是拓撲有序的問題的規(guī)模并沒有增大，而數(shù)學模型更清晰了小結：分層圖的特點分層消耗時間少8例2：迷宮改造（WinterCamp’99）有一個N*M的長方形迷宮，其中假定有P個人，他們分別從P個指定的起點出發(fā)，要求他們只能向南或向東移動，分別到達P個指定的終點問至少拆掉多少堵墻（這是原問題的一部分）例2：迷宮改造（WinterCamp’99）有一個N*M的9例2：迷宮改造（WinterCamp’99）參數(shù)限定

N=M(≤20)1≤P≤3

增加起點與終點重合的人使P=3例2：迷宮改造（WinterCamp’99）參數(shù)限定10解法1：動態(tài)規(guī)劃以平行于副對角線的斜線劃分階段狀態(tài)描述斜線位置三個人的位置細節(jié)解法1：動態(tài)規(guī)劃以平行于副對角線的斜線劃分階段11解法1：動態(tài)規(guī)劃狀態(tài)數(shù)：O(N4)每個狀態(tài)的狀態(tài)轉(zhuǎn)移方案：≤8時間復雜度：O(N4)空間復雜度：O(N3)好像大了點兒……解法1：動態(tài)規(guī)劃狀態(tài)數(shù)：O(N4)好像大了點兒……12②①①②解法1：動態(tài)規(guī)劃—分析仍有冗余計算?、佗谌缬覉D：只考慮兩次P=1的情況即可原因兩人之間只在有公共路線時才有關系其它時候，原則上只需分別考慮①①②的情況被重復計算了①①②①①②解法1：動態(tài)規(guī)劃—分析仍有冗余計算?、佗谌缬?3挖掘問題特點某人路線的最優(yōu)性受其他人影響，但是如果某人與其他人沒有公共路線，那么他的路線是最優(yōu)的當且僅當此路線是他起點與終點之間的最短路如果某人路線中A點與B點之間的部分與其他人沒有公共部分，且該路線是最優(yōu)的，那么AB段一定是A點與B點之間的最短路挖掘問題特點某人路線的最優(yōu)性受其他人影響，但是14挖掘問題特點請看下面的示意圖最短路最短路拆每一段都是最短路挖掘問題特點請看下面的示意圖最短路最短路拆每一段都是最短路15試圖消除冗余②的路線是最短路，只需計算一次通過預處理求出任意兩點間的最短路時間復雜度O(N4)①②①②①①失敗試圖消除冗余②的路線是最短路，只需計算一次①②①②①①失敗16繼續(xù)挖掘問題特點兩人有公共路線時，代價只計算一次兩人路線之并集沒有環(huán)三人路線之并集沒有環(huán)繼續(xù)挖掘問題特點兩人有公共路線時，代價只計算一次17繼續(xù)挖掘問題特點假想有一個人SuperMan要從左上角走到右下角，要求是他要走過所有的公共路線這個SuperMan一定能找到滿意的路線，我們稱該路線為主路線反證法：主路線P>3繼續(xù)挖掘問題特點假想有一個人SuperMan要從左上角走到右18繼續(xù)挖掘問題特點有人可能根本不進入主路線主路線之外的部分都是最短路，預處理時間復雜度O(N2)主路線求“最短”的主路線繼續(xù)挖掘問題特點有人可能根本不進入主路線主路線求“最短”的主19解法2：應用“分層圖思想”每個人有三個狀態(tài)：0：未進入主路線1：正在主路線中2：已離開主路線換一個角度，主路線對每個人同樣有三個狀態(tài)：0，1，20210012解法2：應用“分層圖思想”每個人有三個狀態(tài)：01001220解法2：應用“分層圖思想”將原圖復制33=27份，記為G(s1,s2,s3),其中si∈{0,1,2}表示第i

個人的狀態(tài)在相鄰層的所有對應頂點間加邊，權為：0→1：從起點到該點的最短路長度1→2：從該點到終點的最短路長度0→11→2解法2：應用“分層圖思想”將原圖復制33=27份，記為G(s21解法2：應用“分層圖思想”求解以G(0,0,0)左上角頂點為起點的單源最短路問題。終點不是G(2,2,2)右下角頂點，而是所有滿足si∈{0,2}的層G(s1,s2,s3)的右下角頂點解法2：應用“分層圖思想”求解以G(0,0,0)左上角頂22解法2：應用“分層圖思想”解法2：應用“分層圖思想”23總結干擾因素使問題的模型變得模糊將干擾因素細化為若干狀態(tài)——分層將狀態(tài)聯(lián)系起來——層的連接找到算法總結干擾因素使問題的模型變得模糊24謝謝！謝謝！25“分層圖思想”及其

在信息學競賽中的應用天津市南開中學

肖天“分層圖思想”及其

在信息學競賽中的應用天津市南開中學26主要內(nèi)容這不是一個算法，而是一個建模思想通過一個例題介紹該思想，并小結該思想的特點應用該思想解決另一個例題，得到一個高效算法主要內(nèi)容這不是一個算法，而是一個建模思想27例1：拯救大兵瑞恩（CTSC’99）求從地圖左上角到右下角的最少步數(shù)入口大兵瑞恩例1：拯救大兵瑞恩（CTSC’99）求從地圖左上角到右下角的28例1：拯救大兵瑞恩（CTSC’99）幾點說明：地圖中共有P種鑰匙（門），P

≤10同種鑰匙（或門）可能有多個例1：拯救大兵瑞恩（CTSC’99）幾點說明：29問題的簡化先忽略鑰匙和門的問題Rescue（CTSC’99）問題轉(zhuǎn)化為在一個給定隱式圖中的最短路問題起點終點BFS!問題的簡化先忽略鑰匙和門的問題Rescue（CTSC’99）30分析加入鑰匙和門的因素不能再簡單地求最短路，因為通過某些邊是有條件的（拿到相應鑰匙）需要考慮鑰匙狀態(tài)：0：未拿到該鑰匙1：已拿到該鑰匙分析加入鑰匙和門的因素31圖的分層G(0,0)：無鑰匙G(1,0)：已拿到鑰匙1G(0,1)：已拿到鑰匙2G(1,1)：已拿到鑰匙1和2起點終點終點終點終點圖的分層G(0,0)：無鑰匙G(1,0)：已拿到鑰匙1G32小結：分層圖的特點分層消耗時間少所有層都極為相似所有的層是拓撲有序的問題的規(guī)模并沒有增大，而數(shù)學模型更清晰了小結：分層圖的特點分層消耗時間少33例2：迷宮改造（WinterCamp’99）有一個N*M的長方形迷宮，其中假定有P個人，他們分別從P個指定的起點出發(fā)，要求他們只能向南或向東移動，分別到達P個指定的終點問至少拆掉多少堵墻（這是原問題的一部分）例2：迷宮改造（WinterCamp’99）有一個N*M的34例2：迷宮改造（WinterCamp’99）參數(shù)限定

N=M(≤20)1≤P≤3

增加起點與終點重合的人使P=3例2：迷宮改造（WinterCamp’99）參數(shù)限定35解法1：動態(tài)規(guī)劃以平行于副對角線的斜線劃分階段狀態(tài)描述斜線位置三個人的位置細節(jié)解法1：動態(tài)規(guī)劃以平行于副對角線的斜線劃分階段36解法1：動態(tài)規(guī)劃狀態(tài)數(shù)：O(N4)每個狀態(tài)的狀態(tài)轉(zhuǎn)移方案：≤8時間復雜度：O(N4)空間復雜度：O(N3)好像大了點兒……解法1：動態(tài)規(guī)劃狀態(tài)數(shù)：O(N4)好像大了點兒……37②①①②解法1：動態(tài)規(guī)劃—分析仍有冗余計算?、佗谌缬覉D：只考慮兩次P=1的情況即可原因兩人之間只在有公共路線時才有關系其它時候，原則上只需分別考慮①①②的情況被重復計算了①①②①①②解法1：動態(tài)規(guī)劃—分析仍有冗余計算?、佗谌缬?8挖掘問題特點某人路線的最優(yōu)性受其他人影響，但是如果某人與其他人沒有公共路線，那么他的路線是最優(yōu)的當且僅當此路線是他起點與終點之間的最短路如果某人路線中A點與B點之間的部分與其他人沒有公共部分，且該路線是最優(yōu)的，那么AB段一定是A點與B點之間的最短路挖掘問題特點某人路線的最優(yōu)性受其他人影響，但是39挖掘問題特點請看下面的示意圖最短路最短路拆每一段都是最短路挖掘問題特點請看下面的示意圖最短路最短路拆每一段都是最短路40試圖消除冗余②的路線是最短路，只需計算一次通過預處理求出任意兩點間的最短路時間復雜度O(N4)①②①②①①失敗試圖消除冗余②的路線是最短路，只需計算一次①②①②①①失敗41繼續(xù)挖掘問題特點兩人有公共路線時，代價只計算一次兩人路線之并集沒有環(huán)三人路線之并集沒有環(huán)繼續(xù)挖掘問題特點兩人有公共路線時，代價只計算一次42繼續(xù)挖掘問題特點假想有一個人SuperMan要從左上角走到右下角，要求是他要走過所有的公共路線這個SuperMan一定能找到滿意的路線，我們稱該路線為主路線反證法：主路線P>3繼續(xù)挖掘問題特點假想有一個人SuperMan要從左上角走到右43繼續(xù)挖掘問題特點有人可能根本不進入主路線主路線之外的部分都是最短路，預處理時間復雜度O(N2)主路線求“最短”的主路線繼續(xù)挖掘問題特點有人可能根本不進入主路線主路線求“最短”的主44解法2：應用“分層圖思想”每個人有三個狀態(tài)：0：未進入主路線1：正在主路線中2：已離開主路線換一個角度，主路線對每個人同樣有三個狀態(tài)：0，1，20210012解法2：應用“分層圖思想”每個人有三個狀態(tài)：01001245解法2：應用“分層圖思想”將原圖復制33=27份，記為G(s1,s2,s3),其中si∈{0,1,2}表示第i

個人的狀態(tài)在相鄰層的所有對應頂點間加邊，權為：0→1：從起點到該點的最短路長度1→2：從該點到終點的最短路長度0→11→2解法2：應用“分層圖思想”將原圖復制33=27份，記為G(s46解法2：應用“分層圖思想”求解以G(