ImageVerifierCode 换一换
格式:PPT , 页数:25 ,大小:172.50KB ,
文档编号:2973675      下载积分:22 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-2973675.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(三亚风情)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(分层图思想及其在信息学竞赛中的应用课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

分层图思想及其在信息学竞赛中的应用课件.ppt

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找到算法

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|