当前位置：首页 > news >正文

分治与动态规划实战：从递归优化到网络流问题解析

news 2026/6/5 10:43:53

1. 分治算法：从递归到高效求解

分治算法（Divide and Conquer）是算法设计中的经典范式，核心思想是将一个大问题分解为若干个相互独立且结构相同的子问题，递归求解后再合并结果。这种"分而治之"的策略在计算机科学中应用广泛，比如快速排序、归并排序等都是典型的分治算法。

1.1 主定理（Master Theorem）

主定理是分析分治算法时间复杂度的利器。对于递归式T(n) = aT(n/b) + f(n)，其中a≥1，b>1：

若f(n) = O(n^(log_b a - ε))，则T(n) = Θ(n^(log_b a))
若f(n) = Θ(n^(log_b a))，则T(n) = Θ(n^(log_b a) * log n)
若f(n) = Ω(n^(log_b a + ε))，则T(n) = Θ(f(n))

举个例子，归并排序的递归式T(n) = 2T(n/2) + n，符合第二种情况，因此时间复杂度为Θ(n log n)。

1.2 Karatsuba快速乘法

传统乘法需要O(n²)时间，而Karatsuba算法通过分治将其优化到O(n^1.585)。其核心思想是将两个n位数x和y分别拆分为： x = a·10^(n/2) + b y = c·10^(n/2) + d

然后利用等式： xy = ac·10^n + (ad+bc)·10^(n/2) + bd 其中ad+bc可以通过(a+b)(c+d) - ac - bd计算，只需3次乘法。

def karatsuba(x, y): if x < 10 or y < 10: return x * y n = max(len(str(x)), len(str(y))) m = n // 2 a = x // 10**m b = x % 10**m c = y // 10**m d = y % 10**m ac = karatsuba(a, c) bd = karatsuba(b, d) ad_plus_bc = karatsuba(a+b, c+d) - ac - bd return ac * 10**(2*m) + ad_plus_bc * 10**m + bd

2. 动态规划：从重叠子问题到最优解

动态规划（Dynamic Programming）适用于具有最优子结构和重叠子问题性质的问题。与分治不同，动态规划会存储子问题的解避免重复计算。

2.1 背包问题详解

0-1背包问题是动态规划的经典案例：给定n个物品（重量w_i，价值v_i）和容量W的背包，求最大价值。

定义dp[i][j]为前i个物品装入容量j背包的最大价值，状态转移方程： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i) if j ≥ w_i = dp[i-1][j] otherwise

def knapsack(W, wt, val, n): dp = [[0]*(W+1) for _ in range(n+1)] for i in range(1, n+1): for w in range(1, W+1): if wt[i-1] <= w: dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]) else: dp[i][w] = dp[i-1][w] return dp[n][W]

2.2 动态规划优化技巧

状态压缩：二维dp数组可优化为一维，节省空间
记忆化搜索：自顶向下递归+缓存，更直观但可能有栈溢出风险
滚动数组：交替使用数组行减少空间消耗

3. 网络流问题：从最大流到最小割

网络流模型广泛应用于运输、匹配等问题。一个流网络G=(V,E)包含源点s、汇点t，每条边有容量c(u,v)。

3.1 Ford-Fulkerson算法

基于增广路径的最大流算法步骤：

初始化残余网络为原始容量
在残余网络中寻找s-t增广路径
沿路径推送等于最小残余容量的流
更新残余网络（包括添加反向边）
重复直到没有增广路径

def ford_fulkerson(graph, source, sink): parent = [-1]*len(graph) max_flow = 0 def bfs(residual_graph): visited = [False]*len(residual_graph) queue = [] queue.append(source) visited[source] = True while queue: u = queue.pop(0) for v, capacity in enumerate(residual_graph[u]): if not visited[v] and capacity > 0: queue.append(v) visited[v] = True parent[v] = u if v == sink: return True return False residual_graph = [row[:] for row in graph] while bfs(residual_graph): path_flow = float("Inf") v = sink while v != source: u = parent[v] path_flow = min(path_flow, residual_graph[u][v]) v = u v = sink while v != source: u = parent[v] residual_graph[u][v] -= path_flow residual_graph[v][u] += path_flow v = u max_flow += path_flow return max_flow