网格中非相交路径的近似算法
Approximation Algorithm for non-intersecting paths in a grid
我最近遇到了这个问题，我想我可以在这里分享它，因为我无法得到它。
给定一个 5*5 的网格，编号为 1-25，以及一组 5 对点，它们是网格上路径的起点和终点。
现在我们需要为5对点找到5条对应的路径，使得两条路径不应该重叠。另请注意，仅允许垂直和水平移动。 此外，5 条组合路径应覆盖整个网格。
例如，我们得到的点对为：
P={1,22},{4,17},{5,18},{9,13},{20,23}
那么对应的路径就是
1-6-11-16-21-224-3-2-7-12-175-10-15-14-19-189-8-1320-25-24-23
到目前为止我想到的是：
也许我可以为所有点对计算从源到目的地的所有路径，然后检查路径中是否没有公共点。然而这似乎具有更高的时间复杂度。
谁能提出更好的算法？如果有人可以通过伪 code.Thanks
来解释，我会很高兴
这个问题本质上是 Hamiltonian path/cycle problem 问题（因为您可以将一条路径的终点连接到另一条路径的起点，并将所有五条路径视为一个大循环的一部分）。没有已知的有效算法，因为问题是NP-complete，所以你基本上需要尝试所有可能的回溯路径（有更高级的算法，但它们并没有快多少）。
您的标题要求近似算法，但这不是优化问题 - 并不是某些解决方案比其他解决方案更好；所有正确的解决方案都同样好，如果不正确，那就是完全错误的-因此没有近似的可能性。
编辑：以下是 OP 发布的原始问题的解决方案，其中不包括 "all cells must be covered" 约束。我将它留给那些可能面临原始问题的人。
这个可以用最大流算法解决，比如Edmonds-Karp。
诀窍是将网格建模为图形，其中每个网格单元有两个节点；一个 "outgoing" 节点和一个 "incoming" 节点。对于每对相邻的单元格，存在从任一单元格中的 "outgoing" 节点到另一个单元格中的 "incoming" 节点的边。在每个单元格中，还有一条从 "incoming" 到 "outgoing" 节点的边。每条边的容量为 1. 创建一个全局源节点到所有起始节点的边，以及一个全局汇节点到所有结束节点的边。
然后，运行流算法；结果流显示 non-intersecting 路径。
这是可行的，因为所有进入单元格的流量都必须通过 "internal" 边缘从 "incoming" 到 "ougoing" 节点，因此，流经每个单元格限制为 1 - 因此，没有路径会相交。此外，只要所有容量都是整数，Edmonds-Karp（以及所有基于 Floyd-Warshall 的流算法）将生成整数流。
这是一个用 Python 编写的程序，它遍历所有可能的路径。它使用递归和回溯来查找路径，并标记一个网格以查看哪些位置已被使用。
一个关键的优化是它在网格上标记了起点和终点（25 个点中的 10 个）。
另一个优化是它在开始 "walk" 跨网格之前从每个点生成所有移动。例如，从点 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 的。它在我的笔记本电脑上运行 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();
}
}
旧的错误答案
如果你考虑一下，这个问题是可以通过蛮力解决的 "backward:" 将所有网格方块分配给路径并测试分配是否有效。有 25 个方格，需要构建 5 条路径，每条路径有 2 个端点。所以你知道这 10 个点所在的路径。剩下的就是用它们所在的路径标记剩余的 15 个方块。每种都有 5 种可能性，所以总共有 5^15。也就是300亿左右。剩下的就是构建一个高效的检查器，说明给定的分配是否是一组 5 条有效路径。这通过线性时间搜索很容易做到。下面的代码在大约 2 分钟内找到了您的解决方案，并在我的 MacBook 上进行了详尽的测试，花费了不到 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]
我最近遇到了这个问题，我想我可以在这里分享它，因为我无法得到它。
给定一个 5*5 的网格，编号为 1-25，以及一组 5 对点，它们是网格上路径的起点和终点。
现在我们需要为5对点找到5条对应的路径，使得两条路径不应该重叠。另请注意，仅允许垂直和水平移动。 此外，5 条组合路径应覆盖整个网格。
例如，我们得到的点对为：
P={1,22},{4,17},{5,18},{9,13},{20,23}
那么对应的路径就是
1-6-11-16-21-224-3-2-7-12-175-10-15-14-19-189-8-1320-25-24-23
到目前为止我想到的是： 也许我可以为所有点对计算从源到目的地的所有路径，然后检查路径中是否没有公共点。然而这似乎具有更高的时间复杂度。
谁能提出更好的算法？如果有人可以通过伪 code.Thanks
来解释，我会很高兴这个问题本质上是 Hamiltonian path/cycle problem 问题（因为您可以将一条路径的终点连接到另一条路径的起点，并将所有五条路径视为一个大循环的一部分）。没有已知的有效算法，因为问题是NP-complete，所以你基本上需要尝试所有可能的回溯路径（有更高级的算法，但它们并没有快多少）。
您的标题要求近似算法，但这不是优化问题 - 并不是某些解决方案比其他解决方案更好；所有正确的解决方案都同样好，如果不正确，那就是完全错误的-因此没有近似的可能性。
编辑：以下是 OP 发布的原始问题的解决方案，其中不包括 "all cells must be covered" 约束。我将它留给那些可能面临原始问题的人。
这个可以用最大流算法解决，比如Edmonds-Karp。
诀窍是将网格建模为图形，其中每个网格单元有两个节点；一个 "outgoing" 节点和一个 "incoming" 节点。对于每对相邻的单元格，存在从任一单元格中的 "outgoing" 节点到另一个单元格中的 "incoming" 节点的边。在每个单元格中，还有一条从 "incoming" 到 "outgoing" 节点的边。每条边的容量为 1. 创建一个全局源节点到所有起始节点的边，以及一个全局汇节点到所有结束节点的边。
然后，运行流算法；结果流显示 non-intersecting 路径。
这是可行的，因为所有进入单元格的流量都必须通过 "internal" 边缘从 "incoming" 到 "ougoing" 节点，因此，流经每个单元格限制为 1 - 因此，没有路径会相交。此外，只要所有容量都是整数，Edmonds-Karp（以及所有基于 Floyd-Warshall 的流算法）将生成整数流。
这是一个用 Python 编写的程序，它遍历所有可能的路径。它使用递归和回溯来查找路径，并标记一个网格以查看哪些位置已被使用。
一个关键的优化是它在网格上标记了起点和终点（25 个点中的 10 个）。
另一个优化是它在开始 "walk" 跨网格之前从每个点生成所有移动。例如，从点 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 的。它在我的笔记本电脑上运行 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();
}
}
旧的错误答案
如果你考虑一下，这个问题是可以通过蛮力解决的 "backward:" 将所有网格方块分配给路径并测试分配是否有效。有 25 个方格，需要构建 5 条路径，每条路径有 2 个端点。所以你知道这 10 个点所在的路径。剩下的就是用它们所在的路径标记剩余的 15 个方块。每种都有 5 种可能性，所以总共有 5^15。也就是300亿左右。剩下的就是构建一个高效的检查器，说明给定的分配是否是一组 5 条有效路径。这通过线性时间搜索很容易做到。下面的代码在大约 2 分钟内找到了您的解决方案，并在我的 MacBook 上进行了详尽的测试，花费了不到 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]