algorithm - 网格中非相交路径的近似算法

Question

我最近遇到了这个问题，我想我可以在这里分享它，因为我无法得到它。

我们有一个 5*5 的网格，编号为 1-25，以及一组 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

到目前为止我想到的是: 也许我可以为所有点对计算从源到目的地的所有路径，然后检查路径中是否没有公共(public)点。然而，这似乎具有更高的时间复杂度。

谁能提出更好的算法？如果有人可以通过伪代码进行解释，我将很高兴。谢谢

Answer 1

这个问题本质上是Hamiltonian path/cycle problem问题(因为您可以将一条路径的终点连接到另一条路径的起点，并将所有五条路径视为一个大循环的一部分)。对此没有已知的有效算法，因为问题是 NP 完全问题，所以您基本上需要尝试所有可能的回溯路径(有更高级的算法，但它们并没有快多少)。

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

---

编辑:以下是 OP 发布的原始问题的解决方案，其中不包括“必须覆盖所有单元格”约束。我将它留给那些可能面临原始问题的人。

这可以用最大流算法来解决，比如Edmonds-Karp .

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

然后，运行流算法；生成的流程显示了非交叉路径。

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