算法合集之约制放宽方法在解题中的应用.pptx

约制、放宽约制、放宽”方法在解题中的应用方法在解题中的应用广东省中山纪念中学广东省中山纪念中学 陈启峰陈启峰“约制、放宽约制、放宽”方法的简单定义方法的简单定义l“约制约制”方法方法添增添增一些一些约束约束的的条件、限制条件、限制，并，并保证保证在这些条件和在这些条件和限制下依然能限制下依然能找到解找到解。“约制、放宽约制、放宽”方法的简单定义方法的简单定义l“放宽放宽”方法方法减除、放宽减除、放宽一些一些条件、限制条件、限制，并，并保证保证在这些条件和在这些条件和限制下依然能限制下依然能找到解找到解。引言引言l 在分析问题、设计算法时，我们在分析问题、设计算法时，我们常常觉得条件、限制常常觉得条件、限制过于过于繁杂繁杂过于过于严格严格过于过于宽松宽松过于过于独立独立“约制约制”方法方法“放宽放宽”方法方法加强加强联系联系简化简化关系关系例题消防站（POJ2152）LTC国有国有n个城市。城市间连着个城市。城市间连着公路。公路。每两个城市间有且只有一条每两个城市间有且只有一条通路。通路。由于常发生火灾，由于常发生火灾，LTC决定决定在某些城市建消防站。在某些城市建消防站。在城市在城市k建建一个消防站需要一个消防站需要W(k)的费用。每个的费用。每个城市城市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首先首先,确定状态。确定状态。一般地，状态有参数一般地，状态有参数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)=2BestBest2 2,Best,Best3 3已定已定,求求BestBest1 1有两种情况有两种情况尝试与探索尝试与探索l为了解决这种情况，我们通常会为了解决这种情况，我们通常会增加一个参数增加一个参数 最近消防站的距离或编号？最近消防站的距离或编号？树内或外的最近消防站的编号？树内或外的最近消防站的编号？难以找到好的转移方程难以找到好的转移方程!初步分析初步分析 l在分析中发现：在分析中发现：在状态转移时，难以保证最近消防在状态转移时，难以保证最近消防站的距离或编号与定义的一致站的距离或编号与定义的一致 换句话说，就是换句话说，就是状态定义太严状态定义太严格、题目要求太苛刻格、题目要求太苛刻。l主要障碍主要障碍“结点结点i在在D(i)范围内范围内,必须必须选择选择最近的消防站最近的消防站作为负责作为负责站站”“放宽放宽”方法方法“放宽放宽”方法方法l其实我们无须知道最近的消防站在其实我们无须知道最近的消防站在哪，而只要在哪，而只要在D范围内有消防站就范围内有消防站就行了。行了。限制限制:“结点结点i在在D(i)范围内范围内,必须必须选选择择最近的消防站最近的消防站作为负责站作为负责站”“结点结点i在在D(i)范围内范围内,可以选择可以选择任意的消防站任意的消防站作为负责站作为负责站”可以放宽为可以放宽为 最近消防站最近消防站 转化转化 任意消防站任意消防站“放宽放宽”方法方法l现在结点享有一定现在结点享有一定“自由权自由权”了，了，此时就有必要定义新状态。此时就有必要定义新状态。“放宽放宽”方法方法l令令 表示表示 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)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于是不妨对策略增添限制于是不妨对策略增添限制 令令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“约制约制”方法方法此方案满足上述性质和必要限制：此方案满足上述性质和必要限制：1、设任意一个结点到源点的最短、设任意一个结点到源点的最短路为路为P1 P2 P3Pm s；即任意即任意Pi的负责站都为的负责站都为Pm。P1Pm-2Pm1 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时时,(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的儿子的儿子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根据新添的限制它只能根据新添的限制它只能选择选择j上的消防站作为负责站上的消防站作为负责站 i child j i child j i /k child j 时间复杂度分析l对于每一个确定的对于每一个确定的j,计算计算Fi,j需需要要(i的儿子数的儿子数)的时间的时间,所以所以计算计算F1,j、F2,j Fn,j 总共需总共需要要O(总儿子数总儿子数)=O(n)的时间。的时间。l因此，总的时间复杂度为因此，总的时间复杂度为一张一弛一张一弛l 在保证能找到答案在保证能找到答案的前提下，对过于宽松而茫无头绪的前提下，对过于宽松而茫无头绪的条件、限制进行约制的条件、限制进行约制;对于过于对于过于严格而阻挠前进的条件、限制进行严格而阻挠前进的条件、限制进行放宽。放宽。一张一弛不仅是文武之道，也是解一张一弛不仅是文武之道，也是解题之道。题之道。l能应用能应用“约制约制”方法的题目方法的题目:POI2005knights CEOI锯木厂锯木厂高斯消元解多元一次方程高斯消元解多元一次方程l能应用能应用“放宽放宽”方法的题目：方法的题目：WC2005友好的动物友好的动物l更多精彩内容在 “约制、放宽”方法在解题中的应用.doc