4

我想将具有 N 个加权顶点和 N-1 个边的图划分为三个部分，以使每个部分中所有顶点的权重总和的最大值最小化。这是我试图解决的实际问题，http://www.iarcs.org.in/inoi/contests/jan2006/Advanced-1.php

我考虑了以下方法

/*Edges are stored in an array E, and also in an adjacency matrix for depth first search.
Every edge in E has two attributes a and b which are the nodes of the edge*/
min-max = infinity
for i -> 0 to length(E):
   for j -> i+1 to length(E):
     /*Call depth first search on the nodes of both the edges E[i] and E[j]
     the depth first search returns the sum of weights of the vertices it visits,
     we keep track of the maximum weight returned by dfs*/
     Adjacency-matrix[E[i].a][E[i].b] = 0;
     Adjacency-matrix[E[j].a][E[j].b] = 0;
     max = 0
     temp = dfs(E[i].a) 
     if temp > max then max = temp
     temp = dfs(E[i].b) 
     if temp > max then max = temp
     temp = dfs(E[i].a) 
     if temp > max then max = temp
     temp = dfs(E[i].a) 
     if temp > max then max = temp

     if max < min-max
        min-max = max
     Adjacency-matrix[E[i].a][E[i].b] = 1;
     Adjacency-matrix[E[j].a][E[j].b] = 1;
    /*The depth first search is called four times but it will terminate one time
   if we keep track of the visited vertices because there are only three components*/

  /*After the outer loop terminates what we have in min-max will be the answer*/

上述算法需要 O(n^3) 时间，因为边的数量将是 n-1，外循环将运行 (n-1)！需要 O(n^2) 的时间，dfs 将只访问每个顶点一次，因此是 O(n) 时间。

但问题是 n 可以 <= 3000 并且 O(n^3) 时间不适合这个问题。是否有任何其他方法可以比 n^3 更快地计算解决链接中的问题？

编辑：

我在 c 中实现了@BorisStrandjev 的算法，它给了我对问题中测试输入的正确答案，但对于所有其他测试输入，它给出了错误答案，这是我在 ideone http://ideone.com中的代码的链接/67GSa2，这里的输出应该是 390 但程序会打印 395。

我试图找出我的代码是否有任何错误，但我没有看到任何错误。任何人都可以在这里帮助我，我的代码给出的答案非常接近正确答案，那么算法还有什么更多的吗？

编辑2：

在下图中-

在此处输入图像描述@BorisStrandjev，您的算法将在其中一次迭代中选择 i 作为 1， j 作为 2，但是第三部分 (3,4) 无效。

编辑 3

我终于在我的代码中遇到了错误，而不是 V[i] 存储 i 的总和及其所有后代，而是存储 V[i] 及其祖先，否则它将正确解决上述示例，感谢大家的帮助.

4

3 回答 3

3

是的，有更快的方法。

我将需要一些辅助矩阵，我将以正确的方式将它们的创建和初始化留给您。

首先种植树 - 即使图形定向。计算每个顶点的数组VAL[i]- 一个顶点及其所有后代的乘客数量（记住我们已经种植，所以现在这是有道理的）。desc[i][j]如果 vertexi是 vertex 的后代，还计算布尔矩阵j。然后执行以下操作：

best_val = n
for i in 1...n
  for j in i + 1...n
    val_of_split = 0
    val_of_split_i = VAL[i]
    val_of_split_j = VAL[j]
    if desc[i][j] val_of_split_j -= VAL[i] // subtract all the nodes that go to i
    if desc[j][i] val_of_split_i -= VAL[j]
    val_of_split = max(val_of_split, val_of_split_i)
    val_of_split = max(val_of_split, val_of_split_j)
    val_of_split = max(val_of_split, n - val_of_split_i - val_of_split_j)
    best_val  = min(best_val, val_of_split)

执行此循环后，答案将在best_val. 该算法显然是O(n^2)您只需要弄清楚如何计算desc[i][j]并且VAL[i]如此复杂，但这并不是一项复杂的任务，我认为您可以自己弄清楚。

编辑在这里，我将在伪代码中包含整个问题的代码。在OP自己尝试解决之前，我故意不包含代码：

int p[n] := // initialized from the input - price of the node itself
adjacency_list neighbors := // initialized to store the graph adjacency list

int VAL[n] := { 0 } // the price of a node and all its descendants
bool desc[n][n] := { false } // desc[i][j] - whether i is descendant of j

boolean visited[n][n] := {false} // whether the dfs visited the node already
stack parents := {empty-stack}; // the stack of nodes visited during dfs

