大家好,又见面了,我是全栈君。
近日复习了一些算法知识,小记于此
- 递归与分治法
相互独立且
与原问题同样。
二分法搜索、高速排序、合并排序。
- 动态规划法
动态规划过程是:依据当前(阶段)状态,採取对应的决策。引起状态的转移。例如以下图。一个决策序列就是在变化的状态中产生出来的,这样的多阶段最优化决策解决这个问题的过程就称为动态规划。
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
图1 动态规划决策过程示意图
按顺序求解子阶段。前一子问题的解,为后一子问题的求解提供了实用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其它局部解。
依次解决各子问题。最后一个子问题就是初始问题的解。
因为动态规划解决的问题多数有重叠子问题这个特点,为降低反复计算。对每个子问题仅仅解一次,将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的区别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。
最大m子段和)。
- 贪心算法
- 回溯法 (DFS搜索解空间)
比如n个物品的0-1背包问题。这类子集树通常有2^n个叶节点,其节点总个数为为2^(n+1)-1。
遍历子集树的不论什么算法均需O(2^n)的计算时间
比如旅行售货员问题。排列树通常有n!
个叶节点。因此遍历排列树须要O(n!)的计算时间。
栈Stack)。
N 皇后
- 分支界限法(BFS搜索解空间)
先进先出FIFO队列 和
优先队列分支界限法。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108483.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...