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

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难的优化问题.例如,可以轻松地将分区问题简化为此(平面性属性不会导致问题).因此,计算最佳解决方案的算法(您似乎在评论中要求最佳解决方案)对于"数万个节点"来说不太可能实用.

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

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