经典算法

分治策略、动态规划、贪心算法、回溯法

算法中的经典,同时也是最常用的几种算法

1.分治策略(求解递归式的方法)

待补

2.动态规划

能采用动态规划求解的问题的一般要具有3个性质:
(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3) 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
动规解题的一般思路
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。
这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
动态规划决策过程示意图

(1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
(2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。
实际应用中可以按以下几个简化的步骤进行设计:
(1)分析最优解的性质,并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
(4)根据计算最优值时得到的信息,构造问题的最优解算法实现的说明 动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。
使用动态规划求解问题,最重要的就是确定动态规划三要素:
(1)问题的阶段 (2)每个阶段的状态 (3)从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,
不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。
确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,
表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,
从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}算法实现的步骤1、创建一个一维数组或者二维数组,保存每一个子问题的结果,具体创建一维数组还是二维数组看题目而定,
基本上如果题目中给出的是一个一维数组进行操作,就可以只创建一个一维数组,如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值,
比如背包问题中的不同物体的体积与总体积,找零钱问题中的不同面值零钱与总钱数,这样就需要创建一个二维数组。
注:需要创建二维数组的解法,都可以创建一个一维数组运用滚动数组的方式来解决,即一位数组中的值不停的变化,后面会详细徐叙述
2、设置数组边界值,一维数组就是设置第一个数字,二维数组就是设置第一行跟第一列的值,特别的滚动一维数组是要设置整个数组的值,然后根据后面不同的数据加进来变幻成不同的值。
3、找出状态转换方程,也就是说找到每个状态跟他上一个状态的关系,根据状态转化方程写出代码。
4、返回需要的值,一般是数组的最后一个或者二维数组的最右下角。

3.贪心算法

贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。
贪心算法每一步必须满足一下条件:
1、可行的:即它必须满足问题的约束。
2、局部最优:他是当前步骤中所有可行选择中最佳的局部选择。
3、不可取消:即选择一旦做出,在算法的后面步骤就不可改变了。

4.回溯法

回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法,
其基本思想就是穷举搜索。

1
2
3
4
5
6
7
8
9
10
11
12
► 有许多问题,当需要找出它的解集或者要求回答什
么解是满足某些约束条件的最佳解时,往往要使用回
溯法
► 回溯法的基本做法是搜索,或是一种组织得井井有条
的,能避免不必要搜索的穷举式搜索法。这种方法适
用于解一些组合数相当大的问题。
► 回溯法在问题的解空间树中,按深度优先策略,从根
结点出发搜索解空间树。算法搜索至解空间树的任意
一点时,先判断该结点是否包含(而不是找到解)问题
的解。如果肯定不包含,则跳过对该结点为根的子树
的搜索(剪枝),逐层向其祖先结点回溯;否则,进
入该子树,继续按深度优先策略搜索。

算法思想:
采用了一种“走不通就掉头”的思想。搜索时往往有多分支,
按某一分支为新的出发点,继续向下探索,当所有可能情况都
探索过且都无法到达目标的时候,再回退到上一个出发点,继
续探索另一个可能情况,这种不断回头寻找目标的方法称为“回溯法”。

搜索的方式
主要采用深度优先搜索的方式
回溯三要素:
1) 解空间:该空包含问题的解
2) 约束条件
3) 状态树

N皇后问题
跳马问题
迷宫问题
图的着色问题
0-1背包问题
装载问题
批处理作业调度
填数问题
组合输出问题
算24点问题
ACM应用

---------------- The End ----------------
0%