具有利润的连通图的优化问题

Question

我正在尝试开发一种算法来解决我无法分类的问题，我公开了主题：

您有一张地图，分为多个部分，这些部分具有特定的区域和一定数量的人居住的地方。

该问题包括找到面积不超过特定值的连接部分的集合，从而最大化所选居民的数量。

目前我可以想到两种方法：

将问题视为具有正自然值的无向图中的全对最短路径问题，其中不满足最大选定区域约束的解将被丢弃。为此，您可以使用 Floyd-Warshall 算法、适用于所有对的 Dijkstra 算法或 Thorup 算法（可以在时间 V * E 内完成，其中这些是图的顶点和边）。
将其视为具有利润的开放车辆路径问题，其中每辆车可以在其想要的任何地方开始和结束（具有利润的开放车辆路径问题或 OVRPP）。
另一种方法

此外，根据特定问题的组合，在某些情况下可以使用遗传算法和禁忌搜索，但这仅适用于不允许找到最佳解决方案的情况。

更清楚地说，所寻求的是获得面积之和不超过总面积的连接部分的选择。要最大化的参数是所选部分的总体总和。目标是找到最优解决方案。

例如，这是最大面积为 6（红色区域）的最佳选择

谢谢大家！

Answer 1

最初打算将此作为评论，因为它不构成带有编码解决方案的完整答案，但我相信它可能近似于规范答案。

\n

您的问题已被广泛研究（也许不是这个特定的变体，而是包括这个在内的许多其他问题。）它是背包问题的一种变体，并且是 NP 完全或更难（NP-hard）。这应该是显而易见的，因为问题的一个特殊情况是所有节点都连接到所有其他节点，这正是0-1 背包问题。

\n

在参考文献（1）中，作者展示了一种近似算法，该算法用下限和上限进行近似

\n

(1\xe2\x88\x92\xce\xb5)/2 \xc2\xb7(1 \xe2\x88\x92 1/e^(1\xe2\x88\x92\xce\xb5))\n

和

\n

1 \xe2\x88\x92 1/e + \xce\xb5\n

就良好的近似算法而言，这可能是最接近的。

\n

0-1 背包问题的动态规划解决方案有一个简单的变体，可以产生很好的近似值，如果有兴趣和时间，我可以进一步讨论。

\n

\n