连接所有岛屿的最小成本是多少？（涉及IT技术）

Question

有一个大小为N x M的网格。一些单元格是被标记为'0'的小岛，其余的则是水域。每个水域单元格上都有一个数字，表示建造在该单元格上的桥梁的成本。你需要找到将所有岛屿连接起来所需的最小成本。如果两个单元格共享一条边或一个顶点，则它们相互连接。

可以使用什么算法来解决这个问题？如果N，M的值很小，比如NxM <= 100，那么可以使用什么作为暴力方法？

例如，对于给定的图像，绿色单元格表示小岛，蓝色单元格表示水域，浅蓝色单元格表示应该建造桥梁的单元格。因此，对于以下图像，答案将是17。

最初，我考虑将所有小岛标记为节点，并通过最短桥连接每对小岛。然后问题可以简化为最小生成树，但在这种方法中，我错过了边重叠的情况。例如，在下面的图像中，任意两个小岛之间的最短距离是7（用黄色标出），因此使用最小生成树的答案将是14，但答案应该是11（用浅蓝色标出）。

- vaibhavatul47

---

你在问题中描述的解决方案方法似乎是正确的。您能否详细说明一下“我错过了边缘重叠的情况”是什么意思？ - Asad Saeeduddin

你能分享一下你目前正在使用的代码吗？这将使得回答问题更容易，并且也能让我们了解你当前的方法是什么。 - Asad Saeeduddin

这是 斯坦纳树问题 的一个变体。请访问维基百科获取更多信息。简单来说，虽然无法在多项式时间内找到准确解，但最小生成树是一个不错的近似解。 - Gassa

这不是旅行商问题。它看起来像是在此线程中回答的寻找“便利会议点”，但更加先进（因为岛不是一个点，距离由不同单元格的成本修改，并且它不仅有一个会议点）： https://dev59.com/GWoy5IYBdhLWcg3wL7L1 - user3745123

你可能想查看关于二维欧几里得距离变换算法的比较研究的以下论文。 - MicSim

Answer 1

为解决这个问题，我会使用整数规划框架，并定义三组决策变量：

• x_ij：二进制指示变量，表示是否在水域位置（i，j）建造桥梁。
• y_ijbcn：二进制指示变量，表示第 n 个连接岛屿 b 和 c 的水域位置（i，j）。
• l_bc：二进制指示变量，表示岛屿 b 和 c 是否直接相连（即只能从 b 到 c 的桥梁方格上行走）。

对于桥梁建造成本 c_ij ，最小化的目标价值是sum_ij c_ij * x_ij。我们需要向模型添加以下约束：

• 我们需要确保y_ijbcn变量是有效的。我们只能建造桥梁后到达水域广场，因此对于每个水域位置（i，j），y_ijbcn <= x_ij。如果（i，j）不与岛屿 b 相邻，则y_ijbc1必须等于0。最后，对于n>1，只有在前一步使用了相邻的水域位置时，才能使用y_ijbcn。将N（i，j）定义为与（i，j）相邻的水域广场，则这等效于y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1)。
• 我们需要确保只有在 b 和 c 相连时才设置 l_bc 变量。如果我们将I（c）定义为与岛屿 c 相邻的位置，则可以通过l_bc <= sum_{(i, j) in I(c), n} y_ijbcn来实现。
• 我们需要确保所有岛屿都直接或间接相连。我们可以通过以下方式实现：对于每个非空的真子集 S of 岛屿，要求 S 中至少有一个岛屿与其余集合 S' 中的至少一个岛屿相连。在约束条件中，对于大小小于等于 K/2（其中 K 是岛屿数量）的每个非空集合 S，添加一个约束条件：sum_{b in S} sum_{c in S'} l_bc >= 1。

对于具有 K 个岛屿、W 个水域方格和指定最大路径长度 N 的问题实例，这是一个混合整数规划模型，具有O(K^2WN)个变量和O(K^2WN + 2^K)个约束条件。显然，随着问题规模的增大，这将变得难以处理，但对于你关心的规模可能是可解的。为了了解可扩展性，我会使用 pulp 包在 Python 中实现它。让我们首先从问题底部的 7 x 9 小地图开始：

