0717-7821348
新闻中心

彩乐乐遗漏网

您现在的位置: 首页 > 新闻中心 > 彩乐乐遗漏网
五大经典算法总结
2019-07-09 23:20:32


1、分治法:把一个杂乱的问题分红两个或更多的相同或相似的子问题,再把子问题分红更小的子问题……直到最终子问题能够简略的直接求解,原问题的解即子问题的解的兼并。


2、动态规划法:每次决议计划依赖于当时状况,又随即引起状况的搬运。一个决议计划序列就是在改变的状况中产生出来的,所以,这种多阶段最优化决议计划处理问题的进程就称为动态规划。


3、贪心算法:在对问题求解时,总是做出在当时看来是最好的挑选。也就是说,不从全体最优上加以考虑,他所做出的仅是在某种意义上的部分最优解。常见的贪心算法有:Prim算法、Kruskal算法(都是求最小生成树的)。

根本思路:将问题分化为若干个小问题,逐步求得各个子问题的部分最优解,最终兼并为本来问题的解。


4、回溯法:回溯算法实践上一个相似枚举的查找测验进程,主要是在查找测验进程中寻觅问题的解,当发现已不满意求解条件时,就“回溯”回来,测验其他途径。深度优先;

       回溯法是一种选优查找法,按选优条件向前查找,以抵达方针。但当探究到某一步时,发现原先挑选并不优或达不到方针,就退回一步从头挑选,这种走不通就退回再走的技能为回溯法,而满意回溯条件的某个状况的点称为“回溯点”。


5、分支限界法:相似于回溯法,也是一种在问题的解空间树T上查找问题解的算法。但在一般情况下,分支限界法与回溯法的求解方针不同。回溯法的求解方针是找出T中满意束缚条件的一切解,而分支限界法的求解方针则是找出满意束缚条件的一个解,或是在满意束缚条件的解中找出使某一方针函数值抵达极大或极小的解,即在某种意义下的最优解。


一、分治法

分治法所能处理的问题一般具有以下几个特征:

    1) 该问题的规划缩小到必定的程度就能够简单地处理

    2) 该问题能够分化为若干个规划较小的相同问题,即该问题具有最优子结构性质。

    3) 运用该问题分化出的子问题的解能够兼并为该问题的解;

    4) 该问题所分化出的各个子问题是彼此独立的,即子问题之间不包括公共的子子问题。

若不具有第三条特征,可考虑选用动态规划法(DP)或许贪心法。

若不具有第四条特征,可考虑选用动态规划法。

分治法根本进程:

    step1 分化:将原问题分化为若干个规划较小,彼此独立,与原问题方式相同的子问题;

    step2 处理:若子问题规划较小而简单被处理则直接解,不然递归地解各个子问题

    step3 兼并:将各个子问题的解兼并为原问题的解。


可运用分治法求解的一些经典问题:

(1)二分查找

(2)大整数乘法

(3)Strassen矩阵乘法

(4)棋盘掩盖

(5)兼并排序

(6)快速排序

(7)线性时刻挑选

(8)最接近点对问题

(9)循环赛日程表

(10)汉诺塔


二、动态规划法

 与分治法最大的差别是:适合于用动态规划法求解的问题,经分化后得到的子问题往往不是相互独立的(即下一个子阶段的求解是树立在上一个子阶段的解的基础上,进行进一步的求解)。


适用条件:

能选用动态规划求解的问题的一般要具有3个性质:

    (1) 最优化原理:假如问题的最优解所包括的子问五大经典算法总结题的解也是最优的,就称该问题具有最优子结构,即满意最优化原理。

    (2) 无后效性:即某阶段状况一旦确认,就不受这个状况今后决议计划的影响。也就是说,某状小酒窝况今后的进程不会影响曾经的状况,只与当时状况有关。

   (3)有堆叠子问题:即子问题之间是不独立的,一个子问题鄙人一阶段决议计划中或许被屡次运用到。(该性质并不是动态规划适用的必要条件,可是假如没有这条性质,动态规划算法同其他算法比较就不具有优势)

