最大化给定最小权重的子图数量

Question

我有一个无向平面图，每个节点都有一个权重。我想将该图分割成尽可能多的连接不相交的子图（或达到可能的子图的最小平均权重），假设每个子图必须达到固定的最小权重（即其节点的权重之和）。包含只有单个节点的子图也可以（如果节点的权重大于固定的最小值）。

目前我发现的是一种启发式方法：

create a subgraph out of every node
while there is an underweight subgraph:
  select the subgraph S with the lowest weight
  find a subgraph N that has the lowest weight among the neighbouring subgraphs of S
  merge S to N

显然，这不是最优的解决方案。是否有更好的解决方案？（也许我只是无知，这不是一个复杂的问题，但我从未学过图论......）

编辑（更多背景细节）：该图中的节点是要提供统计数据的低级行政单位。然而，为了避免与个人数据法规产生冲突，这些单位需要具有一定的最小人口规模。我的目标是创建聚合，以便在此过程中尽可能少地丢失信息。邻域关系用作图边缘，因为生成的单位必须是连续的。

大多数集合中的单位（节点）都远高于最低阈值。约5-10％的节点低于阈值，并且大小不同，如示例所示（最小大小为50）：

- Jan Šimbera

---

没有平面条件，这个问题肯定是强 NP-hard 的。我不期望有除了可能是一个动态规划的简单方法来利用平面性之外的其他方式，这个动态规划的运行时间以指数形式依赖于 √n（而不是 n），利用到了平面图的树宽为 O(√n) 的事实。 - David Eisenstat

感兴趣的图有多大？获得最优解有多重要？ - David Eisenstat

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Jan Šimbera

我会添加最大的子图，使其恰好达到最小值 - 较小的子图更有可能在后续填充中有用。 - Mike

你实现了启发式算法吗？它创建了多少个子图？总权重除以阈值是多少（一个粗略的上限）？ - David Eisenstat

Answer 1

这是一个NP-hard的优化问题。例如，划分问题可以轻松地被归约为此类问题（平面性质不会引起问题）。因此，计算最优解的算法（您在评论中似乎要求最优解）对于“成千上万个节点”来说是不可行的。

如果您实际上并不需要最优解而只需要一个好的解决方案，则可以使用本地优化方法，例如禁忌搜索或模拟退火。

因为您的子图的平均权重只是总图的权重除以子图的数量，因此唯一重要的是找到您可以达到的最大子图数量。猜测这个数字N，从一个包含N个子图的初始划分开始，然后使用本地移动的方式（1）将一个节点从一个子图移动到另一个子图，并（2）在相邻的两个子图之间交换两个节点，寻找一个可接受的解决方案，其中每个子图都具有所需的最小权重。如果您根本找不到可接受的解决方案，请减少N（例如减少一个），然后重新开始直到找到解决方案。

- Antti Huima

---

非常感谢。我最初是在寻找一种能够给出最优解的算法，但在发现它是NP难问题后，你的解决方案似乎是我找到的最佳选择。 - Jan Šimbera

Answer 2

实例的细节决定一切。

如果一个顶点本身就超过阈值，那么称之为重要。一个包含两个重要顶点的子图没有意义，因为我们可以将其分为两个子图。因此，最优解中的子图数量与不包含重要顶点的子图数量相关且可加。

因此，我们可以删除重要的顶点，并专注于利用剩下的部分尽可能地构造合法的子图。从您的地图来看，剩下的部分将由许多连接组件组成，每个组件只有少量的顶点。有效的子图必须是连通的，因此这些组件可以独立解决。对于小实例，可以枚举所有有效的子图，然后运行 Algorithm X 以查找最大基数包装。

- David Eisenstat

Answer 3

The problem is NP-hard, so I will present an exponential solution. This solution has many points of improvement, some of which I will highlight.

The main idea is that each partition of vertices is connected by some edges. By trying all possible sets of edges and counting the number of sets for each partition, you can find the best possible partition (optimal solution).

In your previous approach, there was no domain to expand the search. To solve this, we used Disjoint Sets for partition representation and Power Sets to find all possible sets of edges.

public Partition Solve(Graph g, int min)
{
    int max = 0;
    Partition best;

    // Find all the possible partitions for Edges
    foreach(var S in PowerSet(g.Edges))
    {
        // Build the Vertexes partition
        var partition =  BuildPartition(S);

        // Test the min condition foreach component
        if (IsInvalid(partition, min))
            continue;

        // Continue if we already have something better
        if (max >= partition.Length)
            continue;

        // Update
        max = partition.Length;
        best = partition;
    }

    return best;
}

public Partition BuildPartition(Graph g, IEnumerable<Edge> edges)
{
    // Initially Every Vertex in alone in his partition
    var partition = new DisjointSet(g.Vertexes);

    foreach (var edge in edges)
    {
        // If the Vertexes of this edge are already in the same partition DO NOTHING
        if (partition.Find(edge.V1) == partition.Find(edge.V2))
            continue;

        // Join both subsets
        partition.Union(edge.V1, edge.V2);
    }

    return parition;
}

public bool IsInvalid(Partition p, int min)
{
    return p.Sets.Any(t => t.Sum(v => v.Weight) < min);
}

您可以在以下几个方面改进解决方案： - 在PowerSet和IsInvalid条件中添加并行性 - 找到更好的方法来生成有效的边集 - 对于比最小值更重的顶点，有一些起始情况（始终会在单独的子图中）

算法的顺序由Power Set给出。 - Power Set：在这种情况下，对于N个顶点的图，最坏情况下将有3N-6条边，因此时间复杂度为O(2^N)。 - 建立分区：V + E * LogV，因此时间复杂度为O(NLogN) - IsInvalid：O(V)

最后，Solve是O(2^N * N * LogN) 使用这个公式计算操作次数

希望这能帮到您！

- Miguel

---

谢谢！然而，对于一个有10000个顶点的图形，需要检查的次数大约是10^3000，这实际上是不可持续的... - Jan Šimbera

你正在尝试解决一个NP问题！几乎没有什么方法会起作用。使用这个，你可以找到最优解，任何其他算法都将花费相同的时间。另一方面，你需要信任并尝试使用元启发式或进化算法来获得部分解决方案。 - Miguel

我现在确定一个算法是不可行的。我需要的是一种启发式方法，可以在多项式时间内近似得到一个非常好的解决方案... - Jan Šimbera