第8章高级算法

本章将介绍几种高级算法设计技术,包括贪心算法、回溯算法和分治算法。这些算法思想在解决复杂问题时各有特点,掌握它们可以大大扩展解决问题的能力。

8.1 贪心算法

Activity Selection

Activity Selection Animation

贪心算法是一种简单而高效的算法设计技术。它在每一步选择中都采取当前状态下的最优选择,希望通过局部最优达到全局最优。贪心算法不保证得到最优解,但在很多问题中可以得到最优解或接近最优解的解。

贪心算法适用于具有贪心选择性质的问题。贪心选择性质是指通过局部最优选择可以达到全局最优。贪心算法也要求问题具有最优子结构性质,即问题的最优解包含子问题的最优解。

def activity_selection(starts, ends):  
    n = len(starts)  
    activities = list(zip(starts, ends))  
    activities.sort(key=lambda x: x[1])  
      
    selected = [activities[0]]  
    last_end = activities[0][1]  
      
    for i in range(1, n):  
        if activities[i][0] >= last_end:  
            selected.append(activities[i])  
            last_end = activities[i][1]  
      
    return selected  

starts = [1, 3, 0, 5, 8, 5]  
ends = [2, 4, 6, 7, 9, 9]  

result = activity_selection(starts, ends)  
print("选择的活动:")  
for i, (s, e) in enumerate(result):  
    print(f"活动{i+1}: 开始时间{s}, 结束时间{e}")

活动选择问题是贪心算法的经典应用。给定一系列活动,每个活动有开始时间和结束时间,要求选择尽可能多的活动,使得它们不冲突。贪心策略是每次选择结束时间最早的活动,这样可以为后续活动留下最多的时间。

def fractional_knapsack(weights, values, capacity):  
    n = len(weights)  
    items = [(values[i] / weights[i], weights[i], values[i]) for i in range(n)]  
    items.sort(reverse=True)  
      
    total_value = 0  
    remaining_capacity = capacity  
      
    for ratio, weight, value in items:  
        if remaining_capacity >= weight:  
            total_value += value  
            remaining_capacity -= weight  
        else:  
            fraction = remaining_capacity / weight  
            total_value += value * fraction  
            break  
      
    return total_value  

weights = [10, 20, 30]  
values = [60, 100, 120]  
capacity = 50  

max_value = fractional_knapsack(weights, values, capacity)  
print(f"分数背包问题最大价值: {max_value}")

分数背包问题允许物品分割,可以使用贪心算法求解。每次选择性价比最高的物品,优先装入背包。这与0-1背包问题不同,0-1背包问题需要动态规划求解。

最小生成树问题也可以使用贪心算法求解。Prim算法从一个顶点开始,每次选择连接已选顶点和未选顶点的最小权边。Kruskal算法按边权从小到大依次选择,保证不形成环。

def prim_mst(graph):  
    n = len(graph)  
    selected = [False] * n  
    mst = []  
      
    selected[0] = True  
    edges_in_mst = 0  
      
    while edges_in_mst < n - 1:  
        min_weight = float('inf')  
        u, v = -1, -1  
          
        for i in range(n):  
            if selected[i]:  
                for j in range(n):  
                    ifnot selected[j] and graph[i][j] > 0:  
                        if graph[i][j] < min_weight:  
                            min_weight = graph[i][j]  
                            u, v = i, j  
          
        if u != -1:  
            selected[v] = True  
            mst.append((u, v, min_weight))  
            edges_in_mst += 1  
      
    return mst

8.2 回溯算法

N-Queens

N-Queens Animation

回溯算法是一种系统地搜索问题所有解的方法。它通过探索所有可能的候选解来找出所有解,如果候选解不满足约束条件,则回溯到上一步尝试其他候选。回溯算法适用于组合优化问题,如排列、组合、子集等。

def n_queens(n):  
    def is_safe(board, row, col):  
        for i in range(row):  
            if board[i] == col or \  
               abs(board[i] - col) == abs(i - row):  
                returnFalse  
        returnTrue  
      
    def solve(board, row):  
        if row == n:  
            solutions.append(board.copy())  
            return  
          
        for col in range(n):  
            if is_safe(board, row, col):  
                board[row] = col  
                solve(board, row + 1)  
                board[row] = -1  
      
    solutions = []  
    solve([-1] * n, 0)  
    return solutions  

def print_queens_board(solution):  
    n = len(solution)  
    for row in range(n):  
        line = ''  
        for col in range(n):  
            if solution[row] == col:  
                line += 'Q '  
            else:  
                line += '. '  
        print(line)  
    print()  

solutions = n_queens(4)  
print(f"4皇后问题共有{len(solutions)}种解法:")  
for i, sol in enumerate(solutions[:2]):  
    print(f"解法{i+1}:")  
    print_queens_board(sol)

N皇后问题要求在n×n棋盘上放置n个皇后,使得她们互不攻击。皇后可以攻击同一行、同一列和同一对角线上的其他皇后。回溯算法逐行放置皇后,每次放置时检查是否与已放置皇后冲突。

