在网格中求解非交路径的近似算法

Question

我最近遇到了这个问题，觉得我可以在这里分享一下，因为我自己也没搞定。

我们有一个从1到25编号的5*5网格，和5对点的集合，它们是路径在网格上的起始点和终止点。

现在我们需要找到5条相应的路径，满足没有任何两条路径重叠。同时请注意，只允许垂直和水平移动。 此外，这5条路径组合必须覆盖整个网格。

例如，我们有以下点对：

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

对应的路径将会是：

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

我目前想到的方法是：计算源点到目标点的所有路径，然后检查路径中是否有重复的点。不过这种方法时间复杂度较高。

是否有人能提出更好的算法呢？如果可以的话，请用伪代码解释。谢谢！

- user3907480

---

查看移动国王的棋步算法。 - SteveFerg

是的，我听说过那个，但那只是为了保护国王安全。然而，在我看来，这是不同的。 - user3907480

Answer 1

这个问题本质上是哈密顿路径/回路问题问题（因为你可以将一个路径的末尾连接到另一个路径的开头，并将所有五条路径视为一个大循环的一部分）。由于该问题是NP完全问题，因此没有已知的高效算法可用，因此您需要使用回溯尝试所有可能的路径（有更高级的算法，但它们并不快多少）。

您的标题要求近似算法，但这不是优化问题-并非某些解决方案比其他解决方案更好；所有正确的解决方案都同样好，如果不正确，则完全错误-因此不存在近似的可能性。

---

编辑：以下是对原始问题的解决方案，该问题由OP发布，其中不包括“必须覆盖所有单元格”的约束条件。我将其保留下来，供那些可能面临原始问题的人使用。

这可以通过最大流算法解决，例如Edmonds-Karp。

诀窍是将网格建模为一个图形，其中每个网格单元格有两个节点；一个“出站”节点和一个“进站”节点。对于每个相邻的单元格对，从任一单元格的“出站”节点到另一个单元格的“进站”节点都有边缘。在每个单元格内，还存在从“进站”到“出站”节点的边缘。每条边缘的容量为1。创建一个全局源节点，该节点与所有起始节点连接，并创建一个全局汇节点，所有结束节点都与其相连。

然后，运行流算法；结果流显示不相交的路径。

这是因为所有进入单元格的流量都必须通过从“传入”到“传出”节点的“内部”边缘，因此，每个单元格中的流量都被限制为1-因此，没有路径会相交。此外，只要所有容量都是整数，Edmonds-Karp（以及所有基于Floyd-Warshall的流算法）将产生整数流量。

- Aasmund Eldhuset

---

我知道如何在图中找到最大流量。但是如何寻找所有的流路径呢？你能否帮我写一个可行的代码吗？ - user3907480

在对应于流的有向图中进行深度优先搜索。每次处理一对终端，通过选择的路径减少流量。 - David Eisenstat

我在粗体语句中进行了编辑。我认为您的算法现在不起作用。 - user3907480

@user3907480：确实，那个问题完全不同。 - Aasmund Eldhuset

@AasmundEldhuset 你能帮我写一个可行的代码来组合五个路径以形成一条大汉密尔顿路径吗？最好用C++/ Java。谢谢 - user3907480

@user3907480：抱歉，我现在没有时间。此外，我希望你能更加努力，因为你的问题听起来像是想让我们替你完成作业（大多数SO用户不喜欢被当做代码编写服务）。请先自己尝试解决问题（即使是简单的问题，比如从一个起始单元格到一个结束单元格找到哈密顿路径），展示你的代码，并就你卡住的地方提出具体问题。 - Aasmund Eldhuset

Answer 2

以下是关于使用Python编写的程序，可以遍历所有可能的路径。该程序使用递归和回溯来查找路径，并标记一个网格以查看哪些位置已经被使用。

此外，其中一个关键优化是在网格上标记起点和终点（25个点中的前10个点）。

另一项优化是在开始“行走”穿过网格之前，生成每个点的所有移动方式。例如，从点1出发，移动到点2和6；从点7出发，移动到点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)

- Brent Washburne

---

嗨。谢谢。那真是太有帮助了。非常抱歉，但我忘记了一个要点，现在被告知的是，当组合时，路径应覆盖网格上的所有点。您的代码在此示例中实现了这一点，并且看起来在所有情况下都是如此。是吗？ - user3907480

我已经为样例输入进行了检查。它不能确保整个网格的覆盖。http://ideone.com/RPGUOm - user3907480

我已增加了一个完全覆盖的检查，请再试一次。 - Brent Washburne

现在它将找到所有提供完全覆盖的工作路径集合。 - Brent Washburne

Answer 3

起初，我考虑使用暴力算法，并在下面留下了它的代码，但事实证明搜索所有答案比生成所有配置并测试有效答案更加简单。这是搜索代码，最终看起来非常像@Brent Washburne的代码。在我的笔记本上运行时间为53毫秒。

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

旧的、不好的答案

如果你反向思考，将所有的网格方块分配到路径上并测试分配是否有效，这个问题就可以通过暴力方法解决。总共有25个网格方块，需要构建5条路径，每条路径有2个端点。因此，你知道这10个点所在的路径。剩下的15个方块只需标记它们所在的路径即可。每个方块有5种可能性，因此总共有5^15种情况。这大约是300亿。接下来要做的就是构建一个高效的检查器，判断给定的分配是否为一组5条有效路径。这可以通过线性时间搜索轻松完成。下面的代码可以在我的 MacBook 上大约2分钟内找到你的解决方案，并在不到11分钟的时间内进行全面测试：

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

起始数组：

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

结果：

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

- Gene