④ 寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件 。
一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程 。实际应用中可以按以下几个简化的步骤进行设计:
【九大经典算法思想及其典型应用】① 分析最优解的性质,并刻画其结构特征 。
② 递归的定义最优解 。
③ 以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值 。
④ 根据计算最优值时得到的信息,构造问题的最优解 。
(5) 算法实现的说明
动态规划的主要难点在于上面4个步骤的确定,一旦设计完成,实现部分就会非常简单 。使用动态规划求解问题,最重要的就是确定动态规划三要素:
① 问题的阶段
② 每个阶段的状态
③ 从前一个阶段转化到后一个阶段之间的递推关系 。
递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处 。
确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解 。
4.7贪心法Greedy
贪心算法也被称为贪婪算法,它在求解问题时总想用在当前看来是最好方法来实现 。这种算法思想不从整体最优上考虑问题,仅仅是在某种意义上的局部最优求解 。虽然贪心算法并不能得到所有问题的整体最优解,但是面对范围相当广泛的许多问题时,能产生整体最优解或者是整体最优解的近似解 。由此可见,贪心算法只是追求某个范围内的最优,可以称之为“温柔的贪婪” 。
贪心算法从问题的某一个初始解出发,逐步逼近给定的目标,以便尽快求出更好的解 。当达到算法中的某一步不能再继续前进时,就停止算法,给出一个近似解 。由贪心算法的特点和思路可看出,贪心算法存在以下3 个问题 。
① 不能保证最后的解是最优的 。
② 不能用来求最大或最小解问题 。
③ 只能求满足某些约束条件的可行解的范围 。
贪心算法的基本思路如下 。
① 建立数学模型来描述问题 。
② 把求解的问题分成若干个子问题 。
③ 对每一子问题求解,得到子问题的局部最优解 。
④ 把子问题的局部最优解合并成原来解问题的一个解 。
实现该算法的基本过程如下 。
(1)从问题的某一初始解出发 。
(2)while能向给定总目标前进一步 。
(3)求出可行解的一个解元素 。
(4)由所有解元素组合成问题的一个可行解 。
4.8回溯法Recursive search
回溯法也叫试探法,试探法的处事方式比较委婉,它先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一进行枚举和检验 。当发现当前候选解不可能是正确的解时,就选择下一个候选解 。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时,则继续扩大当前候选解的规模,并继续试探 。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解 。在试探算法中,放弃当前候选解,并继续寻找下一个候选解的过程称为回溯 。扩大当前候选解的规模,并继续试探的过程称为向前试探 。
使用试探算法解题的基本步骤如下所示 。
① 针对所给问题,定义问题的解空间 。
② 确定易于搜索的解空间结构 。
③ 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索 。
试探法为了求得问题的正确解,会先委婉地试探某一种可能的情况 。在进行试探的过程中,一旦发现原来选择的假设情况是不正确的,立即会自觉地退回一步重新选择,然后继续向前试探,如此这般反复进行,直至得到解或证明无解时才死心 。
4.9分支限界法Branch and Bound Method
分支限界法类似于回溯法,也是一种在问题的解空间树上搜索问题解的算法,但在一般情况下,分支限界法与回溯法的求解目标不同 。回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解 。
推荐阅读
- 余光中经典情话有哪些?
- 召回算法实践总结
- 家庭婚姻感悟经典句子有哪些?
- 人工智能技术含量降级,算法工程师从主人沦为保姆?是喜是忧?
- 巴菲特十句最经典名言是什么?
- Google tcp拥塞控制 bbr算法
- 字符串匹配KMP算法
- 微软|Win11企业安装率仅1.44% 还不如经典的WinXP多
- Python经典推导式,助你高效优雅的撸代码
- 岁月静好的经典句子有哪些?