def merge_sort(arr):
    # 基线条件：当数组长度为 1 时直接返回
    if len(arr) <= 1:
        return arr

    # 分解
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 递归解决子问题
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    # 合并子问题解
    return merge(sorted_left, sorted_right)

def merge(left, right):
    sorted_arr = []
    i = j = 0

    # 合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    # 将剩余的元素加入结果数组
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])

    return sorted_arr

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted Array:", sorted_arr)

分治法的时间复杂度分析

对于许多分治算法，其时间复杂度可以通过递归公式进行分析： [ T(n) = aT\left(\frac{n}{b}\right) + O(n^d) ] 其中：
- (a) 是子问题的个数；
- (b) 是子问题规模缩小的倍数；
- (O(n^d)) 是分解和合并的代价。
通过主定理可以求解其复杂度。例如归并排序： [ T(n) = 2T\left(\frac{n}{2}\right) + O(n) ] 解得 (T(n) = O(n \log n))。

分治法的灵活性使其成为算法设计的基本工具之一，应用范围广泛且易于优化和并行化。

第三章

1.什么是动态规划法？

2.动态规划法两个重要的特征是什么？（最优子结构，重叠子问题）

3.用动态规划法求解问题的思路是什么？

4.典型的动态规划法实例（01背包问题，最长公共子序列，矩阵连乘，凸多边形最优三角剖分，多边形游戏，流水作业调度，电路布线，最优二叉搜索树）

5.遇到分治法题目的分析或者设计时可以参考以下内容

动态规划（Dynamic Programming, DP）是一种用于解决具有重叠子问题和最优子结构性质的问题的优化方法。它通过将问题分解为子问题，并以自底向上的方式解决，从而避免了重复计算。

动态规划的核心思想

重叠子问题：将问题分解为子问题时，许多子问题会被重复计算。
最优子结构：问题的最优解可以通过子问题的最优解来构造。
状态转移：通过定义状态变量和状态转移方程，将问题转换为递归关系。

动态规划的基本步骤

解决动态规划问题通常分为以下几个步骤：

1. 确定状态变量

找出问题的子问题和递归关系，明确状态的含义。

2. 建立状态转移方程

通过递推或递归关系描述从小规模问题到大规模问题的转化方式。

3. 初始化边界条件

确定问题的基本解（通常是规模最小的子问题的解）。

4. 填表（自底向上）

使用一个数组或表格从最小问题开始迭代计算，直至问题的最终解。

5. 返回最终解

从状态表中提取问题的最优解。

示例：用动态规划解决最长公共子序列（LCS）问题

问题描述：

给定两个字符串 (X) 和 (Y)，找出它们的最长公共子序列的长度。

问题分析

1. 确定状态变量

令 (dp[i][j]) 表示字符串 (X[0 \ldots i-1]) 和 (Y[0 \ldots j-1]) 的最长公共子序列的长度。

2. 状态转移方程

如果 (X[i-1] == Y[j-1])，则 (dp[i][j] = dp[i-1][j-1] + 1)；
如果 (X[i-1] \neq Y[j-1])，则 (dp[i][j] = \max(dp[i-1][j], dp[i][j-1]))。

3. 初始化边界条件

当 (i = 0) 或 (j = 0) 时，(dp[i][j] = 0)，因为一个空字符串的 LCS 长度为 0。

4. 填表过程

使用双重循环，从小到大计算 (dp[i][j])。

5. 返回结果

最终 (dp[m][n]) 就是字符串 (X) 和 (Y) 的 LCS 长度。

具体实现：

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)

    # 初始化 dp 表
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 填表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:  # 字符匹配
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:  # 不匹配
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 返回最终结果
    return dp[m][n]

# 测试
X = "AGGTAB"
Y = "GXTXAYB"
result = longest_common_subsequence(X, Y)
print("Length of LCS:", result)

动态规划的时间复杂度分析