import itertools
import pulp
water = {(0, 2): 2.0, (0, 3): 1.0, (0, 4): 1.0, (0, 5): 1.0, (0, 6): 2.0,
         (1, 0): 2.0, (1, 1): 9.0, (1, 2): 1.0, (1, 3): 9.0, (1, 4): 9.0,
         (1, 5): 9.0, (1, 6): 1.0, (1, 7): 9.0, (1, 8): 2.0,
         (2, 0): 1.0, (2, 1): 9.0, (2, 2): 9.0, (2, 3): 1.0, (2, 4): 9.0,
         (2, 5): 1.0, (2, 6): 9.0, (2, 7): 9.0, (2, 8): 1.0,
         (3, 0): 9.0, (3, 1): 1.0, (3, 2): 9.0, (3, 3): 9.0, (3, 4): 5.0,
         (3, 5): 9.0, (3, 6): 9.0, (3, 7): 1.0, (3, 8): 9.0,
         (4, 0): 9.0, (4, 1): 9.0, (4, 2): 1.0, (4, 3): 9.0, (4, 4): 1.0,
         (4, 5): 9.0, (4, 6): 1.0, (4, 7): 9.0, (4, 8): 9.0,
         (5, 0): 9.0, (5, 1): 9.0, (5, 2): 9.0, (5, 3): 2.0, (5, 4): 1.0,
         (5, 5): 2.0, (5, 6): 9.0, (5, 7): 9.0, (5, 8): 9.0,
         (6, 0): 9.0, (6, 1): 9.0, (6, 2): 9.0, (6, 6): 9.0, (6, 7): 9.0,
         (6, 8): 9.0}
islands = {0: [(0, 0), (0, 1)], 1: [(0, 7), (0, 8)], 2: [(6, 3), (6, 4), (6, 5)]}
N = 6

# Island borders
iborders = {}
for k in islands:
    iborders[k] = {}
    for i, j in islands[k]:
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                if (i+dx, j+dy) in water:
                    iborders[k][(i+dx, j+dy)] = True

# Create models with specified variables
x = pulp.LpVariable.dicts("x", water.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)
pairs = [(b, c) for b in islands for c in islands if b < c]
yvals = []
for i, j in water:
    for b, c in pairs:
        for n in range(N):
            yvals.append((i, j, b, c, n))

y = pulp.LpVariable.dicts("y", yvals, lowBound=0, upBound=1)
l = pulp.LpVariable.dicts("l", pairs, lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)

# Objective
mod += sum([water[k] * x[k] for k in water])

# Valid y
for k in yvals:
    i, j, b, c, n = k
    mod += y[k] <= x[(i, j)]
    if n == 0 and not (i, j) in iborders[b]:
        mod += y[k] == 0
    elif n > 0:
        mod += y[k] <= sum([y[(i+dx, j+dy, b, c, n-1)] for dx in [-1, 0, 1] for dy in [-1, 0, 1] if (i+dx, j+dy) in water])

# Valid l
for b, c in pairs:
    mod += l[(b, c)] <= sum([y[(i, j, B, C, n)] for i, j, B, C, n in yvals if (i, j) in iborders[c] and B==b and C==c])

# All islands connected (directly or indirectly)
ikeys = islands.keys()
for size in range(1, len(ikeys)/2+1):
    for S in itertools.combinations(ikeys, size):
        thisSubset = {m: True for m in S}
        Sprime = [m for m in ikeys if not m in thisSubset]
        mod += sum([l[(min(b, c), max(b, c))] for b in S for c in Sprime]) >= 1

# Solve and output
mod.solve()
for row in range(min([m[0] for m in water]), max([m[0] for m in water])+1):
    for col in range(min([m[1] for m in water]), max([m[1] for m in water])+1):
        if (row, col) in water:
            if x[(row, col)].value() > 0.999:
                print "B",
            else:
                print "-",
        else:
            print "I",
    print ""

使用pulp包中的默认求解器（CBC求解器），该代码运行时间为1.4秒，输出正确解决方案：

I I - - - - - I I 
- - B - - - B - - 
- - - B - B - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - I I I - - - 

接下来，考虑问题顶部的完整问题，这是一个13 x 14的网格，其中有7个岛屿:

water = {(i, j): 1.0 for i in range(13) for j in range(14)}
islands = {0: [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)],
           1: [(9, 0), (9, 1), (10, 0), (10, 1), (10, 2), (11, 0), (11, 1),
               (11, 2), (12, 0)],
           2: [(0, 7), (0, 8), (1, 7), (1, 8), (2, 7)],
           3: [(7, 7), (8, 6), (8, 7), (8, 8), (9, 7)],
           4: [(0, 11), (0, 12), (0, 13), (1, 12)],
           5: [(4, 10), (4, 11), (5, 10), (5, 11)],
           6: [(11, 8), (11, 9), (11, 13), (12, 8), (12, 9), (12, 10), (12, 11),
               (12, 12), (12, 13)]}
