【回溯】2023Q1A-基站维修工程师

题目描述与示例

题目

小王是一名基站维护工程师，负责某区域的基站维护。 某地方有 n 个基站，1 < n < 10，已知各基站之间的距离 s，0 < s < 500，并且基站 x 到基站 y 的距离，与基站 y 到 基站 x 的距离并不一定会相同。 小王从基站 0 出发，途经每个基站 1 次，然后返回基站 0 ，需要请你为他选择一条距离最短的路。

输入

站点数 n 和各站点之间的距离，均为整数。

3     // 表示站点数
0 2 1 // 表示站点0到各站点的路程
1 0 2 // 表示站点1到各站点的路程
2 1 0 // 表示站点3到各站点的路程

输出描述

最短路程的数值。

示例一

输入

3
0 2 1
1 0 2
2 1 0

输出

3

说明

路线为0 -> 2 -> 1 -> 0，距离为所有路线最小 1 + 1 + 1 = 3。如果选择路线0 -> 1 -> 2 -> 0，距离为 2 + 2 + 2 = 6。

解题思路

这道题本质上是一道排列类型的回溯问题。

路径的终点和起点是都定好的，均为基站0，且其他基站能且仅能通过1次。所以我们只需要考虑剩余n-1个基站的全排列方式即可，即一共有(n-1)!种排列方式。

假设一共有 4 个基站，我们有且只有以下6种可能的路径：

0 -> 1 -> 2 -> 3 -> 0
0 -> 1 -> 3 -> 2 -> 0
0 -> 2 -> 1 -> 3 -> 0
0 -> 2 -> 3 -> 1 -> 0
0 -> 3 -> 1 -> 2 -> 0
0 -> 3 -> 2 -> 1 -> 0

所以可以使用回溯的办法，暴力地枚举出所有路径的距离和，并且获得所有距离和中的最小值即可。

剪枝优化

本题还可以进行剪枝优化。思路非常直接：如果某条路径的距离和path_sum已经大于等于当前的ans了，那么这条路径再往下延申，也一定会比ans更大，那么这条路径再往下搜寻就没有意义了，可以进行剪枝。

时空复杂度

时间复杂度：O(N!)。一共有(n-1)!条路径需要计算路径和。

空间复杂度：O(N)。忽略调用递归函数时编译栈所占空间，仅考虑检查数组所占用空间。

代码

解法一：回溯（无剪枝优化）

python"># 题目：2023Q1A-基站维修工程师
# 作者：闭着眼睛学数理化
# 算法>算法：回溯-无剪枝优化
# 代码看不懂的地方，请直接在群上提问

from math import inf

n = int(input())
mat = list()
for i in range(n):
    mat.append(list(map(int, input().split())))

# 用于判断某一节点是否被包含在当前路径中的检查数组
check_list = [False] * n
# 初始化位置0已经被包含在路径中
check_list[0] = True
# 初始化
ans = inf

# 回溯函数
def dfs(mat, check_list, cur_idx, path_sum):
    # 声明ans为全局变量，需要反复地被更新
    global ans
    # 终止递归条件：
    # 当check_list中所有值均为True，说明得到了一条经过了所有点的路径
    # 当前路径和path_sum还需要再加上从位置cur_idx去往位置0的距离
    if all(check_list):
        ans = min(ans, path_sum + mat[cur_idx][0])
        return
    # 横向遍历cur_idx到下一个点nxt_idx的所有距离
    for nxt_idx, val in enumerate(mat[cur_idx]):
        # 只有当nxt_idx还未存在于路径中，cur_idx才可以到达
        if check_list[nxt_idx] == False:
            # 状态更新：
            # 1. 标记下一个点nxt_idx已经存在于路径中
            # 2. 将从cur_idx到nxt_idx的距离val加入当前路径总和中
            check_list[nxt_idx] = True
            path_sum += val
            # 回溯：对下一个点nxt_idx进行递归
            dfs(mat, check_list, nxt_idx, path_sum)
            # 回滚：
            # 1. 标记下一个点nxt_idx从路径中删除
            # 2. 将从cur_idx到nxt_idx的距离val从当前路径总和中减去
            check_list[nxt_idx] = False
            path_sum -= val

# 调用递归函数的入口，最开始cur_idx = 0，path_sum = 0
dfs(mat, check_list, 0, 0)
print(ans)

解法二：回溯（剪枝优化）

python"># 题目：2023Q1A-基站维修工程师
# 作者：闭着眼睛学数理化
# 算法>算法：回溯-剪枝优化
# 代码看不懂的地方，请直接在群上提问

from math import inf

n = int(input())
mat = list()
for i in range(n):
    mat.append(list(map(int, input().split())))

# 用于判断某一节点是否被包含在当前路径中的检查数组
check_list = [False] * n
# 初始化位置0已经被包含在路径中
check_list[0] = True
# 初始化
ans = inf

# 回溯函数
def dfs(mat, check_list, cur_idx, path_sum):
    # 声明ans为全局变量，需要反复地被更新
    global ans
    # 剪枝优化：
    # 如果当前路径和path_sum已经大于等于当前ans
    # 这条路径再往下搜寻没有意义，不可能比ans更小，进行剪枝，终止当前路径继续往下搜寻
    if path_sum >= ans:
        return
    # 终止递归条件：
    # 当check_list中所有值均为True，说明得到了一条经过了所有点的路径
    # 当前路径和path_sum还需要再加上从位置cur_idx去往位置0的距离
    if all(check_list):
        ans = min(ans, path_sum + mat[cur_idx][0])
        return
    # 横向遍历cur_idx到下一个点nxt_idx的所有距离
    for nxt_idx, val in enumerate(mat[cur_idx]):
        # 只有当nxt_idx还未存在于路径中，cur_idx才可以到达
        if check_list[nxt_idx] == False:
            # 状态更新：
            # 1. 标记下一个点nxt_idx已经存在于路径中
            # 2. 将从cur_idx到nxt_idx的距离val加入当前路径总和中
            check_list[nxt_idx] = True
            path_sum += val
            # 回溯：对下一个点nxt_idx进行递归
            dfs(mat, check_list, nxt_idx, path_sum)
            # 回滚：
            # 1. 标记下一个点nxt_idx从路径中删除
            # 2. 将从cur_idx到nxt_idx的距离val从当前路径总和中减去
            check_list[nxt_idx] = False
            path_sum -= val

# 调用递归函数的入口，最开始cur_idx = 0，path_sum = 0
dfs(mat, check_list, 0, 0)
print(ans)