def subset_sum(nums, target):  
    def backtrack(start, current_sum, path):  
        if current_sum == target:  
            result.append(path.copy())  
            return  
          
        for i in range(start, len(nums)):  
            if current_sum + nums[i] <= target:  
                path.append(nums[i])  
                backtrack(i + 1, current_sum + nums[i], path)  
                path.pop()  
      
    result = []  
    backtrack(0, 0, [])  
    return result  

nums = [2, 3, 6, 7]  
target = 7  

solutions = subset_sum(nums, target)  
print(f"子集和问题: 从{nums}中选择元素和为{target}")  
for sol in solutions:  
    print(sol)

子集和问题要求从数组中选择元素,使得它们的和等于目标值。回溯算法尝试每种可能的组合,当当前和超过目标时剪枝,避免不必要的搜索。

回溯算法的时间复杂度通常是指数级,因为需要探索所有可能的解。但通过剪枝可以大大减少搜索空间。剪枝策略包括约束剪枝和优化剪枝。约束剪枝在候选解不满足约束条件时提前终止。优化剪枝在当前解不可能优于已知最优解时提前终止。

8.3 分治算法

分治算法将复杂问题分解为相似的子问题,递归求解子问题,然后将子问题的解合并为原问题的解。分治算法适用于可以自然分解的问题,如排序、查找、计算等。

分治算法的三个步骤是分解、解决和合并。分解步骤将原问题分解为若干子问题。解决步骤递归求解子问题,如果子问题足够小则直接求解。合并步骤将子问题的解合并为原问题的解。

def merge_sort_divide_conquer(arr):  
    if len(arr) <= 1:  
        return arr  
      
    mid = len(arr) // 2  
    left = merge_sort_divide_conquer(arr[:mid])  
    right = merge_sort_divide_conquer(arr[mid:])  
      
    return merge(left, right)  

def merge(left, right):  
    result = []  
    i, j = 0, 0  
      
    while i < len(left) and j < len(right):  
        if left[i] <= right[j]:  
            result.append(left[i])  
            i += 1  
        else:  
            result.append(right[j])  
            j += 1  
      
    result.extend(left[i:])  
    result.extend(right[j:])  
    return result  

data = [38, 27, 43, 3, 9, 82, 10]  
sorted_data = merge_sort_divide_conquer(data)  
print(f"归并排序: {sorted_data}")

归并排序是分治算法的经典应用。它将数组分成两部分,分别排序,然后合并。归并排序的时间复杂度为O(n log n),因为需要log n层递归,每层合并需要O(n)时间。

快速排序也是分治算法,但它使用不同的分解策略。快速排序选择一个基准元素,将数组分成小于基准和大于基准的两部分,然后递归排序两部分。

def karatsuba_multiply(x, y):  
    if x < 10or y < 10:  
        return x * y  
      
    n = max(len(str(x)), len(str(y)))  
    m = n // 2  
      
    high1, low1 = x // 10**m, x % 10**m  
    high2, low2 = y // 10**m, y % 10**m  
      
    z0 = karatsuba_multiply(low1, low2)  
    z1 = karatsuba_multiply((low1 + high1), (low2 + high2))  
    z2 = karatsuba_multiply(high1, high2)  
      
    return (z2 * 10**(2*m)) + ((z1 - z2 - z0) * 10**m) + z0  

result = karatsuba_multiply(1234, 5678)  
print(f"Karatsuba乘法: 1234 × 5678 = {result}")

Karatsuba乘法使用分治思想加速大数乘法。传统乘法需要O(n²)次乘法运算,Karatsuba算法将其降低到O(n^log3)约O(n^1.585)。这在处理超大数乘法时效率提升显著。

8.4 字符串匹配算法

字符串匹配是文本处理中的基本问题,要求在一个文本串中查找模式串的所有出现位置。朴素匹配算法时间复杂度为O(n×m),其中n是文本长度,m是模式长度。KMP算法通过预处理模式串,将时间复杂度降低到O(n+m)。

def kmp_search(text, pattern):  
    def build_lps(pattern):  
        lps = [0] * len(pattern)  
        length = 0  
        i = 1  
          
        while i < len(pattern):  
            if pattern[i] == pattern[length]:  
                length += 1  
                lps[i] = length  
                i += 1  
            else:  
                if length != 0:  
                    length = lps[length - 1]  
                else:  
                    lps[i] = 0  
                    i += 1  
          
        return lps  
      
    lps = build_lps(pattern)  
    positions = []  
    i, j = 0, 0  
      
    while i < len(text):  
        if pattern[j] == text[i]:  
            i += 1  
            j += 1  
              
            if j == len(pattern):  
                positions.append(i - j)  
                j = lps[j - 1]  
        else:  
            if j != 0:  
                j = lps[j - 1]  
            else:  
                i += 1  
      
    return positions  

