最近才捡起的算法设计与分析.分析不准确的地方谅解,请各位看官指正. 1. 分治法与动态规划主要共同点: 二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解. 2. 分治法与动态规划实现方法: ① 分治法通常利用递归求解. ② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解. 3. 分治法与动态规划主要区别: ① 分治法将分解后的子问题看成相互独立的. ② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分. 例如: 在求解斐波那契数列过程中,求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).其中,求解fibonacci(4)时,需要求解fibonacci(3). 在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),即使求解fibonacci(4)子问题的时候已经求解过,也就是说,求解了二次子问题fibonacci(3). 动态规划为了避免类似子问题fibonacci(3)的重复求解,将已经求解过的子问题的解保存下来,在需要的时候将解值取出来,省去子问题解的重复求解过程. 4. 分治法与动态规划适用条件: ① 原问题具有最优子结构性质的前提下,分解出的子问题都绝对相互独立. ② 原问题具有最优子结构性质的前提下,分解出的子问题并不相互独立,求解一个子问题可能要用到已经求解过的子问题的解,子问题间具有重叠性,即适合具有重叠子问题性质的原问题. 5. 分治法与动态规划复杂度分析: ① 分治法因为对子问题进行了多次求解,所以效率比动态规划低一点.(时间复杂度相对高) ② 动态规划求解需要将子问题的解保存下来,所以会比分治法多用一些空间.(空间复杂度相对高) 其实,算法世界里,要么用时间换空间,要么用空间换时间.
Monthly Archives: April 2013
动态规划和贪心算法都是一种递推算法, 均有局部最优解来推导全局最优解.但它们的不同是… 相同点： 动态规划和贪心算法都是一种递推算法 均有局部最优解来推导全局最优解 不同点： 贪心算法： 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。 动态规划算法： 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解 3.边界条件：即最简单的，可以直接得出的局部最优解 ============================================================================== 贪心算法与动态规划 贪心法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解 贪心算法最经典的例子，给钱问题。 比如中国的货币，只看元，有1元2元5元10元20、50、100 如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？ 如果用贪心算，就是我每一次拿那张可能拿的最大的。 比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元 也就是3张 10、5、1。 每次拿能拿的最大的，就是贪心。 但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数 贪心只能得到一个比较好的解，而且贪心算法很好想得到。 再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了 比如某国的钱币分为 1元3元4元 如果要拿6元钱 怎么拿？贪心的话 […]
动态规划和贪心算法的区别
本文的文字部分转载自博客园，但由于其Dijkstra算法的代码存在一些问题，故特修改了一版该算法，更新上去。供大家参考。 本文相关的习题： 试举例说明如果允许带权有向图中某些边的权为负实数，则Dijkstra算法不能正确求得从源到所有其他顶点的最短路径长度。 Dijkstra算法 算法流程： (a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径； (c) 修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替。 (d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。 假设一共有N个节点，出发结点为s，需要一个一维数组prev[N]来记录前一个节点序号，一个一维数组dist[N]来记录从原点到当前节点最短 路径（初始值为s到Vi的边的权值，没有则为+∞），一个二维数组weights[N][N]来记录各点之间边的权重，按以上流程更新prev[N]和 dist[N]。 参考代码： //第四章：贪心算法 ////////////////////////////////////////////////////////////////////////// //FUNCTION: Dijkstra 4.4 单源最短路径问题, P105 //INPUT: // 带权有向图G=(V, E) // V = {1, 2, …, n}, 顶点v是源点 // c是一个二维数组，c[i][j]表示边(i, j )的权，当<i, j> 属于E时，c[i][j]是一个大数(无穷大） // dist[i]表示当前从源点到顶点的i 的最短路径长度. //OUTPUT: // 路径数组prev[] ////////////////////////////////////////////////////////////////////////// […]
单源最短路径算法–Dijkstra算法和Bellman-Ford算法
要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处 理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计 算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1） 选一个方程的近似根，赋给变量x0； （2） 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3） 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)； /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，xn-1） 设方程组为： xi=gi(X) (I=0，1，…，n-1) 则求方程组根的迭代算法可描述如下： 【算法】迭代法求方程组的根 { for (i=0;i x[i]=初始近似根; do { for (i=0;i […]
常用算法设计方法
最少费用购物 Description ?问题描述： 商店中每种商品都有标价。例如，一朵花的价格是2元。一个花瓶的价格是5 元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价售。例如，3朵花的价格不是6元而是5元。2 个花瓶加1 朵花的优惠价是10 元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。 ?编程任务： 对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。 Input 由文件input.txt提供欲购商品数据。文件的第1行中有1 个整数B（0≤B≤5），表示所购商品种类数。接下来的B 行，每行有3 个数C，K 和P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。K 表示购买该种商品总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多可购买5*5＝25件商品。由文件offer.txt提供优惠商品价数据。文 件的第1行中有1 个整数S（0≤S≤99），表示共有S 种优惠商品组合。接下来的S 行，每行的第一个数描述优惠商品组合中商品的种类数j。接着是j 个数字对（C，K），其中C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后一个数字P（1≤ P≤9999）表示此商品组合的优惠价。 Output 程序运行结束时，将计算出的所购商品应付的最少费用输出到文件output.txt中。 Sample Input input.txt 2 7 3 2 8 2 5 offer.txt 2 1 7 3 5 2 7 1 8 2 […]
最小费用购物问题
用2 台处理机A 和B 处理n个作业。设第i 个作业交给机器A 处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性 能关系，很可能对于某些i，有ai>=bi，而对于某些j，j≠i，有aj<bj，既不能将一个作业分开由2 台机器处理，也没有一台机器能 同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。 input 6 2 5 7 10 5 2 3 8 4 11 3 4 output15 //独立任务调度 #include<iostream> #include<vector> using namespace std; const int n=6; int a1[]={2,5,7,10,5,2}; int b1[]={3,8,4,11,3,4}; class tree { public: int a,b; }; int main() { cout<<“******************************************”<<endl; cout<<” 任务调度情况如下:”<<endl; cout<<” (1)作业数目:”<<n<<endl; cout<<” (2)各作业处理时间:”<<endl; cout<<” “; for(int aj=0;aj<n;aj++) cout<<a1[aj]<<” “; cout<<endl; cout<<” “; for(int bj=0;bj<n;bj++) cout<<b1[bj]<<” […]
独立任务最优调度问题
【实验目的】 练习掌握动态规划算法。 【实验内容】 设计一个O(n*n)时间的算法，找出由n个数组成的序列的最长单调递增子序列。 【实验条件】 Microsoft Visual C++ 6.0 【需求分析】 题目要求在O(n*n)的时间内找出n个数组成的序列的最长单调递增子序列,需要用到排序算法，查找最长公共子序列的算法。 【设计原理】 将数组a复制到数组x,先用排序算法将数组x排序，在调用查找最长公共子序列的算法求出数组a和数组x中的最长公共子序列，因为数组x是单调递增的，所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。 【概要设计】 数据： N：数组元素个数。 a[N]：用于存放数组。 X[N]：复制数组a[N]，并排序。 c[i][j]：存储a和x的最长公共子序列的长度。 b[i][j]：记录c[i][j]的值是由哪一个资问题的解得到的。 函数： int Partition(int a[],int p,int t,int x); //数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。 void Swap(int &x,int &y); //交换元素x和y。 void QuickSort(int a[],int p,int r); //快速排序。 void LCSL(int m,int n,int *x,int *y,int **c,int **b); //计算最长公共子序列长度。 void LCS(int […]
在O(n*n)时间内出由n个数组成的序列的最长单调递增子序列。
/* 课本0-1背包。 程序功能：将物体只能一次放入包中，要不超过总量 且 价值最大 经过vc8.0编译通过 * */ #include <iostream> using namespace std; #define N 10 #define C 50 void knapsack(int * v,int *w,int wlength,int c,int(*m)[C+1]) { int n=wlength-1; int jmax=std::min(w[n]-1,c); for(int j=0;j<=jmax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i–) { jmax=std::min(w[i]-1,c); for(int j=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=std::max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=std::max(m[1][c],m[2][c-w[1]]+v[1]); } […]
0-1背包
/* 课本 0-1背包 加上体积限制。 程序功能：将物体只能一次放入包中，要不超过总量、总体积且 价值最大 经过vc8.0编译通过 * */ #include <iostream> #include <iomanip> using namespace std; #define N 10 //物品的可选数量 #define C 40 //包的最大可容纳重量 #define E 28 //包的最大可容纳体积 //动态规划算法 void knapsack(int * v,int *w,int wlength,int c,int *e,int ee,int (*m)[C+1][E+1]) { int n=wlength-1; //—————————————– //递归计算的第一步 //求出当物品只有n的解 int jmax = std::min(w[n]-1,c); int jmax2 = std::min(e[n]-1,ee); for(int j=0;j<=jmax;j++) for(int k=0;k<=jmax2;k++) m[n][j][k] = 0; […]
0-1背包2
/* 课本3-1-1。 程序功能：求解最长公共递增子序列 经过vc8.0编译通过 * */ #include <iostream> #include <string.h> using namespace std; #define N 11 //——————————————————— //最长公共子序列求解 int lcslength(int * x,int m,int * y,int n,int (*b)[N]) { int c[N][N]; int i; for(i=0;i<=n;i++) {c[0][i]=0;c[i][0]=0;} for(i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } […]
求解最长公共递增子序列
最长单调递增子序列问题的定义： 设计一个O(n2)时间的算法，找出由n个数组组成的序列的最长单调递增子序列。 子问题的定义： 对于求解N规模的数组，n-1,n-2,…,1 长度的数组构成了问题的子问题，子问题的详细定义是：求解以第n-1,n-2,…,1 个元素为最大值的最长子序列。 最优子结构： 第n个元素的最长子序列的长度是基于前n-1个元素最长子序列的基础之上，也就是第n个元素的最长子序列长度，是前n个元素的中最长的子序列长度+1。 解决的办法： 从第1个元素开始进行循环，不断地求出1,2,3,..,n元素为最大值的最长子序列长度，然后通过回溯查找最长子序列。 具体算法： Input 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开 Output 最长单调递增子序列，数字之间用空格格开 Sample Input 5 1 3 5 2 9 Sample Output 1 3 5 9 C程序： #include <stdio.h> #include <stdlib.h> void findAllMax(int *,int *,int *,int); void trackBack(int *,int *,int *,int); […]
动态规划法 寻找最长单调递增子序列
After finished <Basic Engish> course & <engineering mathimatics> course, we started <Design and analysis of algorithms>. Frankly, I don’t familiar with most of them, although I’m a programmer with over ten years of experiences. I believe the reason of this is I’m not an algorithm researcher, but IMHO most of […]
我学：Design and analysis of algorithms
这是视频的演讲者是 Simon Sinek。这也是一个非常不错的演讲，当然这并不一定代表认同他对一些公司的看法和讲法，但重要的那种思想。我们做事件和表达必须从内而外。而不是自外而内。作为一点衔接，让我感触较深的是，就是前面提到我听：Richard St. John: 8 secrets of success这篇文章一样，作为一名员工，必须用心去做事，才可能成为一名好员工。举个例子： 公司从来不主动要求员工加班，但必如果一个员工真的认为自己的成长是跟公司、跟工作紧密连接在一起的，那不用要求，他自己就要用心，甚至拼了老命去工作。就像他提到的那样：The goal is not just to hire people who need a job; it’s to hire people who believe what you believe. I always say that, you know, if you hire people just because they can do a job, they’ll work for […]
我听：How great leaders inspire action
精华课程分享：成功的8个秘诀。 这是一篇很短的TED视频，只有3分多钟，但完全可以说“浓缩的都是精华”。 其中最让我深有感触的，也是我选择把这篇演讲放上来的原因是这一句话：Carol Coletta says, “I would pay someone to do what I do.” 我所在的公司其实一直都没怎么赚到钱，但是我们的老板却一直一直一直在往里边投钱，而且在许多时候的许多决策都让我们许多人都看不懂（废话，你要是看懂了，你不也成了Chairman of the Board了？）。 举个例子来说：我们今年不卖XXXX产品，RD努力做好XXXX产品。 OK，我明白，单纯这样讲可能你看不懂，那我换个说法：RD不要理会Sales的那些XXXX产品有YYYY bug、缺ZZZZ功能的抱怨（事实上连RD都知道有些问题很急，甚至有可能RD稍微努力的去配合一下，KKKK项目就能成功了），我想要做的是另外一个 功能/产品，而这个新功能/新产品可能几年内都带不来一分钱的收入，但谈下这个KKKK项目有可能会带来可观的收入，对业务的拓展及数年来的亏损有所帮 助…… 这样讲，也许你能有一点点的明白了吧？ 所以，当我在课堂上听到这句话的时候 Carol Coletta says, “I would pay someone to do what I do.”，真的被深深的感触到了，我们的董事长经营这家公司就是为了一种热爱，他爱这个产品，所以他愿意为这个产品投入大笔大笔的钱（哪怕连续的亏损），同时，他也愿意付钱给同样热爱这个产品的人让他们跟他一起工作。 以下为我专门到网上搜到的这个视频相关的英文原文： Richard St. John: 8 secrets of success http://www.ted.com/talks/richard_st_john_s_8_secrets_of_success.html About this talk Why […]
我听：Richard St. John: 8 secrets of success
1 最近一直在TED官方网站上看视频，尤其是看到杨澜的演讲，不知道为什么我非常激动。通过她17分钟的演讲让我更近一步的了解了杨澜这个人，还有中国现在的一些比较有意思的文化现象。 杨澜在TED上的演讲。我觉得是一次很不错的presentation.吐字清晰最重要，杨澜做到了。说她稀烂的…请你们别眼高手低。自己在家录一段看能不能有这个一半强= = 我欣赏杨澜 做为在TED演讲的极少数的中国人 沙沙的声音、气场和british accent玩的恰到好处 讲的关于中国的也都非常中肯 已经很不错了~~ from: http://www.ted.com/talks/yang_lan.html 杨澜介绍： 国内著名资深电视节目主持人。曾在国内具有强大影响力的电视台担任电视栏目主持，以极具亲和力的主持风格倍受广大电视观众的喜爱。曾主持《正大综艺》、《杨澜访谈录》等电视栏目；曾被评选为“亚洲二十位社会与文化领袖”、“能推动中国前进、重塑中国形象的十二位代表人物”、“《中国妇女》时代人物。 更多介绍：http://baike.baidu.com/view/26288.htm 视频收看地址：http://www.unsv.com/material/news/2011/10/10/Yang_Lan_TED_Speech/ The night before I was heading for Scotland, I was invited to host the final of “China’s Got Talent” show in Shanghai with the 80,000 live audience in the stadium. Guess who was the performing […]