2022年消防站解题报告.doc

《2022年消防站解题报告.doc》由会员分享，可在线阅读，更多相关《2022年消防站解题报告.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、消防站解题报告广东中山纪念中学 陈启峰【咨询题描绘】Z国有n个城市，从1到n给这些城市编号。城市之间连着高速公路，同时每两个城市之间有且只有一条通路。不同的高速公路可能有不同的长度。最近Z国经常发生火灾，因而当地政府决定在某些城市修建一些消防站。在城市k修建一个消防站需要花费大小为的费用。函数W关于不同的城市可能有不同的取值。假如在城市k没有消防站，那么它到离它最近的消防站的间隔不能超过。每个城市在不超过间隔的前提下，必须选择最近的消防站作为负责站。函数D关于不同的城市可能有不同的取值。为了节约钱，当地政府希望你用最少的总费用修建一些消防站，同时使得这些消防站满足上述的要求。【咨询题分析】【数

2、学模型】首先，以n个城市为结点、高速公路为边，高速公路长为边权构造成一个图。由性质“每两个城市之间有且只有一条通路”可知这个图是一棵树。令为结点和结点之间的间隔。任务是找出一个01序列，使得关于,都有同时使得目的函数最小化。【算法模型分析】由于这题涉及到间隔和图论等方面，便可猜测这是一道用图论算法处理的咨询题。但是在尝试过许多图论算法之后却发觉这种猜测是走不通的。这时就要充分地利用咨询题的特别性。我们明白这图是一棵树，同时这题是求目的函数最小化的咨询题。依照这些特性，我们根本上能够确信这题的算法是树型动态规划。【确定动态规划时的矛盾】用动态规划算法解题首先要做的是确定好状态，这应该是不容置疑的

3、，由于状态表示是动态规划中的重中之重。一般地，树型动态规划的状态中会有一个参数,表示此状态的研究对象是以为根的子树。但是，假如仅用表示在以为根的子树中，修建符合要求(子树中的所有结点到最近消防站的间隔不超过其对应的函数D值)的消防站的最小费用即状态只用上述的一个参数，那么状态转移方程是无法找到的。由于这种状态表示无法反映出在哪里修建了消防站、离最近的消防站的详细情况。为理处理这种情况，我们通常会增加一个参数，可称作增加一维。这时应该增加的参数既能够是到最近消防站的间隔，又能够是的最近消防站的编号，也能够是树内的最近消防站的编号，同样能够是树外的最近消防站的编号。到底更加哪个参数是可行的呢？但是

4、事与愿违！所有的这些状态表示都无法找到动态规划转移方程。难道状态还要增加一个参数吗？依然这题本身是NP完全性咨询题、而不是用动态规划标题？别急，先来做个分析吧。【初步分析】分析上面找不到状态转移方程的缘故。在分析中便会发觉产生这些矛盾的主要缘故是，在状态转移时不能保证到最近消防站的间隔或编号与定义的一致换句话说，确实是状态的定义太严格了再换句话说，标题的要求太严格了。因而，现在当务之急是放宽标题的要求。【“放宽”方法转化限制】 现在面对的主要障碍无疑是，“每个城市在不超过间隔的前提下，必须选择最近的消防站作为负责站”这一严格限制在状态转移中起着干扰作用。事实上，我们并不需要明白最近的消防站是哪

5、个，而只要保证在间隔内至少有一个消防站就足够了。因而能够尝试放宽这个限制：把这个限制转化为“每个城市在不超过间隔的前提下，能够选择任意一个消防站作为负责站”。转化后，求出的最优解与转化前的是一样的。缘故在于在转化后，必定存在一个最优解满足性质“每个城市在不超过间隔的前提下，必须选择最近的消防站作为负责站”。现在每个城市都享有一定的“自由权”了，能够在本人的活动范围内自由地选择消防站作为负责站。现在就有必要把状态表示重新定义一下令表示 在以为根的子树里修建一些消防站； 在结点必须修建一个消防站； 以为根的子树内的每个结点在不超过间隔的前提下,选择一个在子树内或结点上的消防站作为负责站； 结点必须

6、选择结点上的消防站作为负责站；的最少总费用（假如在树外则不算在内）。自然而然地“最近的消防站”这几个字在定义中消失了，这为以后确定动态规划转移方程提供了非常大的方便。【进一步分析】 通过“放宽”方法放宽限制后，状态表示根本上已经定下来了。进而要做的是确定动态规划转移方程。但是现在要确定下转移方程依然遇到了一点困难，总觉得欠缺一些性质、关系之类的。相信聪明的读者已经挖掘出缘故了，那确实是现在的限制过于宽松。【“约制”方法增添限制】动态规划算法讲求拓扑顺序和无后效性。然而现在每个城市对负责站的选取是任意的，因而就不妨对策略选取增添限制假设城市选取城市的上消防站作为负责站，令到的途径为，那么关于任意

7、都有的负责站为。假如我们证明总是在一个最优解满足上述的性质，那么此限制就能被增添了。下面将证明必有一个最优解满足上述的性质。证明：令某个最优解对应的01序列为。构造：在01序列的规划下，首先增加一个结点，在和有消防站的结点之间连一条权值为0的边。然后以为源点做一次Dijkstra，并记录下前驱结点。关于每个结点，假如结点有消防站则选择其上的消防站为负责站，否则选择前驱的负责站为其负责站。满足上述性质和必要限制：1、 设任意一个结点到源点的途径为,易知任意都有为的前驱，而的负责站为的负责站为的负责站为，因而任意都有的负责站为。2、 由于每个结点都选择最近的消防站，因而它与负责站的间隔不超过。3、

8、 而构造选取的消防站与最优解是一样的，因而总费用是最少的。综上所述，总是在一个最优解(构造出来的方案)满足上述的性质。证毕。现在，上述的限制终于能够被正确地增添上了。【确定动态规划转移方程】通过两番转化后，动态规划转移方程已经能够被确定下来了。为了转移方便，先定义一个简单的辅助状态，表示在以为根的子树中，修建合符要求(子树中所有结点到其树内的负责站的间隔不超过其对应的函数D值)的消防站的最小费用。明显地下面对进展分析：当时，这表示不存在状态；当时，当在以为根的子树外时，关于的每个儿子都有两种选择：选择以为根的子树内或外的消防站为负责站。中选择以为根的子树内的消防站为负责站时，其子树所需的最少费

9、用为，中选择以为根的子树外的消防站为负责站时，依照新添的限制易知只能够选择上的消防站作为负责站，现在其子树所需的最少费用为。综上得到当时，的每个儿子的选择情况与中的一样。现在还要加上修建上的消防站的费用。因而当同时在以为根的子树内时，现在必定在的某个儿子的子树里。关于的每个不是的儿子其选择情况与中的一样，而关于，依照新添的限制它只能选择作为负责站。综上得到复杂度分析：时间复杂度为,空间复杂度为。【小结】“放宽”方法和“约制”方法不总是互相排挤、矛盾的，它们往往会互相补充。它们各自能够在需要它们的方面发挥专长应用“放宽”方法确定状态;应用“约制”方法确定状态转移方程。在保证能找到答案的前提下，关于过于严格而阻止前进的条件、限制，我们对它进展“放宽”；关于过于宽松而茫无眉目的条件、限制，我们对它进展“约制”这确实是所谓的一张一弛了。一张一弛不仅是文武之道，更是解题之道。