组合优化
out*_*law 7 algorithm math optimization graph
假设我们有一个连通和无向图:G =(V,E).
连通集的定义:属于G的V的一组点形成有效的连通集如果该组中的每个点都在距离同一组中的任何其他点的T-1个边缘内,则T是所述点中的点数.群组.
请注意,连接集只是G的连接子图,没有边但是带有点.
并且我们在连接集上定义了任意函数F,即给定任意连接集CS F(CS)将给出一个实数值.
如果它们的并集不是连接集,则说两个连接集是不相交的.
有关视觉说明,请参见下图:在图表中,红色,黑色,绿色点集都是有效的连接集,绿色集与红色集不相交,但黑色集与红色集不相交.
现在的问题是:我们希望从G中找到一堆不相交的连接集,以便:(1)每个连接集至少有K个点.(K是全局参数).(2)它们的函数值之和,即max(ΣF(CS))被最大化.
除了详尽的搜索之外,是否有任何有效的算法来解决这样的问题？谢谢!
例如,图形可以是2D欧几里得平面中的平面图形,并且连通集合CS的函数值F可以定义为CS中所有点的最小边界矩形的面积(最小边界矩形是包含CS中所有点的最小矩形.
我怀疑是否存在有效的算法，因为例如对于完整的图，如果不知道每个子图上 F 的值，就无法解决问题（除非您对 F 有假设：例如单调性）。
尽管如此，我还是会选择非确定性算法。尝试模拟退火，过渡为：
- 从集合中删除一个点（如果它保持连接）
- 将一个点从一个集合移动到另一个集合（如果它们保持连接）
- 删除一组
- 添加一个点的集合
祝你好运，这似乎是一个难题。