使用rust学习基本算法(三)

ops/2024/10/18 14:25:07/

rust_0">使用rust学习基本算法(三)

动态规划

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

动态规划的关键概念

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

动态规划的步骤

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

动态规划算法的例子

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

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

rust">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格的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。这个问题可以用回溯算法来解决。

rust">// 定义一个公共函数来解决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恰好出现一次。

rust">// 公共函数,用于解决数独问题。接受一个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) {// 如果找到解决方案,则返回truereturn true;} else {// 如果未找到解决方案,撤销当前填入的数字,尝试下一个数字board[i][j] = '.';}}}// 如果所有数字都尝试过后仍无法解决,返回falsereturn false;}}}// 如果所有格子都正确填满,返回truetrue
}// 检查在棋盘的(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个元素的一个组合。通过回溯算法可以求出所有可能的组合。

rust">pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {let mut results = Vec::new();let mut combination = Vec::new();// 从1开始,因为题目中的元素是从1到nbacktrack(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

rust">/*
步骤 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)算法就是使用贪心策略来找到图中某个顶点到其他所有顶点的最短路径。

异同点

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

http://www.ppmy.cn/ops/16303.html

相关文章

微软在汉诺威工业博览会上推出新制造业Copilot人工智能功能,强化Dynamics 365工具集

在近日于德国汉诺威举行的盛大工业博览会上&#xff0c;微软向全球展示了其最新推出的制造业人工智能功能&#xff0c;这些功能以Dynamics 365工具集为核心&#xff0c;旨在通过先进的AI技术为制造业带来前所未有的变革。 此次推出的新功能中&#xff0c;最为亮眼的是支持AI的…

安全运营之通行字管理

一、什么是通行字 安全管理所指的通行字指的是对用于身份验证的账号密码或口令的管理。在计算机系统、网络服务、数据库管理等领域&#xff0c;通行字&#xff08;或称账号口令、密码&#xff09;是用于验证用户身份的重要机制。通行字管理的核心目标是确保只有授权用户才能访…

在 Ubuntu 22.04 上使用 Let‘s Encrypt 配置 Nginx SSL 证书

最近,我在自己的服务器上部署了一个网站,并决定使用 SSL 证书来确保网站的安全性。经过一番研究,我选择了 Lets Encrypt 作为 SSL 证书的提供商,因为它免费、自动化且广受信任。在这篇博客中,我将与大家分享我在 Ubuntu 22.04 上使用 Lets Encrypt 配置 Nginx SSL 证书的过程。…

vscode 创建代码模版

在vscode中快捷创建代码模版 1.在VSCode中&#xff0c;按下Ctrl Shift P&#xff08;Windows/Linux&#xff09;或Cmd Shift P&#xff08;Mac&#xff09;打开命令面板。 2.然后输入"Preferences: Configure User Snippets"并选择该选项。打开一个json文件用户…

WPF之RadioButton单选框和checkbox多选框

RadioButton 单选框: 实现分组的单选框&#xff0c; checkbox 多选框: 表示用户可以选择和清除的控件。 常用属性 GroupName 获取或设置指定哪些 RadioButton 控件互相排斥的名称Content内容IsChecked是否选中 常用事件 checked 选中的事件unchecked 未选中的事件 RadioBu…

最新免费 ChatGPT、GPTs、AI换脸(Suno-AI音乐生成大模型)

&#x1f525;博客主页&#xff1a;只恨天高 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ ChatGPT3.5、GPT4.0、GPTs、AI绘画相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容…

ios CI/CD 持续集成 组件化专题一 iOS 将图片打包成bundle

一、 创建 选择 macos 下的Bundle 二 、取名点击下一步 三、Base SDK 选择ios 四 、Build Active Architecture Only 五、Installation后面的内容删除 六、Skip Install 选择NO 七、Strip Debug Symbols During Copy 中"Release"项设置为 "YES" 八、COM…

HarmonyOS开发:【基于命令行(开发环境)】

准备开发环境 在嵌入式开发中&#xff0c;很多开发者习惯于使用Windows进行代码的编辑&#xff0c;比如使用Windows的Visual Studio Code进行OpenHarmony代码的开发。但当前阶段&#xff0c;大部分的开发板源码还不支持在Windows环境下进行编译&#xff0c;如Hi3861、Hi3516系…