What is the minimum connection cost for all islands?

Question

There is a grid of size N x M. Some cells are islands marked "0" and others are water. Each cell of water has a number on it, indicating the cost of the bridge made on this cell. You must find the minimum cost that all islands can be linked to. A cell is connected to another cell if it shares an edge or vertex.

What algorithm can be used to solve this problem?
Edit: What can be used as a brute force approach if the values ​​of N, M are very small, say, NxM <= 100?

Example. In this image, green cells indicate islands, blue cells indicate that water and light blue cells indicate cells on which the bridge should be made. So for the next image, the answer will be 17 .

Initially, I thought about designating all the islands as nodes and connected each pair of islands along the shortest bridge. Then the problem can be reduced to a minimal spanning tree, but in this approach I skipped the case where the edges overlap. For example, in the following image, the shortest distance between any two islands is 7 (marked in yellow), so using the minimum distances, the answer will be 14, but the answer should be 11 (marked in blue).

Answer 1

To approach this problem, I would use an integer programming structure and define three sets of solution variables:

• x_ij : binary indicator variable for whether we will build a bridge at the location of the water (i, j).
• y_ijbcn : binary indicator of whether the location of the water (i, j) is the n-th point connecting island b with island c.
• l_bc : a binary indicator variable for binding islands b and c (otherwise you can only walk on the squares of the bridge from b to c).

For the cost of building the bridge c_ij, the target value to minimize is sum_ij c_ij * x_ij . We need to add the following restrictions to the model:

• We need to make sure that the variables y_ijbcn are valid. We can always achieve only the area of ​​water if we build a bridge there, so y_ijbcn <= x_ij for each location of the water (i, j). In addition, y_ijbc1 should be 0 if (i, j) does not border island b. Finally, for n> 1, y_ijbcn can be used only if the neighboring water location was used in step n-1. Defining N(i, j) as neighboring (i, j) squares of water, this is equivalent to y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1) .
• We need to make sure that the variables l_bc are set only if b and c are connected. If we define I(c) as places bordering the island c, this can be done using l_bc <= sum_{(i, j) in I(c), n} y_ijbcn .
• We need to ensure that all islands are connected, directly or indirectly. This can be done as follows: for each nonempty proper subset of S islands, it is required that at least one island in S be associated with at least one island in addition to S, which we will call S '. In the constraints, we can realize this by adding a constraint for each nonempty set S of size <= K / 2 (where K is the number of islands), sum_{b in S} sum_{c in S'} l_bc >= 1 .

For an instance of a problem with islands K, water W cells, and a given maximum path length N, this is a mixed integer programming model with variables O(K^2WN) and constraints O(K^2WN + 2^K) . Obviously, this will become intractable as the size of the problem becomes large, but it can be resolved for the sizes you care about. To get an idea of ​​scalability, I implement it in python using a pulp package. First, start with a smaller 7 x 9 map with three islands at the bottom of the 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 = {} 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 "" 

It takes 1.4 seconds to start using the default solver from the pulp package (CBC solver) and outputs the correct solution:

 II - - - - - II - - B - - - B - - - - - B - B - - - - - - - B - - - - - - - - B - - - - - - - - B - - - - - - - III - - - 

Then consider the complete problem at the top of the question, which is a 13 x 14 grid with 7 islands:

 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 solvers often get good solutions relatively quickly, and then spend a lot of time trying to prove the optimal solution. Using the same decisive code as above, the program does not exit within 30 minutes. However, you can provide a timeout to the solver in order to get an approximate solution:

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

This gives a solution with an objective value of 17:

 II - - - - - II - - IIIII - - - - - II - - - I - II - - - - - I - B - B - - - - B - - - B - - - B - - - - - - B - B - - - - II - - - - - - B - - - - - II - - - - - - - B - - - - - B - - - - - - - B - I - - - - B - - - - - B - III - - B - - II - B - - - I - - - - B - III - - - - - - - - - - BIII - - - - - II - - - II - - - - - - - IIIIII 

To improve the quality of the resulting solutions, you can use a commercial MIP-solver (this is free if you are in an academic institution and most likely not free otherwise). For example, here is the performance of Gurobi 6.0.4, again with a 2-minute time limit (although we read from the solution log that the solver found the current best solution within 7 seconds):

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