for k in islands:
    for i, j in islands[k]:
        del water[(i, j)]

for i, j in [(10, 7), (10, 8), (10, 9), (10, 10), (10, 11), (10, 12),
             (11, 7), (12, 7)]:
    water[(i, j)] = 20.0

N = 7

MIP求解器通常能够相对快速地获得良好的解并花费大量时间尝试证明解的最优性。使用与上述相同的求解器代码，程序在30分钟内无法完成。但是，您可以为求解器提供超时时间以获取近似解：

mod.solve(pulp.solvers.PULP_CBC_CMD(maxSeconds=120))

这会得到一个目标值为17的解决方案:

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - B - - - B - - - 
- - - B - B - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - - - - B - - 
- - - - - B - I - - - - B - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

为了提高获得解决方案的质量，您可以使用商业MIP求解器（如果您在学术机构中，则免费，否则可能不免费）。例如，这是Gurobi 6.0.4的性能，再次使用2分钟的时间限制（尽管从解决方案日志中我们可以看出，求解器在7秒钟内找到了当前最佳解决方案）：

mod.solve(pulp.solvers.GUROBI(timeLimit=120))

这实际上找到了一个目标值为16的解决方案，比OP手工找到的还要好一点！

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - - - - - B - - - 
- - - B - - - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - B B - - - - 
- - - - - B - I - - B - - - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

- josliber

---

与其使用y_ijbcn公式，我会尝试一种基于流量的公式（每个元组都有一个变量，由岛对和方形邻接组成；保守约束，在汇点处超额1，在源头处为-1；通过是否购买来限制方格总流入量）。 - David Eisenstat

@DavidEisenstat 感谢您的建议 - 我刚刚尝试了一下，不幸的是，对于这些问题实例，它解决得更慢了。 - josliber

这正是我开始出悬赏时正在寻找的内容。令人惊讶的是，一个描述起来如此琐碎的问题竟然能够让MIP求解器感到如此困难。我在想以下是否正确：连接两个岛屿的路径是一条最短路径，并且必须通过某个单元格(i, j)。例如，在Gurobi的解决方案中，左上角和中间的岛屿是通过一条被限制通过单元格(6, 5)的SP相连的。不确定这是否正确，但我会在某个时候进行调查。谢谢回答！ - Ioannis

@Ioannis 有趣的问题--我不确定你的猜想是否正确，但它对我来说似乎很有道理。您可以将单元格（i，j）视为这些岛屿的桥梁需要进一步连接到其他岛屿的地方，然后在达到该协调点的情况下，您只需要建造最便宜的桥梁来连接岛屿对。 - josliber

Answer 2

一种暴力破解的方法，伪代码如下：

start with a horrible "best" answer
given an nxm map,
    try all 2^(n*m) combinations of bridge/no-bridge for each cell
        if the result is connected, and better than previous best, store it

return best

在C++中，这可以写成：

// map = linearized map; map[x*n + y] is the equivalent of map2d[y][x]
// nm = n*m
// bridged = true if bridge there, false if not. Also linearized
// nBridged = depth of recursion (= current bridge being considered)
// cost = total cost of bridges in 'bridged'
// best, bestCost = best answer so far. Initialized to "horrible"
void findBestBridges(char map[], int nm,
   bool bridged[], int nBridged, int cost, bool best[], int &bestCost) {
   if (nBridged == nm) {
      if (connected(map, nm, bridged) && cost < bestCost) {
          memcpy(best, bridged, nBridged);
          bestCost = best;
      }
      return;
   }
   if (map[nBridged] != 0) {
      // try with a bridge there
      bridged[nBridged] = true;
      cost += map[nBridged];

      // see how it turns out
      findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost);         

      // remove bridge for further recursion
      bridged[nBridged] = false;
      cost -= map[nBridged];
   }
   // and try without a bridge there
   findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost);
}

在进行首次调用后（我假设您正在将2D地图转换为1D数组以便轻松复制），bestCost将包含最佳答案的成本，而best将包含产生它的桥梁模式。但是，这非常慢。

优化：

• 通过使用“桥梁限制”，并逐渐增加最大桥梁数量运行算法，可以找到最小的答案，而无需探索整个树。如果存在1个桥梁答案，则查找时间复杂度为O(nm)，而不是O(2 ^ nm) - 这是一个巨大的改进。
• 一旦超过了bestCost，您可以通过停止递归（这也称为“剪枝”）来避免搜索，因为之后继续寻找毫无意义。如果找不到更好的结果，就别再继续查找了。
• 如果先查看“好”的候选项而不是“坏”的候选项（如现在的情况，单元格按从左到右，从上到下的顺序查看），则以上修剪方法将起到更好的效果。一个好的启发式方法是将那些靠近多个未连接组件的单元格视为比那些没有的单元格优先级更高。但是，一旦添加了启发式算法，您的搜索就开始类似于A*（您也需要某种优先级队列）。
• 要避免重复的桥梁和通往任何地方的桥梁。如果移除任何不会断开岛屿网络的桥梁，则该桥梁是多余的。