动态规划的效率主要取决于状态表的大小和填表的复杂度。

表的大小：状态变量的组合情况（如 (O(n^2)) 或 (O(n))）。
填表复杂度：每个状态的计算代价（通常是常数时间）。

对于 LCS 问题：

状态表大小：(O(m \times n))
每个状态的计算代价：(O(1))
总时间复杂度：(O(m \times n))

动态规划是一种高效的求解方法，适合解决最优化问题、计数问题以及许多序列匹配相关的问题，其自底向上的思路在计算效率和可扩展性上具有优势。

第四章

1.贪心算法的思想是什么？

2.贪心算法的两个重要特征是什么？（最优子结构，贪心选择问题）

3.贪心算法求解问题的思路是什么？

4.典型的贪心算法实例（活动安排问题，装载问题，霍夫曼编码，单源最短路径，最小生成树）.

5.遇到贪心法题目的分析或者设计时可以参考以下内容

贪心法简介

贪心法（Greedy Algorithm）是一种算法设计策略，适用于在每个步骤中都选择当前最优解，最终期望通过一系列局部最优选择得到问题的全局最优解。

贪心法的核心是贪心选择性质，即每一步选择当前局部最优，最终能得到全局最优解。与动态规划不同，贪心法不需要回溯或保存所有子问题的解。

贪心法的基本步骤

问题建模
- 将原问题划分为多个阶段或子问题，每个阶段可以独立决策。
定义贪心选择规则
- 在每一步中，依据某种规则选择当前最优选项。
证明贪心选择性质和最优子结构
- 确保贪心选择的局部最优解不会影响全局最优解（问题必须满足最优子结构性质）。
迭代求解问题
- 根据贪心选择规则，逐步完成问题的解答。
返回解
- 当所有阶段处理完毕时，最终得到完整的解。

示例：用贪心法解决活动选择问题

问题描述：

有 (n) 个活动，每个活动有一个开始时间 (s[i]) 和结束时间 (f[i])。
在同一时间内最多只能参加一个活动。目标是选择最多数量的活动，使它们互不冲突。

贪心策略：

按结束时间最早的活动优先选择。这样可以尽可能为后续活动留出更多时间。

问题分析

1. 建模：

活动的集合为 ({a_1, a_2, \ldots, a_n})，每个活动的时间范围为 ([s[i], f[i]])。
按结束时间 (f[i]) 对活动排序。

2. 定义贪心选择规则：

从当前活动开始时间不早于上一个已选活动的结束时间中，选择结束时间最早的活动。

3. 验证最优性：

按结束时间排序的活动中，优先选择结束时间早的活动，确保留出更多的时间段给剩余活动。

具体实现

def activity_selection(start, finish):
    n = len(start)
    # 将活动按结束时间排序
    activities = sorted(zip(start, finish), key=lambda x: x[1])
    
    selected_activities = []
    last_end_time = 0  # 记录上一个选择的活动的结束时间

    for s, f in activities:
        if s >= last_end_time:  # 当前活动的开始时间不早于上一次活动的结束时间
            selected_activities.append((s, f))
            last_end_time = f  # 更新已选择活动的结束时间

    return selected_activities

# 测试
start_times = [1, 3, 0, 5, 8, 5]
finish_times = [2, 4, 6, 7, 9, 9]

selected = activity_selection(start_times, finish_times)
print("Selected activities:", selected)

输出：

Selected activities: [(1, 2), (3, 4), (5, 7), (8, 9)]

贪心法与动态规划的比较

特性	贪心法	动态规划
适用问题	局部最优可导出全局最优	需要所有子问题的解来求全局最优
计算方式	每一步选择当前局部最优	通过状态转移递推求解
时间复杂度	通常为 (O(n \log n)) 或 (O(n))	通常为 (O(n^2)) 或 (O(n^3))
应用场景	简单、规则明确的问题	更复杂的问题（如背包、序列匹配）

总结