dfs ( currentVertex ) {
   VAL[currentVertex] = p[currentVertex]
   parents.push(currentVertex)
   visited[currentVertex] = true
   for vertex : parents // a bit extended stack definition supporting iteration
       desc[currentVertex][vertex] = true
   for vertex : adjacency_list[currentVertex]
       if visited[vertex] continue
       dfs (currentvertex)
       VAL[currentVertex] += VAL[vertex]
   perents.pop

calculate_best ( )
    dfs(0)
    best_val = n
    for i in 0...(n - 1)
      for j in i + 1...(n - 1)
        val_of_split = 0
        val_of_split_i = VAL[i]
        val_of_split_j = VAL[j]
        if desc[i][j] val_of_split_j -= VAL[i]
        if desc[j][i] val_of_split_i -= VAL[j]
        val_of_split = max(val_of_split, val_of_split_i)
        val_of_split = max(val_of_split, val_of_split_j)
        val_of_split = max(val_of_split, n - val_of_split_i - val_of_split_j)
        best_val  = min(best_val, val_of_split)
    return best_val

最好的分割是{descendants of i} \ {descendants of j},{descendants of j} \ {descendants of i}和{all nodes} \ {descendants of i} U {descendants of j}。

于 2013-01-07T11:42:05.017 回答
1

编辑 4：这行不通！！！

如果您按照 3、4、5、6、1、2 的顺序处理链接中的节点，在处理 6 之后，（我认为）您将拥有以下集合：{{3,4},{5}, {6}}、{{3,4,5}、{6}}、{{3,4,5,6}}，没有简单的方法可以再次拆分它们。

我只是在这里留下这个答案，以防其他人在考虑 DP 算法。

查看 DP 算法中所有已处理的邻居可能会起作用。

.

我正在考虑一个动态编程算法，其中矩阵是（项目 x 集数）

n = number of sets
k = number of vertices
// row 0 represents 0 elements included
A[0, 0] = 0
for (s = 1:n)
  A[0, s] = INFINITY
for (i = 1:k)
  for (s = 0:n)
    B = A[i-1, s] with i inserted into minimum one of its neighbouring sets
    A[i, s] = min(A[i-1, s-1], B)) // A[i-1, s-1] = INFINITY if s-1 < 0

编辑：DP的解释：

这是一个相当基本的动态规划算法。如果你需要更好的解释，你应该多读一些，这是一个非常强大的工具。

A 是一个矩阵。第 i 行表示一个包含直到 i 的所有顶点的图。列 c 表示集合数 = c 的解。

因此A[2,3]，将给出包含项目 0、项目 1 和项目 2 和 3 集合的图表的最佳结果，因此每个集合都在它自己的集合中。

然后从第 0 项开始，计算每个集合数的行（唯一有效的是集合数 = 1），然后使用上述公式执行第 1 项，然后执行第 2 项，依此类推。

A[a, b]然后是所有顶点最多包含 a 和 b 个集合的最优解。因此，您只需返回A[k, n]（包含所有顶点和目标集数的那个）。

编辑 2：复杂性

O(k*n*b)其中 b 是节点的分支因子（假设您使用邻接列表）。

因为n = 3，这是O(3*k*b)= O(k*b)。

编辑 3：确定应将顶点添加到哪个相邻集

在联合查找结构中保留 n 个包含 k 个元素的数组，每个集合都指向该集合的总和。对于每个新行，为了确定可以将顶点添加到哪些集合，我们使用它的邻接列表并查找每个邻居的集合和值。一旦找到最佳选项，我们就可以将该元素添加到适用的集合中，并将其总和增加添加元素的值。

您会注意到该算法仅向下查找 1 行，因此我们只需要跟踪最后一行（不存储整个矩阵），并且可以修改前一行的 n 个数组而不是复制它们。

于 2013-01-07T11:35:26.540 回答
1

您可以结合使用 Binary Search 和 DFS来解决此问题。

以下是我将如何进行：

  1. 计算图的总权重，同时找出图中最重的边。让它们分别为 Sum、MaxEdge。
  2. 现在我们必须在这个范围之间进行二分搜索：[maxEdge, Sum]。
  3. 在每次搜索迭代中，middle = (start + end / 2)。现在，选择一个起始节点并执行 DFS st，在子图中遍历的边的总和尽可能接近“中间”。但保持这个总和小于中间值。这将是一个子图。在同一次迭代中，现在选择另一个未被先前 DFS 标记的节点。以相同的方式执行另一个 DFS。同样，再做一次，因为我们需要将图表分成 3 个部分。
  4. 分钟。上面计算的 3 个子图中的权重是本次迭代的解决方案。
  5. 继续运行这个二分搜索，直到它的结束变量超过它的开始变量。

在第 4 步中获得的所有分钟的最大值就是您的答案。您可以进行额外的簿记以获得 3 个子图。

订单复杂度：N log(Sum)其中 Sum 是图的总权重。

我刚刚注意到您谈到了加权顶点，而不是边。在这种情况下，只需在我的解决方案中将边视为顶点。它应该仍然有效。

于 2013-01-07T11:45:36.333 回答