主页 / 问题 / 652194
Accepted
LmTinyToon
Asked:2020-04-11 15:36:21 +0000 UTC2020-04-11 15:36:21 +0000 UTC

将树拆分为连接组件的算法

  • 772

有一棵树，每个顶点都有自己的权值，你需要把树分成三个连通的分量，每个分量中所有顶点的总权值是相同的。

应该使用什么算法？

到目前为止，我看到了这样一个解决方案——枚举所有边对，然后进行检查——但就性能而言，这是一个困难的决定。

алгоритм

2 个回答

  1. 这个问题乍一看似乎很复杂正面算法的复杂性（N 是顶点数），但可以在多项式时间内更容易、更快地解决。为什么会这样，我想在下面描述。

    首先，明显的枚举算法适用于任意图（也许有优化并且可以更快地解决）。我们的图表非常具体。它比一般情况下的要简单得多。例如，这种简单性表现为没有循环。

    其次，我们需要将图拆分为仅 3 个连接的组件。

    现在让我们讨论一下：如何将图形分解为连接的组件。我们会立即说，划分成连通分量是去除一些边。我将举一个将下图拆分为连接组件的示例：

    源图

    我们得到 2 个连接的组件：

    2 个连接组件 -- 1

    我们得到 3 个连接的组件：

    3 个连接组件 -- 1

    另一个例子。我们得到 2 个连接组件（顶点 1 被顶点 15 替换）：

    2 连接组件 -- 2

    我们得到 3 个连接的组件：

    3 连接组件 -- 2

    如您所见，总是在删除1 条边时，会出现另一个连接组件。这很容易证明。但是，我们不要下载文本。因此，我们需要删除2 条边，以便我们有3 个连通分量。

    让我们重新表述一下这个问题。我们需要在边缘放置 2 个标签，以便每个组件具有相同的总重量。为此需要做什么？明显地！遍历所有对边。为此，我们将它们编号为0到N-1。让我们遍历所有的边对。对于每一对，我们将检查分区是否正确。让我们写伪代码：

    # Перебираем все рёбра
for i in range edge:
    for j in range edge:
       # Если разбиение делит наше дерево на равные по весу части, то заканчиваем выполнение
       if Splitting(i, j):
           break

    显然，这种算法的复杂度是多项式的

    O(N^2 * g(N)),

    其中g(n)是运行时间Splitting。

    但是函数Splitting(i, j)呢？显然，它Splitting(i, j)可以在线性时间内工作。让我们从每个顶点开始深度优先搜索，如果我们已经到过某个顶点，那么我们就不会再去那里。结果证明我们只绕过所有山峰一次。那些。我们已经遍历了每个连接的组件一次。在这种情况下，渐近运行时间将为O(N) 复杂度，但实际上为2N。在DFS（深度优先搜索）中，我们将计算每个连接组件的权重。

    运行时间Splitting可以改进如下。我们来算一算。对于每条边，我们将存储 2 个参数：边上方顶点的总权重和边下方的总权重。让我们举个例子：

    聚类示例

    那些。对于连接顶点15（又名 1，见上文）和3的边，我们可以计算每个簇中的总权重。我们将按以下方式进行。运行树的 LR 遍历并针对每条边（我注意到边可以与相应的顶点关联。例如，边(11, 10)与顶点11关联，边(6, 2)与顶点 6 关联等等。此外，我们将讨论顶点，而不是边）。

    让我们演示一个示例绕过：

    0 - 10 - 11 - 12 - 13 - 15 (1) - 3 - 4 - 5 - 9 - 2 - 6 - 7 - 8

    在遍历的时候，我们会总结考虑子树的权重。子树的权重是指所有顶点的总和。假设在第i步我们已经计算了以顶点v为根的子树的权重。那么我们需要再往上一层计算更高一层子树的权重。我们用下图来说明。

    子树权重计算示意图

    假设我们在顶点11处。而对于这个顶点的子树，我们已经计算了权重（在图中它显示为叶子，但我们假设它有一个子树）。然后我们需要到节点10，计算节点 10 的子树的权重。为了遍历LR，访问并计算以顶点12、13为根的子树的权值。那么以顶点10为根的子树的权重将是子树11、12、13的权重之和：

    示例递归计算子树权重的公式

    我们有通用公式：

    一般情况下递归计算子树权值的公式

    对于顶点v，表示其上方树的权重：

    高于顶部的树重

    在它下面：

    低于顶部的树重

    现在，我们需要类似地为每个顶点计算其上方树的权重。为此，我们假设根顶点之上没有任何东西。然后再次运行LR遍历（修改）。修改将在于我们将在下降期间执行所有操作。

    显然，这个计算上述特征的算法会及时起作用渐近线。

    因此，对于每个顶点，我们都有它下面的树的权重和它上面的树的权重。

    现在我们需要学习如何快速找出给定的顶点v是否位于另一个顶点u的子树中。先介绍一个函数：

    功能

    为了快速计算它，我们需要额外的技巧。还有一个猜测。

    • 4
  2. Best Answer

    很明显，必须恰好移除两条边才能完成分割。同样清楚的是，每个组件都是一棵树。事先也清楚三个子树中每个顶点的总权重是多少。让它成为 S目标。

    让我们将树的任何顶点表示为根，然后考虑有根树。

    • 我们将通过从下到上、从叶到根生长（并加入）一组子树来构建我们的连接组件。我们从一组起始子树开始，每个子树都由树的一个叶节点组成。

    • 如果在构建过程中的某个时刻，我们找到了目标总和为 S 的子树 T ，则存在包含子树 T 的解（如果问题有解）。所有其他分区变体只能“增加”带有附加顶点的 T，其总权重等于零。我们将总和 S 的子树称为target completed。

    • 考虑一个不完整的子树 T，其根节​​点是 P 的子节点。显然 P 必须与 T 属于同一个连通分量。

    • 从最后一个陈述可以直接得出，如果我们有几个不完整的子树，其根节点是同一祖先 P 的儿子，那么它们必须都包含在同一个连接组件中，也包括 P。

    这自动暗示问题的解决方案相当简单：

    1. 我们从一组起始子树 T 开始，每个子树都由树的一个叶节点组成。
    2. 循环遍历当前的一组子树 T，直到我们只剩下一个子树：
    3.     如果某个子树的总权重严格等于 S target（一个完整的子树），那么我们将其视为结果的一部分并将其排除在进一步考虑之外（我们将其从 T 中排除并有条件地将其从源树中排除）。
    4.     如果在这样的消除过程中，源树的某个节点变成了叶节点，那么我们将它作为单独的子树添加到 T 中。
    5.     如果我们在 T 中有所有不完整的子树，其根是某个顶点 P 的儿子，那么我们将它们组合成一个以 P 为根的子树。
    6. 在循环2-5结束时，我们得到了步骤3中得到的连通分量集，以及T中唯一剩下的子树。
    7.     如果在第 3 步恰好得到 2 颗完整的子树，并且 T 中剩余子树的权重也等于 S target，那么这就是我们的解决方案。
    8.     如果在第 3 步恰好获得了 3 个完整的子树，并且 T 中剩余子树的权重为零，那么我们将剩余子树与任何一个完成的子树组合并获得解决方案。
    9.     否则，问题无解。
    • 2

相关问题