贪心法是一种简洁高效的算法设计策略，适用于解决优化问题，如资源分配、路径选择、调度等。它的关键在于选择合适的贪心策略并验证其正确性，确保局部最优能推导出全局最优解。

第五章

1.回溯法的解题思路是什么？

2.回溯法求解问题的基本步骤是什么？

3.回溯法的解空间有哪几类？

4.典型的回溯法实例（装载问题，批处理作业调度、最大团问题，符号三角形，0-1背包问题，N后问题，图的M着色问题，旅行商问题）

5.遇到回溯法题目的分析或者设计时可以参考以下内容

回溯法简介

回溯法是一种系统的搜索算法，用于解决约束满足问题和组合问题。它通过递归地尝试所有可能的解，并在发现当前路径不符合约束时，回退到上一步继续尝试其他路径，从而找到满足条件的解。

回溯法的核心思想是：试探 + 回退。

试探：选择一个可能的解尝试扩展。
回退：如果发现当前选择不可行（不符合约束条件），则撤销选择，返回上一步尝试其他可能的路径。

回溯法的基本步骤

定义问题的解空间
- 将问题转化为一个树形结构，每个节点表示一个状态，每条路径代表一组选择。
设计状态变量
- 使用变量表示问题的当前状态，例如决策的步骤、路径等。
确定约束条件
- 明确解的合法性条件，当一个节点违反约束时，回退到上一步。
设计递归框架
- 按顺序尝试每种可能的选择，并在每次递归调用中扩展解。如果当前解非法或已完成，则停止递归。
收集解
- 如果找到符合条件的解，将其保存。

示例：经典问题解决方案

问题 1：N 皇后问题

描述：在 (N \times N) 的棋盘上，放置 (N) 个皇后，使得它们彼此不能攻击（即不能在同一行、同一列或同一对角线）。

步骤：

解空间：
- 解空间是一个 (N) 层的决策树，每层代表棋盘的一行，节点代表皇后的位置。
状态变量：
- 用数组 positions 表示皇后的位置，其中 positions[i] 为第 (i) 行皇后所在的列号。
约束条件：
- 任意两个皇后不能在同一列：
  [ positions[i] \neq positions[j] ]
- 任意两个皇后不能在同一对角线：
  [ |positions[i] - positions[j]| \neq |i - j| ]
递归框架：
- 从第 (i) 行开始，尝试将皇后放在每一列。如果合法，递归处理下一行。

实现代码：

def solve_n_queens(n):
    def is_safe(row, col, positions):
        for prev_row in range(row):
            prev_col = positions[prev_row]
            # 检查列冲突和对角线冲突
            if prev_col == col or abs(prev_col - col) == abs(prev_row - row):
                return False
        return True

    def backtrack(row, positions):
        if row == n:  # 找到一个合法解
            solutions.append(positions[:])
            return

        for col in range(n):  # 尝试每一列
            if is_safe(row, col, positions):
                positions[row] = col  # 试探
                backtrack(row + 1, positions)  # 递归
                positions[row] = -1  # 撤销试探

    solutions = []
    positions = [-1] * n  # 初始化皇后位置
    backtrack(0, positions)  # 从第 0 行开始
    return solutions

# 测试
n = 4
solutions = solve_n_queens(n)
print(f"{n}-Queens Solutions:")
for sol in solutions:
    print(sol)

输出：

4-Queens Solutions:
[1, 3, 0, 2]
[2, 0, 3, 1]

每个解表示第 (i) 行皇后所在的列号。

问题 2：生成所有子集

描述：给定一个集合 (S = {a, b, c})，生成它的所有子集。

步骤：

解空间：
- 树形结构，每层代表当前元素是否被选中（两种可能：选或不选）。
状态变量：
- 使用数组 path 表示当前选择。
约束条件：
- 无需额外约束，所有路径都有效。
递归框架：
- 对于每个元素，递归尝试包含或不包含该元素。

