《国家集训队2006论文集陈启峰》由会员分享，可在线阅读，更多相关《国家集训队2006论文集陈启峰（41页珍藏版）》请在金锄头文库上搜索。
1、“约制、放宽”方法在解题中的应用广东省中山纪念中学 陈启峰“约制、放宽”方法的简单定义l“约制”方法添增一些约束的 条件、限制，并保证在这些条件 和限制下依然能找到解。“约制、放宽”方法的简单定义l“放宽”方法减除、放宽一些 条件、限制，并保证在这些条件 和限制下依然能找到解。引言l 在分析问题、设计算法时，我们 常常觉得条件、限制过于繁杂 过于严格过于宽松 过于独立“约制”方法“放宽”方法加强 联系简化 关系例题消防站（POJ2152）LTC国有n个城市。城市间连 着公路。每两个城市间有且只有 一条通路。由于常发生火灾， LTC决定在某些城市建消防站。 在城市k建一个消防站需要W(k) 的费
2、用。每个城市k在距离D(k)范 围内,必须选择最近的消防站作为 负责站。LTC想用最少的费用来 满足以上要求。(W:2;D:3) (W:2;D:1) (W:2;D:1) (W:2;D:1)333 (W:2:D:3) (W:2;D:3) (W:2;D:3) (W:2;D:3)333最少费用=6最少费用=2数学模型l以城市为结点,公路为边, 路长为 边权构树。令dis(i,j)为结点i、j 间的距离。任务是建一些消防 站，使得任意结点i,都有 并得使得目标函数最小化。算法模型分析 l搜索?l图论算法？l树型动态规划?Time Limit Exceed想不到好算法尝试与探索l首先,确定状态。一般地，
3、状态有参数Root表示研究对象为Root的子树。l如果只用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)=2Best2,Best3已定,求Best1有两种情况尝试与探索l为了解决这种情况，我们通常 会增加一个参数最近消防站的距离或编号？树内或外的最近消防站的编号 ？ 难以找到好的转移方程!初步分析 l在分析中发现：在状态转移时，难以保证最近消 防站的距离或编号与定义的一致换
4、句话说，就是状态定义太 严格、题目要求太苛刻。l主要障碍“结点i在D(i)范围内 ,必须选择最近的消防站作为负责 站 ”“放宽”方法 “放宽”方法l其实我们无须知道最近的消防站 在哪，而只要在D范围内有消防 站就行了。限制:“结点i在D(i)范围内,必须选 择最近的消防站作为负责站 ”“结点i在D(i)范围内,可以选择 任意的消防站作为负责站 ”可以放宽为最近消防站 转化 任意消防站“放宽”方法l现在结点享有一定“自由权”了， 此时就有必要定义新状态。“放宽”方法l令 表示1、在i的子树建一些消防站；2、在j上必须建一个消防站；3、i的子树结点选择树内或j上的可选消防站为负责站；4、i必须选择
5、j上消防站为负责站；的最少总费用(j在i的子树外则不算在 内)“放宽”方法 (W:2;D:1) (W:1;D:1) (W:2;D:1) (W:4;D:2)112Best1=2 !求F1,4“放宽”方法(W:100;D:1) (W:1:D:1) (W:1;D:2) (W:1;D:1)111 (W:100;D:3)1求F1,5“放宽”方法l这样定义的好处是， “最近的消 防站”在定义中消失了。l这种自由为转移方程提供了很大 方便。进一步分析 l然而，此时要定下转移方程还是 遇到了一点点困难，总觉得结点 间相对独立。l原因：策略选取的任意性导致“约制”方法l动态规划讲求拓扑顺序和无后效 性。l于是不
6、妨对策略增添限制 令P1到负责站Pm的路径为P1 P2 P3Pm，则任意Pi的负责站 都为Pm。 “约制”方法lP1P2P3P4Pm“约制”方法l下面通过构造证明至少存在一个 最优解满足该性质P1到负责 站Pm的路径P1 P2Pm中任 意Pi的负责站都为Pm。“约制”方法证明：假设某最优解不满足这性质。 构造：增加结点s，在s和有消防 站的结点间连一条权为0的边 。以s为源点做Dijkstra，记 录下前驱结点。如果结点上有消防站则选 择它为负责站，否则选择前 驱结点的负责站为负责站。“约制”方法最小费用=2 (W:1;D:2)1(W:1;D:1)1(W:1;D:2)(W:1;D:1)1s00
7、“约制”方法此方案满足上述性质和必要限制 ： 1、设任意一个结点到源点的最短 路为P1 P2 P3Pm s；即任意Pi的负责站都为Pm。P1Pm-2Pm-1 Pms“约制”方法2、结点都选择最近消防站，所以 到负责站的距离不超过D(这结点)；3、构造选取的消防站与最优解一 样，所以总费用最少。 综上所述，总存在一个最优解(构造出来的方案)满足上述的性质 。l如今这限制可以安全地增添上了。转移方程l首先确定下Best的转移方程l下面对F进行分析：当dis(i,j)D(i)时,令 =+ ，这表示不存在此状态 。当dis(i,j) D(i)时,转移方程(1) 当j在i的子树外时，(2)当i=j时,(
8、3)当j不等于i并且在i的子树内时,令j在i的儿子child的子树内,复杂度分析 l时间复杂度为l空间复杂度为l编程复杂度低小结原始模型“放宽”方法 确定状态确定转移方程“约制”方 法解决问题总结l在应用这两种方法的时候，首先 要摸清这两者的适用范围、所起 的作用和效果。一张一弛作为一种解题方法，是 需要在思索、做题中慢慢形成的 。除了实践外，还有几点是需要 注意的：总结敢于创新敢于猜想敢于类比敢于拓展其中敢于创新显得尤为重要,只有 不断创新和实践，才能“拨得云开 见月明”。E-mail:344368722QQ.com转移方程l当dis(i,j) D(i)时,l (1)当j在i的子树外时，i的
9、儿子k有两个选择：选择k的子树内或外 的消防站为负责站。 返回 当选择树内的为负责站时， 所需的最少费用为 ，当选择树外的为负责站时， 根据新添的限制必须选择j上 的消防站作为负责站。 所需的最少费用为 。j /i/ k转移方程l当dis(i,j) D(i)时,l (2)当i=j时,i的儿子的选择情况与一样。此时还要加上建j上的消防站的费用。 返回 i(i=j )/ k转移方程l当dis(i,j) D(i)时,l (3)当j不等于i并且在i的子树内 时 ,此时j必存在于以i的某个儿 子child为根的子树里 返回 如果i的儿子k不等于child,则 其选择情况与中一样child根据新添的限制它
10、只能 选择j上的消防站作为负责站 ichildjichildji/ k childj时间复杂度分析l对于每一个确定的j,计算Fi,j需 要(i的儿子数)的时间,所以计 算F1, j、F2, j Fn, j 总共需要 O(总儿子数)=O(n)的时间。l因此，总的时间复杂度为一张一弛l 在保证能找到答案 的前提下，对过于宽松而茫无头 绪的条件、限制进行约制;对于过 于严格而阻挠前进的条件、限制 进行放宽。一张一弛不仅是文武之道，也是 解题之道。l能应用“约制”方法的题目:POI2005knightsCEOI锯木厂 高斯消元解多元一次方程l能应用“放宽”方法的题目：WC2005友好的动物l更多精彩内容在“约制、放宽”方法在解题中的应用 .doc
