动态规划理论(精华)

1、动态规划理论一动态规划的逆向思维法动态规划是一种思维方法，没有统一的、具体的模式。动态规划可以从多方面去考察，不同的方面对动态规划有不同的表述。我们不打算强加一种统一的表述，而是从多个角度对动态规划的思维方法进行讨论，希望大家在思维具体问题时，也能够从多个角度展开，这样收获会更大。逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。如果原问题可以分解成几个本质相同、规模较小的问题，很自然就会联想到从逆向思维的角度寻求问题的解决。你也许会想，这种将大问题分解成小问题的思维不就是分治法吗?动态规划是不是分而治之呢?其实，虽然我们在运用动态规划的逆向思维法和分治法分析问题时，都使用了

2、这种将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解出来的各个子问题的性质不同。分治法要求各个子问题是独立的（ 即不包含公共的子问题） ，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子问题。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立（ 即各子问题可包含公共的子问题） ，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计 算。这就是动态规划高效 的一个原因。动态规划的逆向思维法的要点可归纳为以

3、下三个步骤：(1) 分析最优值的结构，刻画其结构特征；(2) 递归地定义最优值；0(3) 按自底向上或自顶向下记忆化的方式计算最优值。【例题 1】背包问题描述：有一个负重能力为m的背包和n种物品，第i种物品的价值为v,重量为 w。在不超过背包负重能力的前提下选择若干个物品装入背包，使这些的物品的价值之和最大。每种物品可以不选，也可以选择多个。假设每种物品都有足够的数量。分析：从算法的角度看，解决背包问题一种最简单的方法是枚举所有可能的物品的组合方案并计算这个组合方案的价值之和，从中找出价值之和最大的方案。显然，这种靠穷举所有可能方案的方法不是一种有效的算法。但是这个问题可以使用动态规划加以解决

4、。下面我们用动态规划的逆向思维法来分析这个问题。(1) 背包问题最优值的结构动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动态规划的显著特征。对一个负重能力为m的背包，如果我们选择装入一个第i种物品，那么原背包问题就转化为负重能力为 m-w 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来划分状态，令状态变量sk 表示负重能力为k 的背包，那么sm 的值只取决于sk(k &m)的值。因此背包问题具有最优子结构。(2) 递归地定义最

5、优值动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原问题的最优值。对背包问题而言，有状态转移方程：/maxsk-w+v( 其中 1&i&n,且 k-w/0)sk=若 k0 且存在 1&i&n 使 k- w/0, 0 否则。有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack 是输入背包的负重能力k,返回对应的子背包问题的最优值sk：function knapsack(k:integer):integer ；beginknapsack:=0 ；for i:=1 to n doif k-w=0 thenbegint:=knapsack(k-

6、w)+v ；if knapsack t then knapsack:=t ；end;end；上述递归算法在求解过程中反复出现了一个子问题，且对每次重复出现的子问题都要重新解一次，这需要多花费不少时间。下面先考虑一个具体的背包问题。例如，当m=3， n=2， v1=1 ， w1=1 ， v2=2 ， w2=2 ，图 1 示出了由调用knapsack(3) 所产生的递归树，每一个结点上标有参数k 的值，请注意某些数出现了多次。3/21图1例如， knapsack(1) 被引用了两次：在计算knapsack(3) 和 knapsack(2) 中分别被引用；而knapsack(0)更是被引用了三次。如

7、果knapsack(1) 和 knapsack(0) 每次都要被重新计算，则增加的运行时间相当可观。下面，我们来看看动态规划是如何解决这个问题的。(3) 按自顶向下记忆化或自底向上的方式求最优解一般地，如果一个解最优化问题的递归算法经常反复地解重复的子问题，而不是总在产生新的子问题时，我们说该最优化问题包含重迭子问题。这类问题不宜用分治法求解，因为分治法递归的每一步要求产生相异的子问题。在这种情况下，采用动态规划是很合适的，因为该方法对每一个子问题只解一次，然后把解存放在一个表中，以便在解同样的子问题时查阅，充分利用了重迭子问题。一般来说，解决重迭子问题的方式有两种。自顶向下的记忆化方式该方式