实现代码：

def generate_subsets(nums):
    def backtrack(index, path):
        if index == len(nums):  # 递归终止条件
            subsets.append(path[:])  # 保存当前解
            return
        # 不选当前元素
        backtrack(index + 1, path)
        # 选当前元素
        path.append(nums[index])
        backtrack(index + 1, path)
        path.pop()  # 撤销选择

    subsets = []
    backtrack(0, [])
    return subsets

# 测试
nums = [1, 2, 3]
print("Subsets:", generate_subsets(nums))

输出：

Subsets: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

问题 3：全排列

描述：给定一个数组 (S = [1, 2, 3])，生成所有可能的排列。

步骤：

解空间：
- 树形结构，每层代表选择一个未使用的元素。
状态变量：
- 使用布尔数组 used 表示元素是否已被使用。
- path 表示当前排列。
约束条件：
- 一个元素只能使用一次。
递归框架：
- 遍历每个未使用的元素，递归生成下一个位置的排列。

实现代码：

def generate_permutations(nums):
    def backtrack(path):
        if len(path) == len(nums):  # 递归终止条件
            permutations.append(path[:])  # 保存当前排列
            return
        for i in range(len(nums)):
            if used[i]:
                continue  # 跳过已使用元素
            used[i] = True  # 标记为已使用
            path.append(nums[i])
            backtrack(path)  # 递归
            path.pop()  # 撤销选择
            used[i] = False  # 撤销标记

    permutations = []
    used = [False] * len(nums)  # 初始化标记数组
    backtrack([])
    return permutations

# 测试
nums = [1, 2, 3]
print("Permutations:", generate_permutations(nums))

输出：

Permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

回溯法的时间复杂度

时间复杂度：
- 取决于解空间大小。例如：
  - N 皇后问题：最坏情况下 (O(N!))。
  - 子集生成：解空间大小为 (2^N)，时间复杂度 (O(2^N))。
  - 全排列：解空间大小为 (N!)，时间复杂度 (O(N!))。
剪枝优化：
- 在搜索过程中提前排除不可能的路径，可以显著降低时间复杂度。

总结

回溯法是一种灵活而强大的算法，适用于组合、排列、约束满足等问题。它通过递归试探和回退逐步构造解，并利用剪枝技巧提高效率。回溯法的关键在于清晰地定义解空间和约束条件，并设计合理的递归框架。

第六章分支限界法

1.什么是分支限界法？分支限界法的基本思想

2.分支限界法与回溯法的区别和联系

3.分支限界法中的几种数据结构

4.典型分支限界法（装载问题，0-1背包问题，单源最短路径问题，旅行商问题，批处理作业调度）

5.遇到分支限界法题目的分析或者设计时可以参考以下内容

分支限界法简介

分支限界法（Branch and Bound, B&B）是一种系统化搜索算法，用于求解组合优化问题（如最优解问题）。它与回溯法类似，都通过构造搜索树探索解空间，但分支限界法特别适用于最优化问题，它在搜索过程中通过限界（bounding）来剪除不可能得到最优解的分支，从而减少搜索量。

分支限界法的核心概念

搜索树
- 问题的解空间通过树形结构表示，每个节点对应一个子问题。
- 树的分支表示可能的选择。
分支（Branching）
- 将当前问题划分为若干子问题（扩展子节点）。
限界（Bounding）
- 通过计算当前节点的上界或下界（与问题的最优解相关），排除不可能得到更优解的子问题，减少搜索。
优先搜索策略
- 按某种规则选择优先扩展的节点（如广度优先、深度优先或最佳优先）。
剪枝
- 如果某节点的估计值无法超过当前已知的最优解，则直接舍弃该分支。

分支限界法的基本步骤

