中国邮递员或路线检查问题

中国邮递员问题或路线检查问题是一种欧拉回路问题，它在无向图中找到最短的闭合路径，使得每条边至少被访问一次。这个问题在邮递员需要向城市中的每条街道投递邮件时也非常相关，其目标是找到覆盖每条街道至少一次的最优路线。

路线检查问题

通过网络检查获得遍历网络所有节点的最短路径。

路线检查问题的目的是什么？

中国邮递员问题，也称为邮递员巡回，旨在找到完全遍历无向（连通）图所有边的最小闭合巡回路径。

问题陈述

给定一个无向图，任务是找到访问所有顶点或边至少一次的最短循环路径。

算法

中国邮递员算法

1. 输入
   • 读取n（顶点数）和m（边数）。
   • 设置邻接矩阵a、距离矩阵d和度数组deg。
   • 总和初始为0。
2. 图初始化
   • 将矩阵a的所有元素设置为无穷大（INF）。
   • 对于每条边(x, y, c)
   • 对于每条边(x, y, c)
   • x和y递减1（用于0基索引）。
   • 通过取最小值并等于c来更新a[x][y]和a[y][x]。
   • 将deg[x]和deg[y]递增1。
3. 深度优先搜索 (DFS)
   • 设置一个布尔型标记数组mark，用于跟踪已访问的顶点。
   • 通过调用dfs(0)开始深度优先搜索顶点0。
   • 检查是否有任何顶点未被访问（mark[i] > 0）且度为正（degree[i] > 0）。如果为真，则denied将为真。
4. 图连通性检查
   • 如果这是不好的 - 输出-1并退出，否则继续。
5. Floyd-Warshall 算法
   • 将矩阵a复制到矩阵d。
   • 利用Floyd Warshall算法查找d矩阵中每对顶点之间的最短距离。
6. 记忆化初始化
   • 初始化一个长度为2^15的mem数组，其中所有元素都设置为-1。
7. 动态规划（递归）
   • 定义一个递归函数rec(mask)来找到最佳路径成本。
   • 应用记忆化来存储和调用已预先计算的结果。
8. 构建初始掩码
   • 从一个奇数度顶点的掩码开始（mask |= (1 << i) for i & |mask）。
9. 计算结果
   • 计算结果，等于原始总和与rec(mask)结果的总和。
10. 输出
    • 在最终表格上打印结果。

代码实现（Java）

说明

1. 输入处理：代码接收n和m作为输入，它们分别是顶点数和边数，然后初始化邻接矩阵a、距离矩阵d以及数组deg和mark。
2. 边输入：代码处理边及其成本，定性地更新邻接矩阵a并计算最终成本。
3. DFS检查连通性：这使用DFS（深度优先搜索）来确定图是否连通。如果没有顶点被标记且度为正，则图不连通。
4. Floyd-Warshall算法：Floyd-Warshall算法用于找出所有顶点对之间的距离，该值存储在矩阵d中。
5. 带位掩码的动态规划（DP）：DP计算中应用位掩码技术来找到最便宜的路线，这意味着可以记录已访问的顶点。
6. 输出：现在我们确定结果，即所有成本的总和和DP函数的最小值。如果原始图不连通，则返回-1。

时间复杂度

• DFS在图上执行一次（时间复杂度为O(n + m)，其中n是顶点数，m是边数）。
• 用嵌套循环编写的Floyd-Warshall算法的时间复杂度为O(n^3)，其中n是顶点数。
• 函数rec使用动态规划技术和位掩码状态进行记忆化。在最复杂的情况下，最多有2^n个状态，并且为每个状态计算递推关系。因此，DP部分的时间复杂度变为O(2^n * n^2)。
• 主要因素是动态规划部分，因此总时间复杂度为O(2^n * n^2)。

空间复杂度

• 邻接矩阵a和距离矩阵d都将占用O(n^2)空间，其中n是顶点数。
• 存储deg数组、mark数组和mem数组的空间复杂度为O(n)。
• 输入变量、临时变量和循环索引的空间复杂度为O(1)。
• 最重要的是矩阵使用的空间，因此总复杂度为O(n^2)。

应用

除了邮件投递之外，中国邮递员问题的一些应用还包括网络优化、车辆路径规划和电路设计。解决这个问题提供了有关为各种现实生活场景制定高效运输路线的信息，这些场景中所有边都必须被覆盖并且资源必须得到有效利用。

结论

图着色算法基于中国邮递员问题或路线检查问题。该问题的主要目标是找到最短的循环路径，该路径至少访问无向图的所有边一次。此问题出现在构建邮件投递路线或网络检查等情况中。