连接所有岛屿的最低成本是多少？

Question

有一个大小为N x M的网格.一些细胞是由'0'表示的岛,而其他细胞是水.每个水电池上都有一个数字,表示在该电池上制造的电桥的成本.您必须找到所有岛屿可以连接的最低成本.如果单元共享边或顶点,则单元连接到另一个单元.

可以用什么算法来解决这个问题？
编辑:如果N,M的值非常小,可以用作蛮力方法,比如说NxM <= 100？

示例:在给定图像中,绿色单元格表示岛屿,蓝色单元格表示水,浅蓝色单元格表示应在其上制作桥梁的单元格.因此,对于下面的图像,答案将是17.

最初我想到将所有岛屿标记为节点并用最短的桥连接每对岛屿.然后问题可以减少到最小生成树,但在这种方法中我错过了边缘重叠的情况.例如,在下图中,任意两个岛之间的最短距离为7(标记为黄色),因此通过使用最小生成树,答案为14,但答案应为11(以浅蓝色标记).

Answer 1

为了解决这个问题,我将使用整数编程框架并定义三组决策变量:

• x_ij:我们是否在水位(i,j)建立桥梁的二元指示变量.
• y_ijbcn:水位置(i,j)是否是连接岛b到岛c的第n个位置的二进制指示符.
• l_bc:二进制指示符变量,用于表示岛屿b和c是否直接链接(也就是说,您只能在从b到c的桥梁方块上行走).

对于桥梁建筑成本c_ij,要最小化的目标值是sum_ij c_ij * x_ij.我们需要为模型添加以下约束:

• 我们需要确保y_ijbcn变量有效.如果我们在那里建一座桥,我们总是只能到达水广场,因​​此y_ijbcn <= x_ij对于每个水位(i,j).此外,y_ijbc1如果(i,j)不与边界岛b相邻,则必须等于0.最后,对于n> 1,y_ijbcn仅在步骤n-1中使用相邻水位时才能使用.定义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,要求S中的至少一个岛链接到S的补码中的至少一个岛,我们将其称为S'.在限制,我们可以通过添加约束为大小的每个非空集S实现此<= K/2(其中,K是岛的数量), sum_{b in S} sum_{c in S'} l_bc >= 1.

对于具有K个岛,W水方块和指定的最大路径长度N的问题实例,这是具有O(K^2WN)变量和O(K^2WN + 2^K)约束的混合整数编程模型.显然,随着问题规模变大,这将变得棘手,但对于您关心的尺寸,它可能是可以解决的.为了了解可伸缩性,我将使用纸浆包在python中实现它.让我们首先从较小的7 x 9地图开始,问题的底部有3个岛屿:

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 ""

使用纸浆包装(CBC解算器)中的默认求解器运行需要1.4秒,并输出正确的解决方案:

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

接下来,考虑问题顶部的完整问题,即带有7个岛的13 x 14网格:

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 

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 ++中，这可以写成

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

进行第一个调用后（我假设您正在将2d映射转换为1d数组以方便复制），bestCost将包含最佳答案的成本，best并将包含产生此结果的桥的模式。但是，这非常慢。

优化：

• 通过使用“网桥限制”，并运行用于增加最大网桥数量的算法，您可以找到最少的答案，而无需探索整个树。找到一个1桥答案（如果存在的话）将是O（nm）而不是O（2 ^ nm）-这是一个巨大的改进。
• 超出限制范围后bestCost，您可以避免搜索（通过停止递归；也称为“修剪”），因为继续关注毫无意义。如果无法改善，请不要继续挖掘。
• 如果您在查看“不良”候选者之前先查看“良好”候选者，那么以上修剪效果会更好（因为实际上，所有单元格都是按照从左到右，从上到下的顺序查看的）。一个好的启发式方法是将靠近几个未连接组件的单元的优先级视为比未连接单元的单元更高的优先级。但是，一旦添加了启发式搜索，您的搜索就会开始类似于A *（并且您还需要某种优先级队列）。
• 避免重复的桥梁和无处可去的桥梁。如果删除了所有不断开孤岛网络的网桥，则是多余的。

尽管找到更好的启发式方法不是一件容易的事，但是诸如A *之类的常规搜索算法允许更快的搜索速度。对于特定于问题的方法，可以使用@Gassa建议的在Steiner树上使用现有结果的方法。但是请注意，根据Garey和Johnson的论文，在正交网格上构建Steiner树的问题是NP-Complete 。

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