text = "ABABDABACDABABCABAB"  
pattern = "ABABCABAB"  

positions = kmp_search(text, pattern)  
print(f"在文本中找到模式'{pattern}'的位置: {positions}")

KMP Animation

KMP算法的关键是构建部分匹配表(LPS数组)。LPS数组记录模式串中每个位置之前的最长相同前后缀长度。当匹配失败时,模式串可以跳过已经匹配的部分,避免重复比较。

8.5 最小生成树

MST

MST Animation

最小生成树是连通图的一个子图,它包含所有顶点且边数最少,边权总和最小。最小生成树在网络设计、电路设计等场景有重要应用。Prim算法和Kruskal算法是两种经典的构造方法。

def kruskal_mst(edges, n):  
    def find(parent, i):  
        if parent[i] != i:  
            parent[i] = find(parent, parent[i])  
        return parent[i]  
      
    def union(parent, rank, x, y):  
        root_x = find(parent, x)  
        root_y = find(parent, y)  
          
        if rank[root_x] < rank[root_y]:  
            parent[root_x] = root_y  
        elif rank[root_x] > rank[root_y]:  
            parent[root_y] = root_x  
        else:  
            parent[root_y] = root_x  
            rank[root_x] += 1  
      
    edges.sort(key=lambda x: x[2])  
      
    parent = [i for i in range(n)]  
    rank = [0] * n  
      
    mst = []  
    total_weight = 0  
      
    for u, v, weight in edges:  
        root_u = find(parent, u)  
        root_v = find(parent, v)  
          
        if root_u != root_v:  
            union(parent, rank, root_u, root_v)  
            mst.append((u, v, weight))  
            total_weight += weight  
      
    return mst, total_weight  

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5),  
         (1, 3, 15), (2, 3, 4)]  
n = 4  

mst, weight = kruskal_mst(edges, n)  
print("最小生成树的边:")  
for u, v, w in mst:  
    print(f"边({u}, {v}), 权重{w}")  
print(f"总权重: {weight}")

Kruskal算法按边权从小到大依次选择边,使用并查集检测是否形成环。Prim算法从一个顶点开始,每次选择连接已选顶点和未选顶点的最小权边。两种算法的时间复杂度都是O(E log E)或O(E log V)。

8.6 算法设计总结

掌握算法设计需要理解多种算法思想,并能够根据问题特点选择合适的方法。表8-1总结了主要算法设计技术的特点和适用场景。

算法类型	核心思想	时间复杂度	适用场景
贪心算法	局部最优选择	通常较低	活动选择、最小生成树、分数背包
回溯算法	搜索所有可能解	指数级	N皇后、排列组合、子集问题
分治算法	分解解决合并	O(n log n)常见	归并排序、快速排序、大数乘法
动态规划	保存子问题解	多项式级	背包问题、LCS、最短路径
图算法	BFS/DFS遍历	O(V+E)	路径搜索、连通性、拓扑排序

def algorithm_comparison():  
    import time  
      
    problems = {  
        '小规模排序': ('插入排序', 'O(n²)', '简单,稳定'),  
        '大规模排序': ('快速排序', 'O(n log n)', '高效,原地'),  
        '字符串搜索': ('KMP算法', 'O(n+m)', '避免重复比较'),  
        '最短路径': ('Dijkstra', 'O(E log V)', '正权图最短路径'),  
        '连通分量': ('DFS', 'O(V+E)', '检测图连通性'),  
        '背包问题': ('动态规划', 'O(n×W)', '0-1背包最优解'),  
    }  
      
    print("算法选择指南:")  
    for problem, (algorithm, complexity, note) in problems.items():  
        print(f"{problem}: {algorithm} ({complexity}) - {note}")  

algorithm_comparison()

选择合适的算法需要考虑多个因素。问题规模决定了算法的时间复杂度要求。数据特点影响算法的适用性,如是否有序、是否有重复等。性能要求包括时间限制、空间限制和是否需要最优解。实现难度权衡了开发成本和维护成本。

算法设计的一般流程是,理解问题明确输入输出和约束条件,分析问题寻找最优子结构或贪心选择性质,设计算法确定状态定义或分解策略,验证正确性证明算法可以得到正确解,优化改进通过剪枝或空间优化提高效率。

通过本教材的学习,你已经掌握了数据结构与算法的核心知识。从基础的线性结构到复杂的图论算法,从简单的排序到高级的动态规划,这些知识将为你解决实际问题提供坚实的基础。继续实践和探索,你将发现算法世界的更多精彩。

贪心算法通过局部最优达到全局最优,适用于活动选择、最小生成树等问题。回溯算法系统地搜索所有可能解,适用于组合优化问题。分治算法将问题分解为子问题求解,适用于排序和计算问题。我们还学习了字符串匹配算法和最小生成树算法。希望大家通过实践巩固所学知识,在算法设计的道路上不断进步。

预览时标签不可点

第8章 高级算法