use*_*480 3 algorithm approximation graph-algorithm
我最近遇到了这个问题，并认为我可以在这里分享，因为我无法得到它。
我们得到一个编号为 1-25 的 5*5 网格，以及一组 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到目前为止我想到的是：也许我可以计算所有点对从源到目标的所有路径，然后检查路径中是否没有公共点。然而，这似乎具有更高的时间复杂度。
谁能提出更好的算法？如果有人可以通过伪代码解释，我会很高兴。谢谢
这个问题本质上是哈密顿路径/循环问题（因为您可以将一条路径的末端连接到另一条路径的起点，并将所有 5 条路径视为一个大循环的一部分）。没有已知的有效算法，因为问题是 NP 完全的，因此您本质上需要尝试所有可能的回溯路径（有更高级的算法，但它们并没有快多少）。
您的标题要求使用近似算法，但这不是优化问题 - 并非某些解决方案比其他解决方案更好；所有正确的解决方案都同样好，如果它不正确，那就是完全错误的——所以没有近似的可能性。
编辑：以下是 OP 发布的原始问题的解决方案，其中不包括“必须覆盖所有单元格”约束。我把它留给那些可能面临原始问题的人。
这可以通过最大流算法解决，例如Edmonds-Karp。
诀窍是将网格建模为一个图形，其中每个网格单元有两个节点；一个“传出”节点和一个“传入”节点。对于每对相邻的单元格，从任一单元格中的“传出”节点到另一个单元格中的“传入”节点都有边。在每个单元格内，还有一条从“传入”节点到“传出”节点的边。每条边的容量为 1。创建一个全局源节点，该源节点与所有起始节点都有一条边，以及一个全局汇节点，所有结束节点都具有一条边。
然后，运行流算法；结果流显示了不相交的路径。
这是有效的，因为进入单元格的所有流都必须通过从“传入”节点到“输出”节点的“内部”边缘，因此，通过每个单元格的流量限制为 1 - 因此，没有路径相交. 此外，只要所有容量都是整数，Edmonds-Karp（以及所有基于 Floyd-Warshall 的流算法）将产生整数流。