使用rust学习基本算法（三）

动态规划

动态规划算法是一种在数学、管理科学、计算机科学和经济学中广泛使用的方法，用于解决具有重叠子问题和最优子结构特性的问题。它通过将复杂问题分解为更小的子问题来解决问题，这些子问题被称为“状态”，并且每个状态都是通过从其他状态转换而来的。动态规划算法通常用于求解最优化问题，尤其是那些涉及到决策过程的问题。

动态规划的关键概念

最优子结构：一个问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的解来构造原问题的解。
重叠子问题：在解决原问题的过程中，相同的子问题会被多次遇到和解决。动态规划通过存储这些子问题的解（通常在一个表格中），避免了重复计算。
状态：表示问题解决过程中的某个阶段或情形。
转移方程：定义了从一个状态到另一个状态转移的规则，通常以数学公式的形式给出。

动态规划的步骤

定义状态：确定如何描述问题的一个阶段或情形。
建立状态转移方程：找出状态之间如何转移，即如何从一个或多个已知状态导出一个新状态。
确定边界条件：即最简单的、不需要进一步分解就可以直接解决的子问题。
计算最优值：根据状态转移方程和边界条件，从最简单的子问题开始，逐步计算得到原问题的最优解。

动态规划算法的例子

斐波那契数列：使用动态规划来计算斐波那契数列是最简单的例子。通过存储已经计算过的值，可以避免重复计算。
背包问题：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内选择物品，使得总价值最大。
最长公共子序列：找出两个序列共有的、顺序相同但不必连续的最长子序列。

动态规划算法的一个常见例子是求解斐波那契数列。斐波那契数列是一个经典的动态规划问题，其中每个数是前两个数的和，形式为：F(n) = F(n-1) + F(n-2)，且F(0) = 0, F(1) = 1。

pub fn fibonacci(n: u64) -> u64 {
    let mut dp = vec![0; (n + 1) as usize];
    dp[1] = 1;
    for i in 2..=n as usize {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n as usize]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fibonacci() {
        assert_eq!(fibonacci(0), 0);
        assert_eq!(fibonacci(1), 1);
        assert_eq!(fibonacci(2), 1);
        assert_eq!(fibonacci(3), 2);
        assert_eq!(fibonacci(4), 3);
        assert_eq!(fibonacci(5), 5);
        assert_eq!(fibonacci(10), 55);
    }
}

定义了一个 fibonacci 函数，它接受一个 u64 类型的参数 n，并返回第 n 个斐波那契数。函数内部使用了一个动态规划数组 dp 来存储中间结果，以避免重复计算。接着，我们定义了一个测试模块 tests，其中包含了一个 test_fibonacci 测试函数，用于验证 fibonacci 函数的正确性。

回溯算法

回溯算法是一种通过试错来寻找问题解决方案的算法。当它尝试某一步骤时，如果发现当前步骤不能得到有效的解决方案或达到期望的结果，它将取消上一步甚至是几步的计算，然后通过其他可能的分支继续尝试找到问题的解。

回溯算法的特点

尝试分步的解决一个问题：在分步解决问题的过程中，通过尝试所有可能的分步方法（或者说是递归地尝试每一步），直到找到一个可能存在的正确的解答。
动态规划：与动态规划不同，回溯算法会撤销上一步或几步的计算，再通过其他可能的分支继续尝试。
适用范围广：回溯法可以解决组合数学中的问题，如图的遍历、数独、八皇后问题等。

回溯算法的基本步骤

• 选择：从候选解中选择一个分支。
• 约束：检查这个分支是否符合约束条件。如果不符合，就回溯到上一个分支。
• 目标：检查这个分支是否满足目标条件。如果满足，就记录下这个解，并回溯到上一个分支尝试其他可能。

回溯算法的应用实例

八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。这个问题可以用回溯算法来解决。

// 定义一个公共函数来解决n皇后问题，返回所有可能的解决方案。
pub fn solve_queens(n: usize) -> Vec<Vec<String>> {
    // 初始化一个棋盘，所有位置均为空（用'.'表示）
    let mut board = vec![vec!['.'; n]; n];
    // 用于存储所有找到的解决方案
    let mut solutions = Vec::new();
    // 从第0行开始尝试放置皇后，并进行回溯
    backtrack(&mut board, &mut solutions, 0);
    solutions
}

// 回溯函数
fn backtrack(board: &mut Vec<Vec<char>>, solutions: &mut Vec<Vec<String>>, row: usize) {
    // 如果已经处理完所有行，则将当前棋盘的解决方案添加到solutions中
    if row == board.len() {
        solutions.push(
            board.iter().map(|r| r.iter().collect()).collect(),
        );
        return;
    }

    // 尝试在当前行的每一列中放置皇后
    for col in 0..board.len() {
        // 检查在(row, col)位置放置皇后是否合法
        if is_valid(board, row, col) {
            // 放置皇后
            board[row][col] = 'Q';
            // 移动到下一行
            backtrack(board, solutions, row + 1);
            // 回溯，撤销当前位置的皇后
            board[row][col] = '.';
        }
    }
}

