Approximation Algorithm for non-intersecting paths in a grid

Question

I recently came across this question and thought I could share it here, since I wasn't able to get it.

We are given a 5*5 grid numbered from 1-25, and a set of 5 pairs of points,that are start and end points of a path on the grid.

Now we need to find 5 corresponding paths for the 5 pairs of points, such that no two paths should overlap. Also note that only vertical and horizontal moves are allowed. Also the combined 5 path should cover the entire grid.

For example we are given the pair of points as:

P={1,22},{4,17},{5,18},{9,13},{20,23}

Then the corresponding paths will be

1. 1-6-11-16-21-22
2. 4-3-2-7-12-17
3. 5-10-15-14-19-18
4. 9-8-13
5. 20-25-24-23

What I have thought of so far: Maybe i can compute all paths from source to destination for all pairs of points and then check if there's no common point in the paths. However this seems to be of higher time complexity.

Can anyone propose a better algorithm? I would be glad if one could explain through a pseudo code.Thanks

Answer 1

This problem is essentially the Hamiltonian path/cycle problem problem (since you can connect the end of one path to the start of another, and consider all the five paths as a part of one big cycle). There are no known efficient algorithms for this, as the problem is NP-complete, so you do essentially need to try all possible paths with backtracking (there are fancier algorithms, but they're not much faster).

Your title asks for an approximation algorithm, but this is not an optimization problem - it's not the case that some solutions are better than others; all correct solutions are equally good, and if it isn't correct, then it's completely wrong - so there is no possibility for approximation.

---

Edit: The below is a solution to the original problem posted by the OP, which did not include the "all cells must be covered" constraint. I'm leaving it up for those that might face 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 per grid cell; one "outgoing" node and one "incoming" node. For each adjacent pair of cells, there are edges from the "outgoing" node in either cell to the "incoming" node in the other cell. Within each cell, there is also an edge from the "incoming" to the "outgoing" node. Each edge has the capacity 1. Create one global source node that has an edge to all the start nodes, and one global sink node to which all end nodes have an edge.

Then, run the flow algorithm; the resulting flow shows the non-intersecting paths.

This works because all flow coming in to a cell must pass through the "internal" edge from the "incoming" to the "ougoing" node, and as such, the flow through each cell is limited to 1 - therefore, no paths will intersect. Also, Edmonds-Karp (and all Floyd-Warshall based flow algorithms) will produce integer flows as long as all capacities are integers.

Answer 2

Here's a program written in Python that walks all potential paths. It uses recursion and backtracking to find the paths, and it marks a grid to see which locations are already being used.

One key optimization is that it marks the start and end points on the grid (10 of the 25 points).

Another optimization is that it generates all moves from each point before starting the "walk" across the grid. For example, from point 1 the moves are to points 2 & 6; from point 7, the moves are to points 2, 6, 8 & 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)