回溯、动态规划 -- 最短的路径

最短路径

1.回溯算法求解

2.动态规划求解

import typing as t


# 使用备忘录备忘录
def shortest_path_recall(data: t.List[t.List]) -> t.Union[float, int]:
    """
    回溯算法, 时间复杂度为0(n*m), 空间复杂度为0(n*m)

    TODO: 1.优化方法剪枝(备忘录), 记录某一结点vi之后的最优路径，得到从初始结点v0 -> vk,经过vi的最短路径。
    TODO: 2.比较当前最短路径和全局最短路径的大小，是否进行更新。
    TODO: 3.向右继续前进走。
    """
    if not data:
        return 0
    max_dist = float('inf')
    n = len(data)
    m = len(data[0])
    data.append([0 for _ in range(m)])
    for row in range(n + 1):
        data[row].append(0)

    def recall(i: int, j: int, dist: int):
        nonlocal max_dist
        nonlocal n

        if i == n and j == n - 1:
            max_dist = min(max_dist, dist)
            return
        elif i == n or j == n:
            return

        if i < n:
            # 往下走, 判断是否已经走过
            recall(i + 1, j, dist + data[i][j])
        if j < n:
            # 往右走
            recall(i, j + 1, dist + data[i][j])

    recall(0, 0, 0)
    return max_dist


data = [
    [1, 3, 5, 9],
    [2, 1, 3, 4],
    [5, 2, 6, 7],
    [3, 1, 1, 2]
]
res = shortest_path_recall(data)
print('回溯结果:', res)


def shortest_path_dp(mutex: t.List[t.List]) -> int:
    """
    动态规划
    时间复杂度为O(n*m), 空间复杂度为O(1)
    """
    if not mutex:
        return 0
    n = len(mutex)
    m = len(mutex[0])

    # 加边界
    mutex.append([float('inf') for _ in range(m)])
    for row in range(n + 1):
        mutex[row].append(float('inf'))

    for row in range(n):
        for col in range(m):
            # 跳过第一个位置
            if row == col == 0:
                continue
            mutex[row][col] += min(mutex[row - 1][col], mutex[row][col - 1])
    return mutex[-2][-2]

data1 = [
    [1, 3, 5, 9],
    [2, 1, 3, 4],
    [5, 2, 6, 7],
    [3, 1, 1, 2]
]

res_dp = shortest_path_dp(data1)
print('动态规划结果', res_dp)