// 检查在(row, col)位置放置皇后是否合法
fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize) -> bool {
    // 检查同列是否有其他皇后
    for i in 0..row {
        if board[i][col] == 'Q' {
            return false;
        }
    }

    // 检查左上对角线是否有其他皇后
    let (mut i, mut j) = (row as i32, col as i32);
    while i >= 0 && j >= 0 {
        if board[i as usize][j as usize] == 'Q' {
            return false;
        }
        i -= 1;
        j -= 1;
    }

    // 检查右上对角线是否有其他皇后
    let (mut i, mut j) = (row as i32, col as i32);
    while i >= 0 && j < board.len() as i32 {
        if board[i as usize][j as usize] == 'Q' {
            return false;
        }
        i -= 1;
        j += 1;
    }

    true
}

首先定义了一个 solve_queens 函数，它接受一个表示棋盘大小的 n（在八皇后问题中，n 等于 8），并返回所有可能的解决方案。每个解决方案是一个包含 n 个字符串的 Vec，其中每个字符串代表棋盘上的一行，‘Q’ 表示一个皇后，‘.’ 表示空白。

backtrack 函数是回溯算法的核心，它尝试在棋盘的每一行放置一个皇后，并递归地在下一行中寻找合适的位置。如果当前行没有合适的位置，则回溯到上一行。is_valid 函数用于检查当前位置是否可以放置一个皇后，即它是否不会与之前放置的任何皇后发生冲突。

最后添加了一个单元测试来验证 solve_queens 函数的正确性。

数独：填充9×9的网格，使得每一行、每一列和九个3×3的网格中的数字1到9恰好出现一次。

// 公共函数，用于解决数独问题。接受一个9x9的棋盘（二维字符数组）作为参数。
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
    // 如果棋盘为空，则直接返回
    if board.is_empty() { return; }
    // 调用 solve 函数尝试解决数独
    solve(board);
}

// 尝试解决数独问题的递归函数。返回一个布尔值表示是否找到解决方案。
fn solve(board: &mut Vec<Vec<char>>) -> bool {
    // 遍历棋盘的每一个格子
    for i in 0..board.len() {
        for j in 0..board[0].len() {
            // 如果当前格子为空（用'.'表示）
            if board[i][j] == '.' {
                // 尝试填入1到9中的每一个数字
                for c in '1'..='9' {
                    // 检查填入当前数字是否有效
                    if is_valid(board, i, j, c) {
                        // 如果有效，则在当前格子填入数字，并递归尝试解决下一个空格
                        board[i][j] = c;
                        if solve(board) {
                            // 如果找到解决方案，则返回true
                            return true;
                        } else {
                            // 如果未找到解决方案，撤销当前填入的数字，尝试下一个数字
                            board[i][j] = '.';
                        }
                    }
                }
                // 如果所有数字都尝试过后仍无法解决，返回false
                return false;
            }
        }
    }
    // 如果所有格子都正确填满，返回true
    true
}

// 检查在棋盘的(row, col)位置填入字符c是否有效
fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, c: char) -> bool {
    for i in 0..9 {
        // 检查同一列、同一行、以及同一个3x3宫格内是否存在重复的数字
        // 注意这里的条件判断：检查行、列以及所在3x3宫格是否有重复元素
        if board[i][col] == c || board[row][i] == c || 
           board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c {
            return false;
        }
    }
    true
}

组合问题：从n个不同元素中，任取m（m≤n）个元素为一组，称为从n个不同元素中取出m个元素的一个组合。通过回溯算法可以求出所有可能的组合。

pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    let mut combination = Vec::new();
    // 从1开始，因为题目中的元素是从1到n
    backtrack(1, n, k, &mut combination, &mut results);
    results
}

fn backtrack(start: i32, n: i32, k: i32, combination: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
    // 如果组合中的数量达到了k，将其添加到结果中
    if k == 0 {
        results.push(combination.clone());
        return;
    }

    // 从当前数字开始，尝试每一个可能的选项
    for i in start..=n {
        // 将当前数字添加到组合中
        combination.push(i);
        // 递归地填充剩下的组合
        backtrack(i + 1, n, k - 1, combination, results);
        // 回溯，移除最后一个数字，尝试下一个数字
        combination.pop();
    }
}

总结

回溯算法通过试错来找到所有可能的解决方案，它在遇到“死路”时回退到上一个步骤，然后尝试其他可能的路径。这种方法虽然在某些情况下效率不高（比如解空间非常大时），但对于很多问题来说是一种简单而有效的解决方法。