问题建模
- 定义问题的解空间，并用树形结构表示。
- 明确目标函数（最大化或最小化）。
选择搜索策略
- 确定搜索顺序（如队列/优先队列来存储活结点）。
定义上界/下界函数
- 设计用于估算节点潜在最优解的函数（如问题的松弛解）。
搜索与剪枝
- 按搜索策略选择当前节点。
- 计算其估计值并比较。如果节点的估计值不能超过当前最优解，则剪枝，否则扩展其子节点。
更新当前最优解
- 如果当前节点对应的解优于已知最优解，则更新最优解。
重复直至搜索完成
- 搜索结束后，返回最终解。

示例：用分支限界法解决 0-1 背包问题

问题描述：

给定 (n) 个物品，每个物品有重量 (w[i]) 和价值 (v[i])，背包的最大容量为 (W)。选择若干物品装入背包，最大化总价值且总重量不超过 (W)。

解空间：

用一个搜索树表示选择每个物品的情况：树的每个节点表示一个部分解，左分支表示选择当前物品，右分支表示不选择当前物品。

限界函数（Bounding Function）：

对于每个节点计算上界（最大可能价值），用于剪枝。
- 松弛解：假设可以装入部分物品（贪心策略），求得的价值为当前节点的上界。

算法实现：

import heapq

# 定义节点类
class Node:
    def __init__(self, level, value, weight, bound):
        self.level = level  # 当前处理的物品索引
        self.value = value  # 当前价值
        self.weight = weight  # 当前重量
        self.bound = bound  # 当前节点的估计上界

    def __lt__(self, other):
        return self.bound > other.bound  # 优先队列按上界从大到小排列

# 计算节点的估计上界
def calculate_bound(node, n, W, weights, values):
    if node.weight >= W:
        return 0  # 超过容量，不可能有更优解

    bound = node.value
    total_weight = node.weight
    j = node.level + 1

    # 贪心装入物品以计算上界
    while j < n and total_weight + weights[j] <= W:
        total_weight += weights[j]
        bound += values[j]
        j += 1

    # 部分装入下一个物品
    if j < n:
        bound += (W - total_weight) * values[j] / weights[j]

    return bound

# 分支限界法求解 0-1 背包问题
def branch_and_bound_knapsack(n, W, weights, values):
    # 按单位价值排序
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    weights, values = zip(*items)

    # 初始化优先队列
    queue = []
    root = Node(-1, 0, 0, calculate_bound(Node(-1, 0, 0, 0), n, W, weights, values))
    heapq.heappush(queue, root)

    max_value = 0  # 保存当前最优解

    while queue:
        node = heapq.heappop(queue)

        if node.level == n - 1 or node.bound <= max_value:
            continue  # 到达叶节点或无望更优解，剪枝

        # 扩展左子节点（选择当前物品）
        left = Node(node.level + 1,
                    node.value + values[node.level + 1],
                    node.weight + weights[node.level + 1],
                    0)

        if left.weight <= W and left.value > max_value:
            max_value = left.value  # 更新最优解

        left.bound = calculate_bound(left, n, W, weights, values)
        if left.bound > max_value:
            heapq.heappush(queue, left)

        # 扩展右子节点（不选择当前物品）
        right = Node(node.level + 1, node.value, node.weight, 0)
        right.bound = calculate_bound(right, n, W, weights, values)
        if right.bound > max_value:
            heapq.heappush(queue, right)

    return max_value

# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
n = len(weights)
max_val = branch_and_bound_knapsack(n, W, weights, values)
print("Maximum value:", max_val)

输出：

Maximum value: 7

分支限界法的优缺点

优点：

通过剪枝减少了搜索空间，特别适合最优化问题。
可以找到全局最优解。

缺点：

解空间仍可能很大，容易受到问题规模的限制。
设计上界/下界函数时需结合具体问题。

总结

分支限界法是一种适用于最优化问题的有效算法。它通过优先扩展潜在最优解的路径，同时通过限界函数剪枝无效解，显著减少了搜索空间。应用范围广泛，包括背包问题、旅行商问题和资源分配问题等。