1、四种方法的对比
算法方法 | 用处 | 优点 | 缺点 | 拓展与改良 |
---|---|---|---|---|
回溯法 | 适用于求解组合问题、排列问题、搜索问题等。 | 1. 可以搜索整个解空间,找到最优解。 2. 不需要预先知道问题的解可能在哪里。 | 1. 时间复杂度高,因为需要遍历整个解空间。 2. 需要较大的空间存储搜索轨迹。 | 1. 剪枝优化。 2. 双向搜索。 |
动态规划 | 适用于求解具有最优子结构的问题。 | 1. 重复计算较少,效率高。 2. 可以通过将问题划分为多个子问题来简化问题。 | 1. 需要存储中间结果,占用空间较大。 2. 不能很好地处理某些非最优子结构的问题。 | 1. 记忆化搜索。 2. 状态压缩。 |
贪心法 | 适用于求解具有贪心选择性质的问题。 | 1. 算法简单,易于实现。 2. 通常时间效率较高。 | 1. 得到的不一定是最优解,很难证明其正确性。 2. 对于某些问题,可能无法使用贪心策略。 | 1. 局部搜索等启发式方法。 2. 迭代深化策略。 |
分治法 | 适用于将一个大问题划分为多个相似子问题的情况。 | 1. 对于一些规模较大的问题,可以减少问题的复杂度。 2. 可以利用并行计算提高效率。 | 1. 划分子问题需要一定的技巧和经验。 2. 对于一些问题,划分子问题比较困难。 | 1. 增加唯一性条件来避免重复计算。 2. 引入随机化算法增加多样性。 |
2、一句话理解四种算法思想(知乎大佬总结的)
分治:分而治之,先解决子问题,再将子问题的解合并求出原问题。
贪心:一条路走到黑,选择当下局部最优的路线,没有后悔药。
回溯:一条路走到黑,手握后悔药,可以无数次重来。(英雄联盟艾克大招无冷却)。
动态规划:上帝视角,手握无数平行宇宙的历史存档,同时发展出无数个未来。
回溯算法 Backtracking
通常用于求解组合问题、排列问题、搜索问题等,其优点在于可以搜索整个解空间,找到最优解,但缺点则是时间复杂度高,存储搜索轨迹需要较大空间。对回溯法可以通过剪枝优化、双向搜索等方式进行改良。
动态规划 Dynamic Programming
适用于求解具有最优子结构的问题,其优点在于重复计算较少,效率高,可以通过将问题划分为多个子问题来简化问题,但缺点则是需要存储中间结果,占用空间较大,不能很好地处理某些非最优子结构的问题。对动态规划可以通过记忆化搜索、状态压缩等方式进行改良。
贪心算法 Greedy
适用于具有贪心选择性质的问题,其优点在于算法简单易于实现,通常时间效率较高,但其缺点在于得到的不一定是最优解,难以证明其正确性,对于某些问题也无法使用贪心策略。对贪心法可以通过局部搜索等启发式方法、迭代深化策略等方式进行改良。
分治算法 Divide and Conquer
适用于将一个大问题划分为多个相似子问题的情况,其优点包括对于一些规模较大的问题可以减少问题的复杂度,可以利用并行计算提高效率,但其缺点在于划分子问题需要一定的技巧和经验,对于一些问题,划分子问题也比较困难。对分治法可以通过增加唯一性条件来避免重复计算、引入随机化算法等方式进行改良。
分治法应用
在计算机算法中,回溯法是一种常见的算法思想,通常用于解决组合问题、排列问题、搜索问题等。回溯法的基本思路是:从问题的子集或解空间开始,逐渐向下一步扩展,直到找到问题的解,或者无解时回溯到上一步继续搜索。
除了 n 皇后问题外,回溯法还有许多其他应用问题,如:
组合总和问题:给定一个正整数数组 candidates 和一个正整数 target,找出 candidates 中所有可以使数字和等于 target 的唯一组合。这个问题可以通过回溯法的思想来解决。
全排列问题:给定一个包含不同整数的数组 nums,返回其所有可能的全排列。这个问题也可以通过回溯法来解决。
单词搜索问题:给定一个 m × n 的二维字符网格和一个字符串 word,如果 word 存在于网格中,则返回 true;否则,返回 false。单词搜索问题也可以通过回溯法来解决。
八皇后问题:在 8×8 的国际象棋棋盘中放置 8 个皇后,使它们互相攻击不了。这也是一个著名的回溯法应用问题。
总之,回溯法是一种常见的算法思想,适用于许多组合、排列和搜索问题。在实际应用中,我们可以根据具体问题的特点和要求,选择合适的回溯法算法来解决。
01背包(动态规划)
#include <stdio.h>
#include <math.h>#define N 6 // 背包空间// 物品
#define W 4 // 物品数量
int value[] = {7,3,5,2}; // 价值
int weight[] = {1,2,5,4}; // 重量// 数组记录
int count[W+1][N+1] = {};int main(){int t,f; // 两个for循环// 数组初始化for(t=0; t<W+1; t++){for(f=0; f<N+1; f++){count[t][f] =0;}}int i,j; // 两个for循环for(i=1; i<W+1; i++){ // 遍历所有物品int nowWeight = weight[i-1]; // 当前物品的重量int nowValue = value[i-1]; // 当前价值for(j=1; j<N+1; j++){ // 遍历从 1 - 10重量的情况// 如果可以加上当前物品——并且——加上后的价值大于之前记录的价值,则更新——不行则记录之前的!if(nowWeight<=j && nowValue + count[i-1][j-nowWeight] > count[i-1][j]){count[i][j] = nowValue + count[i-1][j-nowWeight];}else{count[i][j] = count[i-1][j];}}}int n,m; // 两个for循环// 打印结果for(n=0; n<W+1; n++){for(m=0; m<N+1; m++){printf("%d ",count[n][m]);}printf("\n");}return 0;
}
N皇后(回溯法)
递归方法:
#include <stdio.h> #include <math.h>#define N 4 int q[N+1]; // 数组里面存储的是——皇后所在的列号 [i,j] j = q[i] j列号 i行号(第i个皇后) int answer = 0; // 方案数int queenCheck(int j){ // 行号int i = 0;for(i=0;i < j; i++){ // 循环判断 前面的所有皇后if(q[i] == q[j] || abs(j-i) == abs(q[j]-q[i])){ // 是否在同一列 || 是否在同一个斜线上return 0; // 不合法}}return 1; // 合法 }void queenInit(){int i;for(i=0; i<=N; i++){q[i] = 0;} }void printAnswer(){int i;printf("plan %d:",answer);for(i=0; i<=N; i++){printf("%d ",q[i]);}printf("\n"); }void queenFunc(int j){ // 从第j个皇后开始int i;for(i=1;i<=N;i++){q[j] = i; // 位置不断往后挪//如果合法if(queenCheck(j)){if(j == N){ // 找到了 N皇后的一组解answer++;printAnswer(); // 打印方案}else{queenFunc(j+1); // 下一个皇后}}} }int main(){queenInit(); // 初始化QueenqueenFunc(1); // 执行return 0; }
迭代方法:
#include <stdio.h> #include <math.h>#define N 8 int q[N+1]; // 数组里面存储的是——皇后所在的列号 [i,j] j = q[i] j列号 i行号(第i个皇后)int queenCheck(int j){ // 行号int i = 0;for(i=0;i < j; i++){ // 循环判断 前面的所有皇后if(q[i] == q[j] || abs(j-i) == abs(q[j]-q[i])){ // 是否在同一列 || 是否在同一个斜线上return 0; // 不合法}}return 1; // 合法 }void queenInit(){int i;for(i=0; i<=N; i++){q[i] = 0;} } void printAnswer(int answer){int i=0;printf("plan %d:",answer);for(i=0; i<=N; i++){printf("%d ",q[i]);}printf("\n"); }void queenFunc(){int answer = 0; // 方案数int j = 1; // 从第一个皇后开始while (j>=1){q[j] =q[j] + 1; // 从1开始,方便比较while (!queenCheck(j) && q[j]<=N){ // 不合法 && 位置没有超出q[j] +=1; // 往后挪}if(q[j]<=N){ // 找到了合法位置if(j == N){ // 找到了 N皇后的一组解answer++;printAnswer(answer); // 打印方案}else{j++; // 下一个皇后}}else{ // 溢出了也没有找到——回溯!!q[j] = 0; // 把失败的皇后位置重置j--; // 回溯 ---如果一直回溯到之前的第一行皇后 ---此时皇后位置也越界了————那么说明——已经把全部的方案都走完了!}}printf("all plans: %d",answer);}int main(){queenInit(); // 初始化QueenqueenFunc(); // 执行return 0; }