It actually finds a solution to an objective value of 16, better than the OP being able to find manually!

 II - - - - - II - - IIIII - - - - - II - - - I - II - - - - - I - B - B - - - - B - - - - - - - B - - - - - - B - - - - - - II - - - - - - B - - - - - II - - - - - - - B - - BB - - - - - - - - - B - I - - B - - - - - - - B - III - - B - - II - B - - - I - - - - B - III - - - - - - - - - - BIII - - - - - II - - - II - - - - - - - IIIIII 

Answer 2

Pseudo-code brute force approach:

 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 

In C ++, this can be written as

 // 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); } 

After the first call (I assume that you will convert 2d cards to 1d arrays for easy copying), bestCost will contain the cost of the best answer, and best will contain the bridge template which gives this. This, however, is very slow.

Optimization:

• Using the "bridge limit" and running the algorithm to increase the maximum number of bridges, you can find the minimum answers without examining the whole tree. The search for a 1-mode answer, if it existed, would be O (nm) instead of O (2 ^ nm) - a drastic improvement.
• You can avoid the search (by stopping the recursion, it is also called "trimming") as soon as you have exceeded bestCost , because there is no point in continuing to keep track of it. If he can’t get better, don’t keep digging.
• The above cropping works better if you look at the “good” candidates before looking at the “bad” ones (since all cells are scanned from left to right, from top to bottom). A good heuristic would be to consider cells that are adjacent to several unrelated components as being higher priority than cells that are not. However, as soon as you add heuristics, your search begins to resemble A * (and you also need a priority queue).
• Duplication of bridges and bridges to nowhere should be avoided. Any bridge that does not disconnect the island network, if removed, is redundant.

A general search algorithm such as A * can significantly speed up the search, although finding the best heuristic is not an easy task. For a more problematic approach, using existing results in Steiner trees , as @Gassa suggests, is the way to go. Note, however, that the problem of constructing Steiner trees on orthogonal meshes is NP-Complete, according to this article by Gary and Johnson .

If enough is enough, the genetic algorithm can quickly find acceptable solutions if you add a few key heuristics regarding the preferred placement of the bridge.

Answer 3

This problem is a variant of the Steiner tree, called the Steiner tree, which means the node specializes in a certain class of graphs. Compact, node is a weighted Steiner tree, given a node is a weighted undirected graph, where some nodes are terminals, find the cheapest set of nodes, including all terminals that induce a connected subgraph. Unfortunately, I cannot find any solvers in some cursory searches.

To formulate it as an integer program, enter a 0-1 variable for each nonterminal node, and then for all subsets of nonterminal nodes whose removal from the initial graph disables two terminals, requires that the sum of the variables in the subset must be at least 1. This leads to too a lot of restrictions, so you have to use them lazily, using an efficient node connection algorithm (maximum flow, mainly) to detect the most violated restriction. Sorry for the lack of details, but it will be painful to implement, even if you are already familiar with the whole programming.

Answer 4

Given that this problem occurs in the grid, and you have well-defined parameters, I would approach the problem of systematically eliminating the problem space by creating a minimum spanning tree. That being said, it makes sense to me if you approach this problem with the Prim algorithm.

Unfortunately, now you are faced with the problem of abstracting the grid to create a set of nodes and edges ... ergo the real problem with this post is how to convert the nxm grid to {V} and {E}

This conversion process is, at first glance, likely NP-Hard due to the large number of possible combinations (assume that all costs for waterways are identical). To handle instances where paths overlap, you should consider creating a virtual island.

When this is done, start Prim Algorithm and you should come up with the best solution.

I do not believe that dynamic programming can be effectively run here because there is no observable optimality principle. If we find the minimum value between the two islands, this does not necessarily mean that we can find the minimum value between these two and the third islands or another subset of islands that will (in my definition, find MST via Prim) be connected.

If you want the code (pseudo one way or another) to convert your grid into a set of {V} and {E}, send me a personal message and I will consider splicing along with the implementation.

Answer 5

I agree that this is a traveling salesman problem, but it can be roughly forced with n = 7. Calculate the minimum cost path between each island and you will only have n (n-1) / 2 solutions = 21 calculation