1、“ “分层图思想分层图思想”及其及其在信息学竞赛中的应用在信息学竞赛中的应用天津市南开中学 肖天主要内容主要内容n这不是一个算法，而是一个建模思想n通过一个例题介绍该思想，并小结该思想的特点n应用该思想解决另一个例题，得到一个高效算法例例1 1：拯救大兵瑞恩（：拯救大兵瑞恩（CTSC99CTSC99）求从地图左上角到右下角的最少步数入口大兵瑞恩例例1 1：拯救大兵瑞恩：拯救大兵瑞恩（CTSC99CTSC99）几点说明：n地图中共有P种钥匙（门），P 10n同种钥匙（或门）可能有多个问题的简化问题的简化先忽略钥匙和门的问题RescueRescue（CTSC99CTSC99）问题转化为在一个给定隐
2、式图中的最短路问题起点终点BFS !分析分析加入钥匙和门的因素n不能再简单地求最短路，因为通过某些边是有条件的（拿到相应钥匙）n需要考虑钥匙状态： 0：未拿到该钥匙 1：已拿到该钥匙图的分层图的分层G(0, 0)：无钥匙G(1, 0)：已拿到钥匙1G(0, 1)：已拿到钥匙2G(1, 1)：已拿到钥匙1和2起点终点终点终点终点小结：分层图的特点小结：分层图的特点n分层消耗时间少n所有层都极为相似n所有的层是拓扑有序的n问题的规模并没有增大，而数学模型更清晰了例例2 2：迷宫改造（：迷宫改造（Winter Camp99Winter Camp99）有一个N*M的长方形迷宫，其中假定有P个人，他们分
3、别从P个指定的起点出发，要求他们只能向南或向东移动，分别到达P个指定的终点问至少拆掉多少堵墙（这是原问题的一部分）例例2 2：迷宫改造（：迷宫改造（Winter Camp99Winter Camp99）n参数限定 N = M ( 20) 1 P 3 增加起点与终点重合的人使 P = 3解法解法1 1：动态规划：动态规划n以平行于副对角线的斜线划分阶段n状态描述 斜线位置 三个人的位置n细节解法解法1 1：动态规划：动态规划n状态数：O(N4)n每个状态的状态转移方案： 8n时间复杂度：O(N4)n空间复杂度：O(N3)好像大了点儿解法解法1 1：动态规划：动态规划 分析分析仍有冗余计算！如右图
4、：只考虑两次P=1的情况即可n原因 两人之间只在有公共路线时才有关系 其它时候，原则上只需分别考虑的情况被重复计算了挖掘问题特点挖掘问题特点n某人路线的受其他人影响，但是n如果某人与其他人没有公共路线，那么他的路线是最优的当且仅当此路线是他起点与终点之间的最短路n如果某人路线中A点与B点之间的部分与其他人没有公共部分，且该路线是最优的，那么AB段一定是A点与B点之间的最短路挖掘问题特点挖掘问题特点请看下面的示意图最短路最短路拆拆每一段都是最短路试图消除冗余试图消除冗余n的路线是最短路，只需计算一次n通过预处理求出任意两点间的最短路n时间复杂度O(N4)失败继续挖掘问题特点继续挖掘问题特点n两人
5、有时，代价只计算一次n两人路线之并集没有环n三人路线之并集没有环继续挖掘问题特点继续挖掘问题特点n假想有一个人SuperMan要从左上角到右下角，要求是他要走过所有的公共路线n这个SuperMan一定能找到满意的路线，我们称该路线为主路线n反证法：主路线P 3继续挖掘问题特点继续挖掘问题特点n有人可能根本不进入主路线n主路线之外的部分都是最短路，预处理时间复杂度O(N2)主路线求“最短”的主路线解法解法2 2：应用：应用“分层图思想分层图思想”n每个人有三个状态： 0：未进入主路线 1：正在主路线中 2：已离开主路线n换一个角度，主路线对每个人同样有三个状态：0，1，20210012解法解法2
6、 2：应用：应用“分层图思想分层图思想”n将原图复制33=27份，记为G(s1, s2, s3),其中si 0, 1, 2表示第 i 个人的状态n在相邻层的所有对应顶点间加边，权为： 01：从起点到该点的最短路长度 12：从该点到终点的最短路长度0112解法解法2 2：应用：应用“分层图思想分层图思想”n求解以G(0, 0, 0)左上角顶点为起点的单源最短路问题。n终点不是G(2, 2, 2)右下角顶点，而是所有满足si 0, 2的层G(s1, s2, s3)的右下角顶点解法解法2 2：应用：应用“分层图思想分层图思想”)2 , 2 , 2()3()0 , 2 , 2()2()2 , 0 , 2()3()2()0 , 0 , 2() 1 ()2 , 2 , 0()3() 1 ()0 , 2 , 0()2() 1 ()2 , 0 , 0()3()2() 1 ()0 , 0 , 0(mindpdpdppdpdppdppdpppdAns总结总结n干扰因素使问题的模型变得模糊n将干扰因素细化为若干状态分层n将状态联系起来层的连接n找到算法
