消防站解题报告

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