小编Jan*_*era的帖子

我有一个无向平面图,每个节点都有一个权重.我希望将图形分成尽可能多的连接不相交的子图(编辑:或者达到子图的最小平均权重),条件是每个子图必须达到固定的最小权重(这是一个权重之和)其节点).只包含单个节点的子图也可以(如果节点的权重大于固定的最小值).

到目前为止我发现的是一种启发式:

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%低于阈值且尺寸不同:

我有一个可变长度的矢量列表,例如:

q <- list(c(1,3,5), c(2,4), c(1,3,5), c(2,5), c(7), c(2,5))

我需要计算列表中每个向量的出现次数,例如(可接受的任何其他合适的数据结构):

list(list(c(1,3,5), 2), list(c(2,4), 1), list(c(2,5), 2), list(c(7), 1))

有没有一种有效的方法来做到这一点？实际列表中有数万个项目,因此二次行为是不可行的.