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