消防站解题报告

消防站解题报告广东中山纪念中学陈启峰【问题描述】Z国有n个城市，从1到n给这些城市编号。城市之间连着高速公路，并且每两个城市之间有且只有一条通路。不同的高速公路可能有不同的长度。最近Z国经常发生火灾，所以当地政府决定在某些城市修建一些消防站。在城市k修建一个消防站须要花费大小为)(kW的费用。函数W对于不同的城市可能有不同的取值。如果在城市k没有消防站，那么它到离它最近的消防站的距离不能超过)(kD。每个城市在不超过距离这个城市）(D的前提下，必须选择最近的消防站作为负责站。函数D对于不同的城市可能有不同的取值。为了节省钱，当地政府希望你用最少的总费用修建一些消防站，并且使得这些消防站满足上述的要求。【问题分析】【数学模型】首先，以n个城市为结点、高速公路为边，高速公路长为边权构造成一个图。由性质“每两个城市之间有且只有一条通路”可知这个图是一棵树。令),(jidis为结点i和结点j之间的距离。任务是找出一个01序列nXXXX......,,321，使得对于ni1,都有)(}1|),(min{iDXjidisj并且使得目标函数niiiWXZ1)(最小化。【算法模型分析】由于这题涉及到距离和图论等方面，便可猜想这是一道用图论算法解决的问题。可是在尝试过许多图论算法之后却发现这种猜想是走不通的。这时就要充分地利用问题的特殊性。我们知道这图是一棵树，并且这题是求目标函数最小化的问题。根据这些特性，我们基本上可以肯定这题的算法是树型动态规划。【确定动态规划时的矛盾】用动态规划算法解题首先要做的是确定好状态，这应该是不容置疑的，因为状态表示是动态规划中的重中之重。一般地，树型动态规划的状态中会有一个参数Root,Root表示此状态的研究对象是以Root为根的子树。但是，如果仅用RootF表示在以Root为根的子树中，修建符合要求(子树中的所有结点到最近消防站的距离不超过其对应的函数D值)的消防站的最小费用——即状态只用上述的一个参数，那么状态转移方程是无法找到的。因为这种状态表示无法反映出在哪里修建了消防站、离Root最近的消防站的详细情况。为了解决这种情况，我们通常会增加一个参数，可称作增加一维。这时应该增加的参数既可以是Root到最近消防站的距离，又可以是Root的最近消防站的编号，也可以是树内的最近消防站的编号，同样可以是树外的最近消防站的编号。到底更加哪个参数是可行的呢？可是事与愿违！所有的这些状态表示都无法找到动态规划转移方程。难道状态还要增加一个参数吗？还是这题本身是NP完全性问题、而不是用动态规划题目？别急，先来做个分析吧。【初步分析】分析上面找不到状态转移方程的原因。在分析中便会发现产生这些矛盾的主要原因是，在状态转移时不能保证Root到最近消防站的距离或编号与定义的一致——换句话说，就是状态的定义太严格了——再换句话说，题目的要求太严格了。所以，此时当务之急是放宽题目的要求。【“放宽”方法转化限制】现在面对的主要障碍无疑是，“每个城市在不超过距离这个城市）(D的前提下，必须选择最近的消防站作为负责站”这一严格限制在状态转移中起着干扰作用。其实，我们并不须要知道最近的消防站是哪个，而只要保证在距离这个城市）(D内至少有一个消防站就足够了。于是可以尝试放宽这个限制：把这个限制转化为“每个城市在不超过距离这个城市）(D的前提下，可以选择任意一个消防站作为负责站”。转化后，求出的最优解与转化前的是一样的。原因在于在转化后，必定存在一个最优解满足性质“每个城市在不超过距离这个城市）(D的前提下，必须选择最近的消防站作为负责站”。现在每个城市都享有一定的“自由权”了，可以在自己的活动范围内自由地选择消防站作为负责站。此时就有必要把状态表示重新定义一下——令jiF,表示①在以i为根的子树里修建一些消防站；②在结点j必须修建一个消防站；③以i为根的子树内的每个结点在不超过距离这个结点）(D的前提下,选择一个在子树内或结点j上的消防站作为负责站；④结点i必须选择结点j上的消防站作为负责站；的最少总费用（如果j在树外则不算在jiF,内）。自然而然地“最近的消防站”这几个字在定义中消失了，这为以后确定动态规划转移方程提供了很大的方便。【进一步分析】经过“放宽”方法放宽限制后，状态表示基本上已经定下来了。进而要做的是确定动态规划转移方程。但是此时要确定下转移方程还是遇到了一点困难，总觉得欠缺一些性质、关系之类的。相信聪明的读者已经挖掘出原因了，那就是此时的限制过于宽松。【“约制”方法增添限制】动态规划算法讲求拓扑顺序和无后效性。然而现在每个城市对负责站的选取是任意的，于是就不妨对策略选取增添限制——假设城市1P选取城市mP的上消防站作为负责站，令1P到mP的路径为1P2P3P……mP，那么对于任意],1[mi都有iP的负责站为mP。如果我们证明总是在一个最优解满足上述的性质，那么此限制就能被增添了。下面将证明必有一个最优解满足上述的性质。证明：令某个最优解对应的01序列为nXXXX......,,321。构造：在01序列nXXXX......,,321的布局下，首先增加一个结点s，在s和有消防站的结点之间连一条权值为0的边。然后以s为源点做一次Dijkstra，并记录下前驱结点。对于每个结点，如果结点有消防站则选择其上的消防站为负责站，否则选择前驱的负责站为其负责站。满足上述性质和必要限制：1、设任意一个结点到源点的路径为1P2P3P……mPs,易知任意],2[mi都有iP为1iP的前驱，而mP的负责站为mP1mP的负责站为mP……1P的负责站为mP，所以任意],1[mi都有iP的负责站为mP。2、由于每个结点都选择最近的消防站，所以它与负责站的距离不超过这个结点）(D。3、而构造选取的消防站与最优解是一样的，所以总费用是最少的。综上所述，总是在一个最优解(构造出来的方案)满足上述的性质。证毕。如今，上述的限制终于可以被正确地增添上了。【确定动态规划转移方程】经过两番转化后，动态规划转移方程已经可以被确定下来了。为了转移方便，先定义一个简单的辅助状态Best，iBest表示在以i为根的子树中，修建合符要求(子树中所有结点到其树内的负责站的距离不超过其对应的函数D值)的消防站的最小费用。明显地}|min{,为根的子树中在以ijFBestjii下面对F进行分析：①当)(),(iDjidis时，jiF,∞，这表示不存在状态jiF,；②当)(),(iDjidis时，⑴当j在以i为根的子树外时，对于i的每个儿子k都有两种选择：选择以k为根的子树内或外的消防站为负责站。当选择以k为根的子树内的消防站为负责站时，其子树所需的最少费用为kBest，当选择以k为根的子树外的消防站为负责站时，根据新添的限制易知k只可以选择j上的消防站作为负责站，此时其子树所需的最少费用为jkF,。综上得到的儿子为ikjkkjiFBestF},min{,,⑵当ji时，i的每个儿子的选择情况与⑴中的一样。此时还要加上修建j上的消防站的费用。因此的儿子为ikjkkjiFBestjWF},min{)(,,⑶当ji并且j在以i为根的子树内时，此时j必定在i的某个儿子child的子树里。对于i的每个不是child的儿子其选择情况与⑴中的一样，而对于child，根据新添的限制它只能选择j作为负责站。综上得到childkikjkkjchildjiFBestFF并且的儿子为},min{,,,复杂度分析：时间复杂度为)(2nO,空间复杂度为)(2nO。【小结】“放宽”方法和“约制”方法不总是互相排斥、矛盾的，它们往往会互相补充。它们各自可以在需要它们的方面发挥特长——应用“放宽”方法确定状态;应用“约制”方法确定状态转移方程。在保证能找到答案的前提下，对于过于严格而阻挠前进的条件、限制，我们对它进行“放宽”；对于过于宽松而茫无头绪的条件、限制，我们对它进行“约制”——这就是所谓的一张一弛了。一张一弛不仅是文武之道，更是解题之道。