邻接列表

邻接链表是一种常用于表示图的数据结构，特别适合表示稀疏图。在邻接链表中，图的每个顶点都对应一个链表，链表中的每个节点表示与该顶点相邻的顶点。这种数据结构使得查找所有与特定顶点相邻的顶点变得非常高效。

结构简介

对于一个包含 V 个顶点和 E 条边的图，邻接链表由一个数组或者哈希表组成，数组或哈希表的大小为 V。数组或哈希表的每个索引位置 i 都存储一个链表，这个链表包含了所有从顶点 i 出发的边所连接到的其他顶点。这样，图中的每条边都会在某个链表中以节点的形式出现。

优点

节省空间：相比于邻接矩阵，邻接链表在表示稀疏图时可以节省大量空间，因为它只存储存在的边而不是整个 V×V 的矩阵。
高效的边遍历：对于给定的顶点，可以快速访问其所有邻接顶点，时间复杂度为 O(E)，这对于某些算法（如深度优先搜索）非常有用。

缺点

查找边的效率低：如果要判断两个顶点之间是否存在边，需要在对应的链表中进行遍历，最坏情况下的时间复杂度为 O(V)。
空间开销：虽然相比邻接矩阵节省了空间，但是因为链表的存在，每条边都需要额外的空间来存储指针信息。

考虑一个简单无向图，顶点集合为 {0,1,2,3}，边集合为 {(0,1),(0,2),(1,2),(2,3)}。

邻接链表表示如下：

顶点 0 的链表：1 -> 2
顶点 1 的链表：0 -> 2
顶点 2 的链表：0 -> 1 -> 3
顶点 3 的链表：2

/*
步骤 1: 定义图结构
首先，定义图的结构。在这个例子中，图由顶点的集合组成，每个顶点通过一个 Vec<LinkedList<usize>> 存储其邻接顶点的索引。
*/
use std::collections::LinkedList;

// 图结构
pub struct Graph {
    // 邻接链表存储图的边
    adj_list: Vec<LinkedList<usize>>,
}

impl Graph {
    // 创建一个包含 n 个顶点的新图，初始化时没有边
    pub fn new(n: usize) -> Self {
        let adj_list = vec![LinkedList::new(); n];
        Graph { adj_list }
    }

    // 添加一条无向边
    pub fn add_edge(&mut self, src: usize, dest: usize) {
        // 因为是无向图，所以需要在两个方向上都添加
        self.adj_list[src].push_back(dest);
        self.adj_list[dest].push_back(src);
    }

    // 打印图的邻接链表表示
    pub fn print(&self) {
        for (i, adj) in self.adj_list.iter().enumerate() {
            print!("顶点 {} 的邻接顶点:", i);
            for v in adj {
                print!(" {}", v);
            }
            println!();
        }
    }
}
/*
步骤 2: 使用图结构
接下来，使用这个图结构来创建一个简单的图，并添加一些边。
*/
fn main() {
    let mut graph = Graph::new(4); // 创建一个包含4个顶点的图

    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);

    graph.print(); // 打印图的邻接链表
}

异同点

回溯算法

回溯算法是一种通过探索所有可能的候选解来找出所有解的问题解决方法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即“回溯”并尝试另一个解。回溯法通常用于解决组合问题，如数独、八皇后问题等。

动态规划

动态规划用于解决具有重叠子问题和最优子结构性质的问题。通过将问题分解为较小的子问题，并存储这些子问题的解（通常是使用数组或哈希表），动态规划避免了重复计算子问题，从而提高了效率。动态规划通常用于求解最优化问题，如最短路径、最长公共子序列等。

贪心算法

贪心算法在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不保证总能得到最优解，但在某些问题上效果非常好。例如，迪杰斯特拉（Dijkstra）算法就是使用贪心策略来找到图中某个顶点到其他所有顶点的最短路径。

异同点

• 相似之处：这三种算法在某种程度上都试图找到问题的最优解。它们都有一个共同的目标，即通过某种方式遍历解空间来找到问题的解。
• 不同之处：
  • 目标不同：回溯算法通常用于找出所有可能的解决方案，而动态规划和贪心算法更多地关注于找到最优解。
  • 处理子问题的方式不同：动态规划通过存储子问题的解来避免重复计算，而回溯算法则可能会多次解决相同的子问题。贪心算法则在每一步都做出局部最优选择，不一定考虑整体。
  • 应用范围不同：动态规划适用于有重叠子问题和最优子结构的问题；回溯算法适用于需要遍历整个解空间以找到所有解的问题；贪心算法适用于能够通过局部最优选择来达到全局最优的问题。
  • 性能和准确性：动态规划能够保证找到最优解，但可能会有较高的空间复杂度；回溯算法能够找到所有可能的解，但效率较低；贪心算法执行效率高，但不一定能找到全局最优解。