国家集训队2006论文集陈启峰.ppt
《国家集训队2006论文集陈启峰.ppt》由会员分享,可在线阅读,更多相关《国家集训队2006论文集陈启峰.ppt(41页珍藏版)》请在三一文库上搜索。
1、“约制、放宽”方法在解题中的应用 广东省中山纪念中学 陈启峰,一张一弛, 解题之道,“约制、放宽”方法的简单定义,“约制”方法添增一些约束的条件、限制,并保证在这些条件和限制下依然能找到解。,“约制、放宽”方法的简单定义,“放宽”方法减除、放宽一些条件、限制,并保证在这些条件和限制下依然能找到解。,引言,在分析问题、设计算法时,我们常常觉得条件、限制,过于繁杂 过于严格,过于宽松 过于独立,“约制”方法,“放宽”方法,加强联系,简化关系,例题消防站(POJ2152),LTC国有n个城市。城市间连着公路。每两个城市间有且只有一条通路。由于常发生火灾,LTC决定在某些城市建消防站。在城市k建一个消
2、防站需要W(k)的费用。每个城市k在距离D(k)范围内,必须选择最近的消防站作为负责站。LTC想用最少的费用来满足以上要求。,(W:2;D:3), (W:2;D:1), (W:2;D:1), (W:2;D:1),3,3,3, (W:2:D:3), (W:2;D:3), (W:2;D:3), (W:2;D:3),3,3,3,最少费用=6,最少费用=2,数学模型,以城市为结点,公路为边, 路长为边权构树。令dis(i,j)为结点i、j间的距离。任务是建一些消防站,使得任意结点i,都有 并得使得目标函数 最小化。,算法模型分析,搜索? 图论算法? 树型动态规划?,Time Limit Exceed
3、想不到好算法,尝试与探索,首先,确定状态。 一般地,状态有参数Root 表示研究对象为Root的子树。 如果只用Besti表示在i的子树中修 建满足要求的消防站的最少费用,,状态转移方程?,尝试与探索, (W:1;D:1;Best:?), (W:1;D:1;Best:1),1,(W:1;D:1;Best:1),1,第一种情况:消防站在 Best1=D(2)=1,第二种情况:消防站在 Best1=D(1)+D(3)=2,Best2,Best3已定,求Best1,有两种情况,无法找到转移方程,尝试与探索,为了解决这种情况,我们通常会增加一个参数 最近消防站的距离或编号? 树内或外的最近消防站的编号
4、?,难以找到好的转移方程!,初步分析,在分析中发现: 在状态转移时,难以保证最近消防站的距离或编号与定义的一致 换句话说,就是状态定义太严格、题目要求太苛刻。,主要障碍“结点i在D(i)范围内,必须选择最近的消防站作为负责站 ”,“放宽”方法,太严格!,怎么办?,放宽限制!,“放宽”方法,其实我们无须知道最近的消防站在哪,而只要在D范围内有消防站就行了。 限制:“结点i在D(i)范围内,必须选择最近的消防站作为负责站 ”,“结点i在D(i)范围内,可以选择 任意的消防站作为负责站 ”,可以放宽为,最近消防站 转化 任意消防站,SO,“放宽”方法,现在结点享有一定“自由权”了,此时就有必要定义新
5、状态。,“放宽”方法,令 表示 1、在i的子树建一些消防站; 2、在j上必须建一个消防站; 3、i的子树结点选择树内或j上 的可选消防站为负责站; 4、i必须选择j上消防站为负责站; 的最少总费用(j在i的子树外则不算在内),“放宽”方法, (W:2;D:1), (W:1;D:1), (W:2;D:1), (W:4;D:2),1,1,2,Best1=2 !,求F1,4,“放宽”方法,(W:100;D:1), (W:1:D:1), (W:1;D:2), (W:1;D:1),1,1,1, (W:100;D:3),1,求F1,5,“放宽”方法,这样定义的好处是, “最近的消防站”在定义中消失了。 这
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 国家 集训队 2006 论文集 陈启峰
链接地址:https://www.31doc.com/p-2094171.html