partialorder

最近陷入了啥时候可以用treedp和树上的贪心的思考

treedp比较清楚,直接从DP的有最优子问题的条件对应过来就可以。那么树上的贪心呢?这里指的是从底往上的一类算法类似tree-dp,但是每个节点不需要保存多个状态,只需要存一个最优值就可以了,子树的最优值就可以计算出父亲的最优值,而不需要枚举子树的可能状态。啥样的问题可以用这样的算法呢?

有一篇paper似乎给出了一类充分(应该不必要)的条件:

如果符合这两点:

1.单调性:如果问题在某个节点为根的子树上的解不是最优,那么父亲节点处的解不会优于最优解。

2.最小化:如果一个算法,对于给定的子树的解,能计算出父亲节点在子树的解确定条件下的最优解。

那么可以在树上进行贪心,每一次使用这个算法向上推进得到全局最优解。

归纳证明:首先叶子节点的最优解通过初始化可得。

对于每一个节点t,假设u和v是两个儿子,且得到了原问题在以u和v为根的子树上的最优解。由于单调性,没有必要枚举其它的解来计算t为根的子树的最优解因为由u和v的其他解得到的t的解不会更优,因此只需要计算出u和v子树最优情况下t的所有可能解中最优的就行了。那么具有最小化性质的算法可以对于任意给定子树的解,求出以t为根的树的最优解,当然也可以求出在u和v子树最优情况下,t的最优解,于是这个最优解就是在所有可能的子树状态中的最优解,即问题在以t为根的子树上的最优解。然后按层归纳可得。

这个证明看起来没有问题,但是我就是很难相信,总想找到反例。因为原论文并不是这么表述的,我整理了一遍之后这两个条件看上去太简单了,如果是对的,那么对一些没有解决的树上的问题影响似乎有点大,因为似乎好多问题都能证明出这两个性质,于是可以找到多项式时间或者常数近似的算法?把现在没有找到的结论推进了一大步,不科学啊。

也许是我在应用这两个条件的时候没有定义清楚,所以其实是不符合这两个性质的?还是这个证明本身有问题?



评论