不做多余说明, 其实就是问题的逆向解题, 当前问题需要的条件,找到上一步怎么才能得到这些条件, 为了找寻这些条件又得到了一些新问题, 逐一最后把最上层的条件满足,所有的小问题都解决了
6. 动态规划法
动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。
动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。
7. 迭代法
迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。
例如
app版本的不断升级其实就是迭代法的具体表现
8. 分支界限法
分枝界限法是一个用途十分广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不相同。
分支定界法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)。在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支,这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
与贪心算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。
例如
猜数其实就是分支界限法的一个表现
8. 回溯法
回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
其基本思想是,在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。 若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
排序: 是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列
常见排序算法