假设我们有一个连通的无向图:G=(V,E)。
连通集的定义:一组属于 G 的 V 的点形成一个有效的连通集当且仅当该组中的每个点都在距同一组中任何其他点的 T-1 条边内，T 是数字组中的点数。
请注意，连通集只是 G 的连通子图，没有边但有点。
并且我们在连通集上定义了一个任意函数 F，即给定一个任意连通集 CS F(CS) 将为我们提供一个实数值。
如果两个连通集的并集不是连通集，则称它们不相交。
为了直观的解释，请看下图:
图中，红、黑、绿点集都是有效的连通集，绿集与红集不相交，黑集与红集不相交。
现在的问题是: 我们想从 G 中找到一堆不相交的连通集，以便: (1)每个连通集至少有K个点。 (K 是一个全局参数)。 (2)它们的函数值之和，即max(ΣF(CS))被最大化。
除了穷举搜索之外，是否有任何有效的算法来解决此类问题？ 谢谢!
例如，图可以是二维欧几里德平面上的平面图，连通集CS的函数值F可以定义为CS中所有点的最小外接矩形的面积(minimum bounding rectangle 是包含 CS 中所有点的最小矩形)。
最佳答案
如果你能定义你的函数并证明它是一个Submodular Function (类似于连续优化中凸性的属性)然后有非常有效的(强多项式)算法可以解决您的问题，例如Minimum Norm Point .
要证明您的函数是子模块的，您只需证明以下内容:
最小范数点算法有几种可用的实现方式，例如Matlab Toolbox for Submodular Function Optimization
关于algorithm - 组合优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3922144/