事例:


有n级台阶,一个人每次上一级或许两级,问有多少种走完n级台阶的办法。

剖析:动态规划的完成的关键在于能不能精确合理的用动态规划表来笼统出 实践问题。在这个问题上,咱们让f(n)表明走上n级台阶的办法数。

那么当n为1时,f(n) = 1,n为2时,f(n) =2,就是说当台阶只需一级的时分,办法数是一种,台阶有两级的时分,办法数为2。那么当咱们要走上n级台阶,必定是从n-1级台阶迈一步或许是从n-2级台阶迈两步,所以抵达n级台阶的办法数必定是抵达n-1级台阶的办法数加上抵达n-2级台阶的办法数之和。即f(n) = f(n-1)+f(n-2),咱们用dp[n]来表明动态规划表,dp[i],i>0,i<=n,表明抵达i级台阶的办法数。

int fun(int n){if (n==1||n==2)return n;/*判别n-1的状况有没有被计算过*/if (!dp[n-1])  dp[n-1] = fun(n-1);if(!dp[n-2])  dp[n-2]=fun(n-2);return dp[n-1]+dp[n-2];}


三、贪心算法

贪心算法是指在对问题求解时,总是做出在当时看来是最好的挑选。也就是说,不从全体最优上加以考虑,只做出在某种意义上的部分最优解。贪心算法不是对一切问题都能得到全体最优解,关键是贪心战略的挑选,挑选的贪心战略有必要具有无后效性,即某个状况曾经的进程不会影响今后的状况,只与当时状况有关。

解题的一般进程是:

1.树立数学模型来描绘问题;

2.把求解的问题分红若干个子问题;

3.对每一子问题求解,得到子问题的部分最优解;

4.把子问题的部分最优解组成本来问题的一个解。


比如:钱币找零问题

这个问题在咱们的日常日子中就愈加遍及了。假定1元、2元、5元、10元、20元、50元、100元的纸币别离有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来付出K元,至少要用多少张纸币?用贪心算法的思维,很显然,每一步尽或许用面值大的纸币即可。在日常日子中咱们自然而然也是这么做的。在程序中现已事先将Value依照从小到大的次序排好。

public class charge {  public static void main(String[] args) {  //TODO 主动生成的办法存根  int res = charge(84);  System.out.println(res);  }
private static int charge(int money) { int count = 0; int value[] = {50,20,10,5,2,1}; while(money>0){ int l五大经典算法总结ength = value.length; for(int i=0;i<length;i++){ while(money>=value[i]){ money=money-value[i]; count++; //System.out.println(money); } }  } return count; }}

 四、回溯法

        回溯法是一种体系地查找问题解答的办法。在查找的进程中测验找到问题的解,假如发现找不到了,就退一步,往上回溯(剪枝进程)。关于许多杂乱问题和大规划问题都能够运用回溯法。 

 &nb五大经典算法总结sp;    回溯法的根本思维是依照深度优先查找的战略,从根节点开端查找,当到某个节点时要判别是否是包括问题的解,假如包括就从该节点持续查找下去,假如不包括,就向父节点回溯。若用回溯法求问题的一切解时,要回溯到根,且根结点的一切可行的子树都要已被查找遍才完毕。而若运用回溯法求任一个解时,只需查找到问题的一个解就能够完毕。 

      回溯法常用的剪枝函数:(1)束缚函数:在节点处减去不满意束缚的子树。(2)边界函数:减去得不到最优解的子树。


一般进程:

1、针对所给问题,确认问题的解空间

2、运用适于查找的办法安排解空间

3、运用深度优先查找解空间

4、在查找进程顶用剪枝函数防止无效查找。


举例:N皇后问题

在一个N*N的棋盘上放置N个皇后,每行一个并使其不能相互进犯(同一行、同一列、同一斜线上的皇后都会主动进犯)(代码暂不表明出)。