时间戳

首页 > 解决方案 > 如何修剪这种类型的排序加权树以最大化这个特定的功能？

algorithm - 如何修剪这种类型的排序加权树以最大化这个特定的功能？

问题描述

免责声明 #1：我不是专业人士，所以我的许多命名法可能不是标准或有用的。请容忍我/编辑我。

免责声明＃2：正如标签所暗示的那样，这可能一开始是一个理论问题，但我认为这是一个编程问题，尽管一些理论也很好。

首先，让我描述一下这种类型的排序加权树，现在称为SWR 树。让我们T = (V, E, W, U, m, r)成为一棵 SWR 树。的唯一定义属性T是：

现在，让我描述一下现在称为的函数。将产生如下数字：TF(T)FT

另外，让我描述一下正确的修剪过程T。考虑修剪边缘。当一条边被修剪时，它的子树被删除。不仅如此，它的所有较大的边（及其子树）也被删除（请记住，由于排序，只考虑较大的兄弟边）。因此，剩下的树T'仍然是 SWR 树，并且正确地继承了T. 显然，F(T')变了（甚至U*变f了）。

因此，问题出现了。给定一棵 SWR 树T，如何正确修剪它以获得T'最大值为的 SWR 树F？

免责声明#3：我知道这个问题就像是从天上掉下来的，而且相当混乱。请随时根据需要重新制定它。另外，只是为了制定问题本身让我有点筋疲力尽，所以我还没有办法解决这个问题。

标签： algorithmoptimizationtreemathematical-optimizationgraph-algorithm

解决方案

让我们首先通过删除叶子权重来稍微简化您的问题定义。现在没有一个权重是负数，我们可以在每个叶子下放置一个子节点，并将每个叶子的权重移动到它的新子边缘。

我可以写下一个看起来很紧凑的整数程序来解决这个问题。对于每条边，如果我们保留边e，则变量x[e]为 1，否则为 0。如果变量是其级别上最大同级的最小值，则该变量y[e]为 1 ，否则为 0。e

maximize sum_{e} W(e) y[e]
subject to
for all e, x[e] ∈ {0, 1}
for all e, y[e] ∈ {0, 1}
for all e sibling of e' with W(e) ≤ W(e'), x[e'] − x[e] ≤ 0
for all e parent of e', x[e'] − x[e] ≤ 0
for all levels ℓ, for all e at level ℓ, for all p at level ℓ−1, y[e] + x[p] − sum_{e' child of p with W(e) ≤ W(e')} x[e] ≤ 1
for all levels ℓ, sum_{e at level ℓ} y[e] = 1

前两个约束组强制执行剪枝限制。下一个约束组本质上说，一条边不能是其级别上最大兄弟的最小值，除非其级别上的每个兄弟组都具有至少同样有价值的边或完全消失。最后的约束只需要打破关系。

这个公式可以用整数程序求解器来求解，但我强烈怀疑有一个更有效的算法。

推荐阅读