岛屿

岛屿

关注
发信
关注(28)粉丝(399)

algorithm - 连接所有岛屿的最低费用是多少？

有一个大小为 N x M 的网格。一些单元是用“0”表示的岛，其他单元是水。每个水电池上都有一个数字，表示在该水电池上建造一座桥的成本。您必须找到可以连接所有孤岛的最低成本。如果一个单元共享一条边或一个顶点，则该单元将连接到另一个单元。

可以使用什么算法解决此问题？如果N，M的值非常小(例如NxM
示例:在给定的图像中，绿色单元格表示岛，蓝色单元格表示水，浅蓝色单元格表示应在其上架桥的单元格。因此，对于以下图像，答案将为 17 。

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

最佳答案

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

  • 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 变量有效。如果我们在那里建造一座桥，我们总是只能到达一个水广场，因​​此每个水位置(i，j)的y_ijbcn <= x_ij。此外，如果(i，j)不与岛屿b毗邻，则y_ijbc1必须等于0。最后，对于n> 1，仅当在步骤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，要求S中的至少一个孤岛与S的补数中的至少一个孤岛链接，我们将其称为S'。在约束中，我们可以通过为大小为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 map 开始，该 map 底部有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 - - -

    接下来，考虑问题顶部的完整问题，这是一个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

    10-07 22:58
    Powered by LMLPHP ©2024 岛屿 0.025977