Approximation algorithm for disjoint paths in a grid
I recently came across this question and thought I could share it here as I was unable to get it.
We are given a 5 * 5 grid, numbered from 1-25, and a set of 5 pairs of points that are the start and end points of the path on the grid.
Now we need to find 5 matching paths for 5 pairs of points so that no two paths should overlap. Also note that only vertical and horizontal movements are allowed. Also, the combined 5 path should cover the entire grid.
For example, we are assigned a pair of points as:
P={1,22},{4,17},{5,18},{9,13},{20,23}
Then the corresponding paths will be
-
1-6-11-16-21-22
-
4-3-2-7-12-17
-
5-10-15-14-19-18
-
9-8-13
-
20-25-24-23
What I've been thinking so far: Perhaps I can compute all the paths from source to destination for all point pairs and then check if there is a common point in the paths. However, this seems to have a higher time complexity.
Can anyone suggest a better algorithm? I would be glad if it could be explained with pseudocode. thank
source to share
Here's a Python program that looks at all potential paths. It uses recursion and backtrace to find paths and marks the grid to see which locations are already in use.
One of the key optimizations is that it marks the start and end points of the grid (10 out of 25 points).
Another optimization is that it generates all moves from each point before starting to "walk" the grid. For example, from point 1 the displacements refer to points 2 and 6; from point 7, the displacements refer to points 2, 6, 8, and 12.
points = [(1,22), (4,17), (5,18), (9,13), (20,23)]
paths = []
# find all moves from each position 0-25
moves = [None] # set position 0 with None
for i in range(1,26):
m = []
if i % 5 != 0: # move right
m.append(i+1)
if i % 5 != 1: # move left
m.append(i-1)
if i > 5: # move up
m.append(i-5)
if i < 21: # move down
m.append(i+5)
moves.append(m)
# Recursive function to walk path 'p' from 'start' to 'end'
def walk(p, start, end):
for m in moves[start]: # try all moves from this point
paths[p].append(m) # keep track of our path
if m == end: # reached the end point for this path?
if p+1 == len(points): # no more paths?
if None not in grid[1:]: # full coverage?
print
for i,path in enumerate(paths):
print "%d." % (i+1), '-'.join(map(str, path))
else:
_start, _end = points[p+1] # now try to walk the next path
walk(p+1, _start, _end)
elif grid[m] is None: # can we walk onto the next grid spot?
grid[m] = p # mark this spot as taken
walk(p, m, end)
grid[m] = None # unmark this spot
paths[p].pop() # backtrack on this path
grid = [None for i in range(26)] # initialize the grid as empty points
for p in range(len(points)):
start, end = points[p]
paths.append([start]) # initialize path with its starting point
grid[start] = grid[end] = p # optimization: pre-set the known points
start, end = points[0]
walk(0, start, end)
source to share
This problem is essentially a Hamiltonian path / loop problem (since you can connect the end of one path to the beginning of another, and consider all five paths as part of one large loop). There are no known efficient algorithms for this as the problem is NP-complete, so you really need to try all possible backtrace paths (there are more interesting algorithms, but they are not much faster).
Your name requires an approximation algorithm, but this is not an optimization problem - this is not a case where some solutions are better than others; all correct solutions are equally good, and if this is not true, then it is completely wrong - therefore there is no room for approximation.
Edit: Below is a solution to the original problem posted by the OP that doesn't include the "all cells must be covered" constraint. I leave this for those who may be facing the original problem.
This can be solved with a maximum flow algorithm such as Edmonds-Karp .
The trick is to model the grid as a graph, where there are two nodes for each cell in the cell; one "outgoing" node and one "incoming" node. For each adjacent pair of cells, there are faces from an "outgoing" node in any cell to an "incoming" node in another cell. Within each cell there is also an edge from the "inbound" to the "outbound" node. Each edge has a capacity of 1. Create one global source node that has an edge for all start nodes and one global sink node to which all end nodes have an edge.
Then start the flow algorithm; the resulting stream shows non-intersecting paths.
This works because all flow entering a cell must pass through the "inner" edge from the "inbound" to the "ougoing" node, and thus the flow through each cell is limited to 1 - so no paths cross. Additionally, Edmonds-Karp (and all Floyd-Warshall based flow algorithms) will generate integer streams if all capacities are integers.
source to share
Well, I started thinking about a brute force algorithm and I left that below, but it turns out that it is actually easier to search for all the answers rather than generating all the configurations and checking for the correct answers. Here's a search code that turned out to be very similar to @Brent Washburne's. It works after 53 milliseconds on my laptop.
import java.util.Arrays;
class Puzzle {
final int path[][];
final int grid[] = new int[25];
Puzzle(int[][] path) {
// Make the path endpoints 0-based for Java arrays.
this.path = Arrays.asList(path).stream().map(pair -> {
return new int[] { pair[0] - 1, pair[1] - 1 };
}).toArray(int[][]::new);
}
void print() {
System.out.println();
for (int i = 0; i < grid.length; i += 5)
System.out.println(
Arrays.toString(Arrays.copyOfRange(grid, i, i + 5)));
}
void findPaths(int ip, int i) {
if (grid[i] != -1) return; // backtrack
grid[i] = ip; // mark visited
if(i == path[ip][1]) // path complete
if (ip < path.length - 1) findPaths(ip + 1, path[ip + 1][0]); // find next path
else print(); // solution complete
else { // continue with current path
if (i < 20) findPaths(ip, i + 5);
if (i > 4) findPaths(ip, i - 5);
if (i % 5 < 4) findPaths(ip, i + 1);
if (i % 5 > 0) findPaths(ip, i - 1);
}
grid[i] = -1; // unmark
}
void solve() {
Arrays.fill(grid, -1);
findPaths(0, path[0][0]);
}
public static void main(String[] args) {
new Puzzle(new int[][]{{1, 22}, {4, 17}, {5, 18}, {9, 13}, {20, 23}}).solve();
}
}
Old, bad answer
This problem is handled by brute force if you think backward: assign all the grid squares to the paths and test to make sure the assignment is valid. There are 25 grid squares and you need to build 5 paths, each with two endpoints. This means that you know the paths on which these 10 points lie. All that is left is to mark the remaining 15 squares with the paths on which they lie. There are 5 possibilities for each of them, so only 5 ^ 15. That's about 30 billion. All that's left is to create an efficient check that says if the given job is 5 valid paths. It's easy to do this with a linear time search. The code below finds your solution in about 2 minutes and takes just under 11 minutes to fully test my MacBook:
import java.util.Arrays;
public class Hacking {
static class Puzzle {
final int path[][];
final int grid[] = new int[25];
Puzzle(int[][] path) { this.path = path; }
void print() {
System.out.println();
for (int i = 0; i < grid.length; i += 5)
System.out.println(
Arrays.toString(Arrays.copyOfRange(grid, i, i + 5)));
}
boolean trace(int p, int i, int goal) {
if (grid[i] != p) return false;
grid[i] = -1; // mark visited
boolean rtn =
i == goal ? !Arrays.asList(grid).contains(p) : nsew(p, i, goal);
grid[i] = p; // unmark
return rtn;
}
boolean nsew(int p, int i, int goal) {
if (i < 20 && trace(p, i + 5, goal)) return true;
if (i > 4 && trace(p, i - 5, goal)) return true;
if (i % 5 < 4 && trace(p, i + 1, goal)) return true;
if (i % 5 > 0 && trace(p, i - 1, goal)) return true;
return false;
}
void test() {
for (int ip = 0; ip < path.length; ip++)
if (!trace(ip, path[ip][0] - 1, path[ip][1] - 1)) return;
print();
}
void enumerate(int i) {
if (i == grid.length) test();
else if (grid[i] != -1) enumerate(i + 1); // already known
else {
for (int ip = 0; ip < 5; ip++) {
grid[i] = ip;
enumerate(i + 1);
}
grid[i] = -1;
}
}
void solve() {
Arrays.fill(grid, -1);
for (int ip = 0; ip < path.length; ip++)
grid[path[ip][0] - 1] = grid[path[ip][1] - 1] = ip;
enumerate(0);
}
}
public static void main(String[] args) {
new Puzzle(new int[][]{{1, 22}, {4, 17}, {5, 18}, {9, 13}, {20, 23}}).solve();
}
}
Initial array:
[ 0, -1, -1, 1, 2]
[-1, -1, -1, 3, -1]
[-1, -1, 3, -1, -1]
[-1, 1, 2, -1, 4]
[-1, 0, 4, -1, -1]
Result:
[ 0, 1, 1, 1, 2]
[ 0, 1, 3, 3, 2]
[ 0, 1, 3, 2, 2]
[ 0, 1, 2, 2, 4]
[ 0, 0, 4, 4, 4]
source to share