algorithm - 最大化具有给定最小权重的子图数

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

显然这不是最优的。有没有人有更好的解决方案？ (可能是我孤陋寡闻，这不是一个复杂的问题，但我从来没有研究过图论...)

编辑(更多背景详细信息):此图中的节点是要为其提供统计数据的低规模行政单位。但是，这些单位需要有一定的最小人口规模，以避免与个人数据立法发生冲突。我的目标是创建聚合，以便在途中丢失尽可能少的信息。邻域关系用作图形边，因为生成的单元必须是连续的。

集合中的大多数单元(节点)都远高于最小阈值。如示例所示(最小尺寸 50)，其中大约 5-10% 的尺寸低于阈值:

Answer 1

这是一个 NP-hard 优化问题。例如，Partition problem可以很容易地减少到这个(平面性不会引起问题)。所以一个计算出最优解的算法(而且你在评论中似乎要求一个最优解)不太可能适用于“数万个节点”。

如果您实际上不需要最优解，而是需要一个好的解，我会使用局部优化方法，例如禁忌搜索或模拟退火。

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