zal*_*loo 3 algorithm optimization partitioning graph-theory delaunay
我正在寻找一种算法,将图形划分为最大尺寸为n的顶点组(每个顶点都是连接的,如果它是自己的图形),同时保持组的数量最小化.我需要这个算法将delaunay三角剖分划分为每个区域中具有相同顶点数的区域.如果有人对解决这个问题有更好的想法,请告诉我!
看起来你正在寻找统一k路图分区问题的解决方案,其中,给定一个图G(V,E),目标是将顶点集V划分为一系列k不相交的子集V1, V2, ..., Vk,使得每个子集的大小Vi近似|V|/k.此外,通常需要"漂亮"的分区,其中任何两个子集之间的边缘权重之Vi和Vj最小化.
首先,众所周知,这个问题是NP完整的,排除了有效精确算法的存在.从好的方面来说,已经开发了许多有效的启发式方法,它们在许多实际问题上表现得非常好.
具体而言,基于迭代多级方法的方案在实践中非常成功.在这样的方法中,通过递增地合并相邻顶点以在层级的每个级别形成较小的"粗略"图来创建图的层次结构.当粗略图形变得足够小时形成初始分区,然后该分区从层次结构"映射"到原始图形上.通常作为该映射过程的一部分执行分区的迭代细化,通常导致伪最佳分区.
这种算法的实现并非易事,但是许多现有的包支持这样的例程.具体而言,METIS包被广泛使用.