类似A*的通用搜索算法可以实现更快的搜索，尽管找到更好的启发式方法并不是一项简单的任务。对于更具问题特定性的方法，使用已有的史泰纳树结果，如@Gassa所建议的那样，是正确的方法。然而，请注意，在正交网格上构建Steiner树的问题是NP完全的，根据Garey和Johnson的这篇论文。

如果“足够好”的解决方案就足够了，那么遗传算法可能可以快速找到可接受的解决方案，只要您添加了一些关于首选桥梁位置的关键启发式方法即可。

- tucuxi

---

尝试所有的2^(n*m)种组合，嗯，2^(13*14) ~ 6.1299822e+54次迭代。如果我们假设您每秒可以执行一百万次迭代，那么这将需要... ~194380460000000000000000000000000000000000`年。这些优化是非常必要的。 - Mooing Duck

OP确实要求“当N，M的值非常小，例如NxM <= 100时，请提供一种蛮力方法”。假设有20座桥足够了，并且您只使用上面限制桥梁数量的优化，最优解将在O(2^20)内找到，这个复杂度对于您的理论计算机范围来说是很好处理的。 - tucuxi

大多数回溯算法在添加剪枝、迭代加深等优化之前效率都非常低下。但这并不意味着它们毫无用处。例如，国际象棋引擎通常使用这些算法（当然，它们会使用书中的每一个技巧来积极地进行剪枝），从而战胜国际象棋大师。 - tucuxi

Answer 3

这个问题是史泰纳树的一个变种，称为节点加权史泰纳树，专门针对某些图形。简而言之，节点加权史泰纳树是在给定节点加权无向图中寻找最便宜的节点集，其中包括所有终端节点并引出一个连通子图。可惜，在一些简单搜索中似乎找不到任何求解器。

为了将其制定成整数规划问题，需要为每个非终端节点制定一个0-1变量，然后对于所有从起始图中移除两个终端节点之间连接的非终端节点的子集，要求该子集中变量的总和至少为1。这会导致太多的约束条件，因此您需要使用高效的节点连通性算法（基本上是最大流）来懒惰地强制执行它们，并检测违反约束条件的最大值。抱歉没有详细信息，但即使您已经熟悉整数规划，实现这个问题也很困难。

- David Eisenstat

Answer 4

考虑到这个问题发生在一个网格中，并且您有明确定义的参数，我会通过创建最小生成树系统地消除问题空间来解决问题。在这样做时，如果您使用Prim算法来解决这个问题，那么对我来说是有意义的。

不幸的是，现在你遇到了抽象化网格以创建一组节点和边的问题...因此，这篇文章的真正问题是如何将我的n x m网格转换为{V}和{E}？

乍一看，这个转换过程很可能是NP-Hard的，因为可能的组合数量非常多（假设所有水路成本都相同）。为了处理路径重叠的情况，您应该考虑制作一个虚拟岛屿。

完成后，运行Prim算法，您应该能够得出最优解。

我认为动态规划在这里无法有效运行，因为没有可观察的最优性原则。如果我们找到两个岛之间的最小成本，那并不一定意味着我们可以找到连接这两个岛和第三个岛或其他子集的最小成本岛（按照我的定义通过Prim找到MST）。

如果您需要代码（伪代码或其他）将您的网格转换为一组{V}和{E}，请发送私信给我，我会尝试拼凑出一个实现方案。

- karnesJ.R

---

所有的水费用并不相同（见例子）。由于Prim没有创建这些“虚拟节点”的概念，因此您应该考虑一个可以实现的算法：斯坦纳树（其中您的虚拟节点被称为“斯坦纳点”）。 - tucuxi

@tucuxi:提及所有水路费用可能相同是必要的，因为这是将搜索空间膨胀到最大潜力的条件。这就是我提出此事的原因。关于Prim算法，我假设负责为此问题实现Prim算法的程序员知道Prim算法不会创建虚拟节点，并在实现层面上处理此问题。我还没有看过斯坦纳树（仍然是本科生），所以感谢您提供了新的学习资料！ - karnesJ.R