8、的程序流程基本按照原问题的递归定义，不同的是，它专门设置了一张表，以记忆在求解过程中得出的所有子问题的解。一个记忆的递归算法为每个子问题的解在表中记录一个表项。初始时每个表项都包含一个特殊值，以示该表项的解有待填入。例如背包问题中：s=-1 ; (0 i m)当在递归算法的执行中第一次遇到一个子问题时( 即 s=-1) ，计算其解并填入表中，以后每遇到该子问题，只要查看表中先前填入的值即可。下面，我们按照自上而下的记忆化方式，写出求背包问题的递归算法。函数memorized_knapsack输入背包的负重能力k,返回背包问题的解sk 。 s 表应设为全局变量，使得函数执行后，传出所有子问题的解

9、 s(0 i =0 then begint:=memorized_knapsack(k-W)+V ；if sk t then sk:=t；end ；end ；memorized_knapsack:=sk ；end；我们在主程序通过调用memorized_knapsack(m)即可获得背包问题的解。显然这种自顶向下记忆化的算法效率比重复解重迭子问题的knapsack 算法要强一些。此外，在程序中加入判别哪些子问题需要求解的语句，只解那些肯定要解的子问题，从而节省了时间。自底向上的方式假设我们要解决在分析函数knapsack 当中提出的那个具体的背包问题。观察一下在调用memorized_knap

10、sack(4) 的过程中，sk 被计算出来的顺序。我们发现，首先是s0 被计算出来，然后是s1 ， s2 ，最后 s3 被计算出来，这与调用的次序正好相反。动态规划的执行方式是自底向上，所有的子问题计算一次，充分利用重迭子问题。因此，我们很自然就想到与这种自底向上的执行方式相应的采用自底向上的方式递推所有子问题的最优值。我们知道，计算负重能力为k 的背包问题的解仅依赖于计算负重能力小于k 的背包问题的解，因此填s表的方式与解决负重能力递增的背包问题相对应：最初设定负重能力为0 的背包问题的解s0=0 。然后依次考虑负重能力为1, 2，m的背包问题的解o每填入一个sk(0 &k&m)时，充分利用

11、所有重迭子问题的解：sk-w(0i 0)下面是按照自底向上方式计算背包问题的算法流程。过程knapsack_order 输入背包的负重能力k， s 表设为全局变量。过程执行后所有子问题的解通过s 表传给主程序。procedure knapsack_order(k:integer);beginfor i:=1 to k do s:=0;for j:=1 to k dofor i:=1 to n doif j-w=0 thenbegint:=sj-w+v;if sj =0 then begint:=sj-w+v;if sj |决策n | f结束状态1 11111图 1 动态规划决策过程示意图(1)

12、 划分阶段：，按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后 的阶段一定要是有序的或者是可排序的，否则问题就无法求解。(2) 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。(3) 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。(4) 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。(5) 程

13、序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据上述动态规划设计的步骤，可得到大体解题框架如图2 所示。图 2 动态规划设计的一般模式上述提供了动态规划方法的一般模式，对于简单的动态规划问题，可以按部就班地进行动态规划的设计。下面，给出一个利用动态规划方法求解的典型例子。【例题6】数字三角形问题。图3 示出了一个数字三角形宝塔。数字三角形中的数字为不超过100 的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。任务一：假设三角形行数0 10,键盘输入一个确定的整数值 M编程确定是否 存在一条路径，使得沿着该路径所经过的数字的总和恰为

14、M若存在则给出所有路径，若不存在，则输出 NO Answer! 字样。任务二：假设三角形行数0 100,编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，任务一中文件第一行是三角形的行数N 和整数值Mo以后的N行分别是从最顶层到最底层的每一层中的数字。任务二中文件数据格式同任务一，只是第一行中没有整数值M在例子中任务二的文件数据表示如下：输入： 5输出：输出路径和最大值或 No Answer! 字样。图 3 数字三角形4 5 2 6 5【分析】对于这一问题，很容易想到用枚举的方法去解决，即列举出所有路径并记录每一条路径所经过的数字

15、总和。然后判断数字总和是否等于给定的整数值M或寻找出最大的数字总和，这一想法很直观，而且对于任务一，由于数字三角形的行数不大 （ =10）,因此其枚举量不是很大，应该能够实现。但对于任务二，如果用枚举的方法，当三角形的行数等于100 时，其枚举量之大是可想而知的，显然，枚举法对于任务二的求解并不适用。其实，只要对对任务二稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该问题是一个典型的多阶段决策最优化的问题。算法设计与 分析如下：对于任务一，合理地确认枚举的方法，可以优化问题的解法。由于

16、从塔顶 到底层每次都只有两种走法，即左或右。设0 表示左，1 表示右，对于层数为N 的数字塔，从顶到底的一种走法可用一个N-1 位的二进制数表示。如例中二进制数字串1011，其对应的路径应该是：8-1-4-6。这样就可以用一个N-l 位的二进制数来模拟走法和确定解的范围。穷举出从0 到 2n-1 个十进制数所对应的 N-1 位二进制串对应的路径中的数字总和，判定其是否等于M而求得问题的解。对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为 n ，则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段第 n-1 阶段中各决策点至始点的最佳路径，最终求

17、出始点到终点的最佳路径。设：fk(Uk)为从第k阶段中的点Uk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大，fk(Uk) 表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设：Uk1为k-1阶段中某点Uk沿左斜线向下的点；Uk2为k-1阶段中某点Uk沿右斜线向下的点；dk(Uk1)为k阶段中Uk1的数字；dk(Uk2)为k阶段中Uk2的数字。因而可写出顺推关系式( 状态转移方程) 为：fk(Uk尸maxfk-1(Uk)+dk(Uk1), fk-1(Uk)+dk(Uk2)(k=1, 2, 3,，n)f0(U0) =0经过一次顺推，便可分别求出由顶至底N

18、个数的 N 条路径，在这N 条路径所经过的N 个数字和中，最大值即为正确答案。四动态规划方法实现的灵活性与技巧性上述例子给出了一般情况下的动态规划思维过程。一些较为简单的问题可以 按部就班 来操作，但大多数的 动态规划 问题，特别是作为信息学竞赛中的 动态规划 问题，考察的知识是多方面的，应用的技巧是灵活多变的。下面给出上述例 5变形的例子。【例题7】花店橱窗布置问题（99IOI试题）。假设以最美观的方式布置花 店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为

19、 的花瓶在最右边，花束可以移动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶 中列的顺序即如果I J，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为 1,秋海 棠的标识数为2,康乃馨的标识数为3,所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必 须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则 多余的花瓶必须空，即每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束 时会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为 0o在上述例子中，花瓶 与花束

20、的不同搭配所具有的 美学值，可以用如下表格表示：IIIIIIIII花瓶1 I花瓶2 |花瓶3 |花瓶4 |花瓶5 |IIIIIIII 杜鹃花 I7 | 23 | -5 | -24 | 16 |IIIIIIII 秋海棠 |5 | 21 | -4 | 10 | 23 |IIIIIIII 康乃馨 | -21 |5 | -4 | -20 | 20 |根据表格，杜鹃花放在花瓶2 中，会显得非常好看，但若放在花瓶4 中则显得很难看。为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1&F& 100

21、, F100, -50看到经过转化后的问题，发现问题与例题6 的数学三角形问题十分相似，数字三角形问题的题意是：给定一个数字三角形，要求编程计算从顶至底的一条路径，使得路径所经过的数字总和最大( 要求每行选且仅选一个数字) 。同时，路径中相邻两行的数字，必须保证下一行数字的列数与上一行数字的列数相等或者等于上一行数字的列数加1上例中已经知道：数字三角形中的经过数字之和最大的最佳路径，路径的每个中间点到最底层的路径必然也是最优的，可以用动态规划方法求解，对于 花店橱窗布置问题经过转化后，也可采取同样的方法得出本题同样符合最优性原理。因此，可以对此题采用动态规划的方法。(2) 对问题原型动态规划方

22、法的修改。 数字三角形 问题的动态规划方法为：已知它是用行数来划分阶段。假设用ai ， j 表示三角形第i 行的第 j 个数字，用p i ， j 表示从最底层到 ai,j 这个数字的最佳路径 ( 路径经过的数字总和最大) 的数字和，易得问题的动态转移方程为：pn+1,j=0(1 i n+1)pi,j=maxpi+1,j,pi+1,j+1+ai,j(1 i i path 。在明确两题的不同之后，就可以对动态规划方程进行修改了。假设用bi ， j 表示美学值表格中第i 行的第 j 个数字，用qi ， j 表示从表格最底层到bi ， j 这个数字的最佳路径( 路径经过的数字总和最大) 的数字和，修改

23、后的动态规划转移方程为：qi,V+1=- 00(1 i F+1)qF ，j=bF ，j(1 jV)qi , j=maxqi+1 , k(jK &V+1)+AI,J(1I F, 1JV)这样，得出的maxq1, k (1 &j &V)就是最大的美学值，算法的时间复杂度为O(FV2)。(3) 对算法时间效率的改进。先来看一下这样两个状态的求解方法：qi,j=maxqi+1 , k (j k V+1)+bi , j (1 i F, 1j V) qi,j+1)=maxqi+1, k (j+1 k V+1)+ai , j+1) (1 i F,1j+1 V)上面两个状态中求maxqi+1 ， k 的过程进

24、行了大量重复的比较。此时对状态的表示稍作修改，用数组 ti , j=maxqi,k(j kV+1)(1 i F;,1&j&V)表示新的状态。经过修改后，因为qi ， j=ti+1 , j+1+ai , j,而 ti , j=maxti , j+1 , qi,j(1&i&F,1jV),所以得出新的状态转移方程：ti,V+1=- oo(1 i f 十 1)tF , j=maxtF , j+1 , bF , j(1 j V)ti,j=maxti , j+1 , ti+1 , j+1+ai , j(1iF, 1j V)这样，得出的最大美学值为t1,1,新算法的时间复杂度为 O(F*V),而 空间复杂度

25、也为O(F*V),完全 可以满足1&F&V bf, jthen tf,j:=tf, j+1 else tf,j:=bf,j; 设定动态规划的初始条件，其中-9999 表示负无穷for i:=f-1 downto 1 dofor j:= v downto 1 do beginti, j:=ti, j+1;if ti+1, j+1 + bi, j ti, j thenti, j:=ti+1, j+1 +bi, j;end; end;procedure print; 将最佳美学效果和对应方案输出到文件var f1: text;i,j,p: integer; 为当前需确定位置的花束编号，p 为第 i

26、束花应插入的花瓶编号的最小值beginassign (f1, st2); rewrite (f1);writeln (f1, t 1, 1);p:=1;for i:=1 to f do begin 用循环依次确定各束花应插入的花瓶j:=p;while ti, j =ti, p do inc (j);write (f1, j-1, ); p:=j;end;writeln (f1);close (f1);end; beginreadp;main;print;end.由此可看出，对于看似复杂的问题，通过转化就可变成简单的经典的动态规划问题。在问题原型的基础上，通过分析新问题与原问题的不同之处，修改状

27、态转移方程，改变问题状态的描述和表示方式，就会降低问题规划和实现的难度，提高算法的效率。由此可见，动态规划问题中具体的规划方法将直接决定解决问题的难易程度和算法的时间与空间效率，而注意在具体的规划过程中的灵活性和技巧性将是动态规划方法提出的更高要求。五应用举例.【例题1】最短路径问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1 所示，试找出从结点A到结点E的最短距离。图 1我们可以用深度优先搜索法来解决此问题，该问题的递归式为其中是与v 相邻的节点的集合，w(v,u) 表示从 v 到 u 的边的长度。具体算法如下：function MinDistance

28、(v):integer;beginif v=E then return 0elsebeginmin:=maxint;for 所有没有访问过的节点i doif v 和 i 相邻 thenbegin标记i 访问过了;t:=v 到 i 的距离 +MinDistance(i);标记i 未访问过;if tw（u,v）+Fk+1v then Fk:=w（u,v）+Fk+1v;end;输出F1A;end【例题 2】生产计划问题工厂生产某种产品，每单位（千件 ）的成本为1（千元 ），每次开工的固定成本为3（ 千元 ） ，工厂每季度的最大生产能力为6（ 千件 ） 。经调查，市场对该产品的需求量第一、二、三、四季

29、度分别为2 ， 3， 2， 4（千件） 。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（ 少付固定成本费） ，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（ 千元 ） 。还规定年初和年末这种产品均无库存。试制订一个生产计划，即安排每个季度的产量，使一年的总费用（ 生产成本和存储费） 最少。这是一个明显的多阶段问题，我们按照计划时间自然划分阶段，状态定义为每阶段开始时的存储量xk，决策为每个阶段的产量uk,记每个阶段的需求量（已知）为dk,则状态转移方程为：设每个阶段开工固定成本费用为 a,生产单位数量产品的成本为b,每阶段单位 数量产品的存储费用为

30、c，阶段指标为阶段的生产成本费用和存储费用之和，即：指标函数Vkn 为 vk 之和，最优值函数fk(xk) 为从第 k 阶段的状态xk 出发到过程终结的最小费用，满足其中允许决策集合Uk由每阶段的最大生产能力决定，设过程终结时允许存储量为x0n+1,则终端条件为：【例题3】 Bitonic 旅行路线问题欧几里德货郎担问题是对平面给定的n 个点确定一条连结各点的、闭合的游历路线问题。图1(a) 给出了七个点问题的解。Bitonic 旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图1 (b)给出了

31、七个点问题的解。图1请设计一种多项式时间的算法，解决Bitonic 旅行路线问题。首先将n个点按X坐标递增的顺序排列成一个序列 L=0显然 Ln 为最右点，L1 为最左点。由于点1 往返经过二次( 出发一次，返回一次) ，因此点1 拆成两个点：L0=L1= 点1。设： Wi,j - 边 的距离；Wi.j -j-i条连续边 , , 的距离和。由点i 至点 j 的连续边组 成的路径称为连续路径； d - 从点 i 出发由左至右直到n 点后再由右至左到达点i-1 的最短距离。d的递归式如下: 我们专门设置了一张记忆表k(1 i n),记下使得d最小的J值。显然递归式的边界 dn=Wn,n-1 ， k

32、n=n 。由 d 的递归式和记忆表k 的定义可以看出，在由点i-1 至点 i 的最短路上，点i 至 k 的子路径上的点序号是遂一递增的，为由左至右方向上的连续子路径。按照递归定义，若 kwN且kk+1 wN,则点 kk+1+1 至点kkk+1+1 也是由左至右方向上的连续子路径；否则kk+1 至 k+1 为由右至左方向上的连续子路径，该子路径上的点序号是遂一递减的。显然要使d最小，必须分别使di+1 dn-1,dn 最小,d包含了di+1 din最小的子问题，因此该问题具有最优子结构和重叠子问题性质，满足动态规划法适用的条件。为了提高算法效率，我们从dn 出发，运用动态规划方法依次求dn-1,

33、dn- 2,d1,充分利用重叠子问题。最后求得的d1 便是最短 是最短游历路线的距离；从点1 出发，顺着记忆表k 的指示可以递归递输出这条游历路线。【例题4】皇宫看守SGOI2001第二次竞赛试题第4题，中国教育曙光网举办问题描述太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

34、数据输入：输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树，描述如下：第 1 行 n ，表示树中结点的数目。第 2 行至第 n+1 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i(0viv=n),在该宫殿安置侍卫所需的经费k,该边的儿子数mi接下来m个数，分别是这个节点的 m个儿子 的标号 r1 ， r2， . ， rm。对于一个n( 0 n = 1500 )个结点的树，结点标号在1 到 n 之间，且标号不重复。数据输出：输出到OUTPUT.TXT件中。输出文件仅包含一个数，为所求的最少的经费。如左图的输入数据示例输出数据示例在下面我们用根结点的标号来表示一

35、棵树，树T 就是根结点标号为T 的树。设f(T,0)表示对于一棵树T,不在T的树根上布置守卫的情况下，监控 T的全部节点所需的最少的费用；设f(T,1)表示对于一棵树T,不在T的树根上布置守卫的情况下，监控除了T 的根结点以外的其他全部节点所需的最少的费用，当然也可以监控住T 的根结点，不过不是强行要求的；设f(T,2)表示对于一棵树T,在T的树根上布置守卫的情况下，监控 T的全部节点所需的最少的费用；假设T的儿子节点为T1,T2,Tn；则我们可以得到递归公式：( 1)( 2)( 3)下面说明上面的三个公式的含义。如果 T 的根不布置守卫，并且要求监控T 的所有结点，则必须保证T 的子结点中有一个结点Tk 的根上布置了一个守卫，这样在Tk 的根上的守卫可以同时看守T 的根。至于T 的其他子结点(i=1,2,.n,iwk),可以在树根上布置守卫，也可以不布置，但是必须监控住自己所有的结点(因为T 的根上没有守卫)，因此选择最优的方案minf(Ti,0),f(Ti,2)。这样就得到了(1)式；如果 T 的根不布置守卫，并且要求监控除了T 的根结点以外的其他全部节点，则必须保证T 的所有的子结点Ti 都被监控，