《算法合集之《“约制、放宽”方法在解题中的应用》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《“约制、放宽”方法在解题中的应用》.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,“放宽”方法,这样定义的好处是， “最近的消防站”在定义中消失了。 这
6、种自由为转移方程提供了很大方便。,进一步分析,然而，此时要定下转移方程还是遇到了一点点困难，总觉得结点间相对独立。 原因：策略选取的任意性导致,限制过于宽松,“约制”方法,动态规划讲求拓扑顺序和无后效性。 于是不妨对策略增添限制 令P1到负责站Pm的路径为P1 P2 P3Pm，则任意Pi的负责站都为Pm。,“约制”方法,P1P2P3P4Pm,“约制”方法,下面通过构造证明至少存在一个最优解满足该性质P1到负责站Pm的路径P1 P2Pm中任意Pi的负责站都为Pm。,“约制”方法,证明：假设某最优解不满足这性质。 构造：增加结点s，在s和有消防 站的结点间连一条权为0的边。 以s为源点做Dijks
7、tra，记 录下前驱结点。 如果结点上有消防站则选 择它为负责站，否则选择前 驱结点的负责站为负责站。,“约制”方法,最小费用=2, (W:1;D:2),1,(W:1;D:1),1,(W:1;D:2),(W:1;D:1),1,s,0,0,“约制”方法,此方案满足上述性质和必要限制： 1、设任意一个结点到源点的最短路为P1 P2 P3Pm s； 即任意Pi的负责站都为Pm。,P1Pm-2Pm-1 Pms,“约制”方法,2、结点都选择最近消防站，所以到负责站的距离不超过D(这结点)； 3、构造选取的消防站与最优解一样，所以总费用最少。 综上所述，总存在一个最优解 (构造出来的方案)满足上述的性质。
8、 如今这限制可以安全地增添上了。,转移方程,首先确定下Best的转移方程 下面对F进行分析： 当dis(i,j)D(i)时,令 =+ ， 这表示不存在此状态 。 当dis(i,j) D(i)时,转移方程,(1) 当j在i的子树外时， (2)当i=j时, (3)当j不等于i并且在i的子树内时, 令j在i的儿子child的子树内,复杂度分析,时间复杂度为 空间复杂度为 编程复杂度低,小结,原始模型,“放宽”方法,确定状态,确定转移方程,“约制”方法,解决问题,总结,在应用这两种方法的时候，首先要摸清这两者的适用范围、所起的作用和效果。 一张一弛作为一种解题方法，是需要在思索、做题中慢慢形成的。除了
9、实践外，还有几点是需要注意的：,总结,敢于创新 敢于猜想 敢于类比 敢于拓展 其中敢于创新显得尤为重要,只有不断创新和实践，才能“拨得云开见月明”。,Thank You!,E-mail:344368722QQ.com,转移方程,当dis(i,j) D(i)时, (1)当j在i的子树外时， i的儿子k有两个选择： 选择k的子树内或外 的消防站为负责站。 返回,当选择树内的为负责站时， 所需的最少费用为 ，,当选择树外的为负责站时， 根据新添的限制必须选择j上的消防站作为负责站。 所需的最少费用为 。,j / i / k,转移方程,当dis(i,j) D(i)时, (2)当i=j时, i的儿子的选
10、择情况与 一样。此时还要加上 建j上的消防站的费用。 返回,i(i=j) / k,转移方程,当dis(i,j) D(i)时, (3)当j不等于i并且在i的子树内时 , 此时j必存在于以i的某个儿子 child为根的子树里 返回,如果i的儿子k不等于child,则 其选择情况与中一样,child根据新添的限制它只能 选择j上的消防站作为负责站,i child j,i child j,i / k child j,时间复杂度分析,对于每一个确定的j,计算Fi,j需要(i的儿子数)的时间,所以计算F1, j、F2, j Fn, j 总共需要O(总儿子数)=O(n)的时间。 因此，总的时间复杂度为,一张一弛,在保证能找到答案的前提下，对过于宽松而茫无头绪的条件、限制进行约制;对于过于严格而阻挠前进的条件、限制进行放宽。 一张一弛不仅是文武之道，也是解题之道。,一张一驰,能应用“约制”方法的题目: POI2005knights CEOI锯木厂 高斯消元解多元一次方程 能应用“放宽”方法的题目： WC2005友好的动物,更多精彩内容在 “约制、放宽”方法在解题中的应用.doc,