C 语言旅行商问题

旅行商问题 (TSP) 是 数学 和 计算机科学 领域一个著名的优化问题。可以这样描述：找到一条访问每个城市恰好一次的 最短路径，计算每对城市之间的 旅行距离，然后 返回 起始城市。这个问题有许多实际应用，包括 物流规划、电路设计 和 车辆路径规划。在本文中，我们将探讨如何使用 动态规划 来解决 C 语言中的 旅行商问题，并提供一个示例程序及其结果。

使用动态规划解决旅行商问题 (TSP)

动态规划 是一种强大的工具，通过将优化问题分解成更小的 子问题 并存储这些 子问题 的解来避免重复计算，从而解决优化问题。可以使用下面列出的步骤通过 动态规划 来解决 TSP：

子问题定义

现在我们来定义我们的 子问题：dp[mask][i]，其中 'mask' 是一个二进制数，表示已访问城市的集合，'i' 表示 当前城市。dp[mask][i] 的值将是在 “mask” 中访问了所有城市并最终停留在城市 “i” 的 最低成本。

基本情况

当 'mask' 只包含 一个城市 时（即 'mask' 的二进制 编码 中只有一个 位 被设置为 1），将 dp[mask][i] 初始化为一个很大的值（表示无穷大）。

递推关系

对于每个 子问题 dp[mask][i]，遍历所有不在 'mask' 中的城市 'j'，并计算从 'mask' 中已访问过的任何城市 'k' 前往城市 'j' 的成本。将 最低成本 添加到 dp[mask | (1 << j)][j] 中。

最终答案

最终答案 将是 dp[(1 << n) - 1][i] 的最小值，其中 'n' 是城市总数。

递归方程

动态规划解决 TSP 的 递归方程 如下：

dp[mask][i] = min(dp[mask ^ (1 << j)][j] + cost[i][j]) 对于所有不在 mask 中的 j。

在此，cost[i][j] 表示城市 'i' 和 'j' 之间的距离。

dp[mask][i]: 它表示从城市 “i” 开始，访问二进制掩码 “mask” 中列出的所有城市的 最低成本。'mask' 是一个二进制数，如果城市 j 已被访问，则第 j 位设置为 1，否则为 0。

mask ^ (1 << j): 通过翻转 “mask” 中的第 j 位，此表达式创建了一个新的 mask，并有效地将城市 “j” 标记为已访问。这是通过将 左移操作 与 异或运算符 () 结合来实现的。

从城市 'i' 到城市 'j' 的旅行成本是 cost[i][j]。它从成本矩阵中获取，该矩阵包含每对城市之间的旅行时间。

时间复杂度

动态规划 方法，其中 'n' 是城市数量，解决 TSP 的时间复杂度为 O(n^2 * 2^n)。这是因为有 2^n 种可能的 城市 子集，并且我们必须为每个子集遍历 'n' 个城市才能确定最低成本。

示例

下面是一个 C 语言中 旅行商问题 的程序示例

输出

Enter the number of cities: 4
Enter the cost matrix:
0 10 15 20