Approximation Algorithm for non-intersecting paths

问题:

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

回答1:

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)

回答2:

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.

回答3:

Well, I started out thinking about a brute force algorithm, and I left that below, but it turns out it's actually simpler to search for all answers rather than generate all configurations and test for valid answers. Here's the search code, which ended up looking much like @Brent Washburne's. It runs in 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 doable by brute force if you think about it "backward:" assign all the grid squares to paths and test to see if the assignment is valid. There are 25 grid squares and you need to construct 5 paths, each with 2 endpoints. So you know the paths these 10 points lie on. All that's left is to label the remaining 15 squares with the paths they lie on. There are 5 possibilities for each, so 5^15 in all. That's about 30 billion. All that's left is to build an efficient checker that says whether a given assignment is a set of 5 valid paths. This is simple to do by linear time search. The code below finds your solution in about 2 minutes and takes a bit under 11 minutes to test exhaustively on 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();
  }
}

The starting 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]

The 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]