algorithm - What is the minimum cost to connect all the islands? -

there grid of size n x m. cells islands denoted '0' , others water. each water cell has number on denoting cost of bridge made on cell. have find minimum cost islands can connected. cell connected cell if shares edge or vertex.

what algorithm can used solve problem ?
edit: can used brute force approach if values of n, m small, nxm <= 100?

example: in given image, green cells indicate islands, blue cells indicate water , light blue cells indicate cells on bridge should made. following image, answer 17.

initially thought of marking islands nodes , connecting every pair of islands shortest bridge. problem reduced minimum spanning tree, in approach missed case edges overlapping. for example, in following image, shortest distance between 2 islands 7(marked in yellow), using minimum spanning trees answer 14, answer should 11 (marked in light blue).

to approach problem, use integer programming framework , define 3 sets of decision variables:

• x_ij: binary indicator variable whether build bridge @ water location (i, j).
• y_ijbcn: binary indicator whether water location (i, j) n^th location linking island b island c.
• l_bc: binary indicator variable whether islands b , c directly linked (aka can walk on bridge squares b c).

for bridge building costs c_ij, objective value minimize sum_ij c_ij * x_ij. need add following constraints model:

• we need ensure y_ijbcn variables valid. can reach water square if build bridge there, y_ijbcn <= x_ij every water location (i, j). further, y_ijbc1 must equal 0 if (i, j) not border island b. finally, n > 1, y_ijbcn can used if neighboring water location used in step n-1. defining n(i, j) water squares neighboring (i, j), equivalent y_ijbcn <= sum_{(l, m) in n(i, j)} y_lmbc(n-1).
• we need ensure l_bc variables set if b , c linked. if define i(c) locations bordering island c, can accomplished l_bc <= sum_{(i, j) in i(c), n} y_ijbcn.
• we need ensure islands linked, either directly or indirectly. can accomplished in following way: every non-empty proper subset s of islands, require @ least 1 island in s linked @ least 1 island in complement of s, we'll call s'. in constraints, can implement adding constraint every non-empty set s of size <= k/2 (where k number of islands), sum_{b in s} sum_{c in s'} l_bc >= 1.

for problem instance k islands, w water squares, , specified maximum path length n, mixed integer programming model o(k^2wn) variables , o(k^2wn + 2^k) constraints. become intractable problem size becomes large, may solvable sizes care about. sense of scalability, i'll implement in python using pulp package. let's first start smaller 7 x 9 map 3 islands @ bottom of question:

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 = {} k in islands:     iborders[k] = {}     i, j in islands[k]:         dx in [-1, 0, 1]:             dy in [-1, 0, 1]:                 if (i+dx, j+dy) in water:                     iborders[k][(i+dx, j+dy)] = true  # create models specified variables x = pulp.lpvariable.dicts("x", water.keys(), lowbound=0, upbound=1, cat=pulp.lpinteger) pairs = [(b, c) b in islands c in islands if b < c] yvals = [] i, j in water:     b, c in pairs:         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] k in water])  # valid y k in yvals:     i, j, b, c, n = k     mod += y[k] <= x[(i, j)]     if n == 0 , 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)] dx in [-1, 0, 1] dy in [-1, 0, 1] if (i+dx, j+dy) in water])  # valid l b, c in pairs:     mod += l[(b, c)] <= sum([y[(i, j, b, c, n)] i, j, b, c, n in yvals if (i, j) in iborders[c] , b==b , c==c])  # islands connected (directly or indirectly) ikeys = islands.keys() size in range(1, len(ikeys)/2+1):     s in itertools.combinations(ikeys, size):         thissubset = {m: true m in s}         sprime = [m m in ikeys if not m in thissubset]         mod += sum([l[(min(b, c), max(b, c))] b in s c in sprime]) >= 1  # solve , output mod.solve() row in range(min([m[0] m in water]), max([m[0] m in water])+1):     col in range(min([m[1] m in water]), max([m[1] m in water])+1):         if (row, col) in water:             if x[(row, col)].value() > 0.999:                 print "b",             else:                 print "-",         else:             print "i",     print "" 

this takes 1.4 seconds run using default solver pulp package (the cbc solver) , outputs correct solution:

i - - - - - i  - - b - - - b - -  - - - b - b - - -  - - - - b - - - -  - - - - b - - - -  - - - - b - - - -  - - - i - - -  

next, consider full problem @ top of question, 13 x 14 grid 7 islands:

water = {(i, j): 1.0 in range(13) 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)]} k in islands:     i, j in islands[k]:         del water[(i, j)]  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 solvers obtain solutions relatively , spend huge of time trying prove optimality of solution. using same solver code above, program not complete within 30 minutes. however, can provide timeout solver approximate solution:

mod.solve(pulp.solvers.pulp_cbc_cmd(maxseconds=120)) 

this yields solution objective value 17:

i - - - - - i - - i  i - - - - - i - - - -  i - - - - - - b - b - -  - - b - - - b - - - b - - -  - - - b - b - - - - i - -  - - - - b - - - - - i - -  - - - - - b - - - - - b - -  - - - - - b - - - - - b -  - - - - b - i - - b - -  i - b - - - - - - - b -  i - - - - - - - - - - b  i - - - - - i - - -  - - - - - - - i i i  

to improve quality of solutions obtain, use commercial mip solver (this free if @ academic institution , not free otherwise). instance, here's performance of gurobi 6.0.4, again 2-minute time limit (though solution log read solver found current best solution within 7 seconds):

mod.solve(pulp.solvers.gurobi(timelimit=120)) 

this finds solution of objective value 16, 1 better op able find hand!

i - - - - - i - - i  i - - - - - i - - - -  i - - - - - - b - b - -  - - b - - - - - - - b - - -  - - - b - - - - - - i - -  - - - - b - - - - - i - -  - - - - - b - - b b - - - -  - - - - - b - - - b - - -  - - - - b - i - - b - -  i - b - - - - - - - b -  i - - - - - - - - - - b  i - - - - - i - - -  - - - - - - - i i i