第1页共6页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共6页消防站解题报告广东中山纪念中学陈启峰【问题描述】Z国有n个城市，从1到n给这些城市编号。城市之间连着高速公路，并且每两个城市之间有且只有一条通路。不同的高速公路可能有不同的长度。最近Z国经常发生火灾，所以当地政府决定在某些城市修建一些消防站。在城市k修建一个消防站须要花费大小为W(k)的费用。函数W对于不同的城市可能有不同的取值。如果在城市k没有消防站，那么它到离它最近的消防站的距离不能超过D(k)。每个城市在不超过距离D(这个城市）的前提下，必须选择最近的消防站作为负责站。函数D对于不同的城市可能有不同的取值。为了节省钱，当地政府希望你用最少的总费用修建一些消防站，并且使得这些消防站满足上述的要求。【问题分析】【数学模型】首先，以n个城市为结点、高速公路为边，高速公路长为边权构造成一个图。由性质“每两个城市之间有且只有一条通路”可知这个图是一棵树。令dis(i,j)为结点i和结点j之间的距离。任务是找出一个01序列X1,X2,X3......Xn，使得对于1≤i≤n,都有min{dis(i,j)|Xj=1}≤D(i)并且使得目标函数Z=∑i=1nXi×W(i)第2页共6页第1页共6页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共6页最小化。【算法模型分析】由于这题涉及到距离和图论等方面，便可猜想这是一道用图论算法解决的问题。可是在尝试过许多图论算法之后却发现这种猜想是走不通的。这时就要充分地利用问题的特殊性。我们知道这图是一棵树，并且这题是求目标函数最小化的问题。根据这些特性，我们基本上可以肯定这题的算法是树型动态规划。【确定动态规划时的矛盾】用动态规划算法解题首先要做的是确定好状态，这应该是不容置疑的，因为状态表示是动态规划中的重中之重。一般地，树型动态规划的状态中会有一个参数Root,Root表示此状态的研究对象是以Root为根的子树。但是，如果仅用FRoot表示在以Root为根的子树中，修建符合要求(子树中的所有结点到最近消防站的距离不超过其对应的函数D值)的消防站的最小费用——即状态只用上述的一个参数，那么状态转移方程是无法找到的。因为这种状态表示无法反映出在哪里修建了消防站、离Root最近的消防站的详细情况。为了解决这种情况，我们通常会增加一个参数，可称作增加一维。这时应该增加的参数既可以是Root到最近消防站的距离，又可以是Root的最近消防站的编号，也可以是树内的最近消防站的编号，同样可以是树外的最近消防站的编号。到底更加哪个参数是可行的呢？可是事与愿违！所有的这些状态表示都无法找到动态规划转移方程。难道状态还要增加一个参数吗？还是这题本身是NP完全性问题、而不是用动态规划题目？别急，先来做个分析吧。【初步分析】分析上面找不到状态转移方程的原因。在分析中便会发现产生这些矛盾的主要原因是，在状态转移时不能保证Root到最近消防站的距离或编号与定义的一致——换句话说，就是状态的定义太严格了——再换句话说，题目的要求太严格了。第3页共6页第2页共6页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共6页所以，此时当务之急是放宽题目的要求。【“放宽”方法转化限制】现在面对的主要障碍无疑是，“每个城市在不超过距离D(这个城市）的前提下，必须选择最近的消防站作为负责站”这一严格限制在状态转移中起着干扰作用。其实，我们并不须要知道最近的消防站是哪个，而只要保证在距离D(这个城市）内至少有一个消防站就足够了。于是可以尝试放宽这个限制：把这个限制转化为“每个城市在不超过距离D(这个城市）的前提下，可以选择任意一个消防站作为负责站”。转化后，求出的最优解与转化前的是一样的。原因在于在转化后，必定存在一个最优解满足性质“每个城市在不超过距离D(这个城市）的前提下，必须选择最近的消防站作为负责站”。现在每个城市都享有一定的“自由权”了，可以在自己的活动范围内自由地选择消防站作为负责站。此时就有必要把状态表示重新定义一下——令Fi,j表示①在以i为根的子树里修建一些消防站；②在结点j必须修建一个消防站；③以i为根的...
