福州第一中学　　林元

【摘要】

　　这是一道典型的树的最优化问题，使用简单的三阶动态规划算法解决，数据结构使用树转二叉树的偏二叉树表示法，具体实现为双亲、儿子、兄弟表示法。动态规划的第三阶规模为2。

【正文】

〖问题〗

　　求给定的带权树的符合下面条件的子顶点集合V：
　　　1． 若点i∈V，则所有与i相邻的点j可被标号。
　　　2． 任意一个点j，若j不属于V，则j可被标号。
　　　3． S=∑（Weight[i]，i∈V），并且S最小。

〖思路〗

　　考虑到树本身的特性：除了根节点外，每一个节点都仅与该节点的父节点与儿子节点有关系；大多数情况下，每个节点的状况都是由它的儿子节点的状况决定的。这与动态规划的无后效性要求相符，再加上本题求的又是最优方案，这一切都与动态规划算法不谋而合。

〖算法〗

　　初步定下算法方向后，剩下的就是考虑动态规划的最优子结构性质的满足及状态转移方程了。

　　最优子结构性质

　　要求覆盖以节点i为顶点的树的最佳方案Vi，显然只需考虑节点i属于或不属于集合V两种情况，两者择优即可。既Vi=min{Vi1，Vi2}（1表示属于，2表示不属于）

　　若i∈V，则对于i的任一儿子j，也只有属于或不属于集合V两种情况：若j∈V，则问题转化到求Vj1的小一级规模问题，转化成功；若j不属于V，则要不求Vj2，要不就是j不能被j的任意一个儿子标号，则求所有Vk（k为j的儿子），Vi1求好了。

　　否则，i一定要能被i的某个儿子j标号，这时求所有Vj（j为i的儿子）。若所有的j都是j被j的儿子标号时最"省"（即所有Vj= Vj2），那么实际上按这样的方案没有一个j∈V,造成了i不能被标号。所以要找一个"牺牲"最小的i的儿子j，把方案Vj2换成Vj1。这样就求出了"覆盖以节点i为顶点且不包括节点i的最佳节点集Vi2"。

　　状态转移方程

　　通过上面的分析，我们很容易得到下面这组状态转移方程：
　　　　F(i)=min{F(i,1),F(i,2)}
　　　　F(i,1)=Weight(i)+∑min{F(j),∑min{F(k,1),F(k,2)}}
　　　　F(i,2)=∑F(j)；若所有F(j)<F(j,1)，则换取代价最小的F(j,2)
　　　　（以上j为i儿子，k为j儿子）

　　临界条件

　　容易得到：
　　　　F(i)=F(i,1)
　　　　F(i,1)=Weight(i)
　　　　F(i,2)=+∞
　　　　（以上i为叶子节点）

〖数据结构〗

　　考虑到本题是多叉树，且n最大1500，必须使用"树转二叉树"的偏二叉树表示法纪录树。又为写程序的方便，加上了节点的"双亲"属性。最终数据结构为树的儿子、兄弟、双亲表示法。参考的变量说明如下：

const
　max=1500;
type
　Point=record
　　data1,data2,child,brother,parents:integer;
　　end;
var
　a:array[1..max] of Point;

〖程序实现〗

　　参看参考程序： Guard.pas

〖测试点〗

　　1．单节点树
　　2．单链树
　　3．对付贪心算法的数据一
　　所有节点权值都为1，相邻边最多的点不再最佳点集内。
　　4．对付贪心算法的数据二
　　最佳点集并非包含点最少的点集。
　　5．对付贪心算法的数据三
　　不能用几种"估算点代价法"解决的数据。（估算点代价法指通过估算每个节点划入最佳点集的代价择优录取的贪心算法）
　　6．搜索不能出的大数据
　　标准二叉树、三叉树，便于测试数据生成程序的书写。
　　7．保证动态规划的每段代码都能运行到的数据
　　8．能用贪心算法或搜索得分的数据

〖心得体会〗

　　动态规划是解决树的最优化问题时常用的算法，因为树本身的无后效性特性保证了动态规划最优子结构性质的满足。
　　简单三阶动态规划是解决树的最优化问题的叫标准算法，可移植性好，易于分析，编程结构化程度高，可读性好，效率高，易于实现。
　　但要求程序员分析必须严密，论证要简洁、合理。