logo资料库

算法分析与设计课程的设计论文.doc

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：doc 举报 版权申诉
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
资料共14页，剩余部分请下载后查看
    信息技术学院 算 法 设 计 与 分 析 课 程 考 查 论 文 目 0-1 背包问题的算法设计策略对比与分析 题 专 班 学 姓 业 级 号 名 计算机科学与技术 2006 级软件方向 061124015 刘翠兰 宋振方 2008 年 12 月 31 日 任 课 教 师 完 成 日 期
    2006 级软件方向算法设计与分析课程考查论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说，算法的概念是至关重要的，例如，在一个大型软件系统的开发中，设计出 有效的算法将起决定性的作用。算法是解决问题的一种方法或一个过程。程序是算法用某种设计语 言具体实现描。计算机的普及极大的改变了人们的生活。目前，各行业、各领域都广泛采用了计算 机信息技术，并由此产生出开发各种应用软件的需求。为了以最小的成本、最快的速度、最好的质 量开发出适合各种应用需求的软件，必须遵循软件工程的原则。设计一个高效的程序不仅需要编程 小技巧，更需要合理的数据组织和清晰高效的素算法，这正是计算机科学领域数据结构与算法设计 所研究的主要内容。 1 算法复杂性分析的方法介绍 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的 空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本 身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复 杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则 有： T=T(N,I)和S=S(N,I) 。（通常，让A隐含在复杂性函数名当中 最坏情况下的时间复杂性： T max (N)  max NDI ), INT (  max DI  N 最好情况下的时间复杂性： k  i 1  ), INet i ( i  k i i 1  , INet ( i * ) *INT ( , ) T min (N)  min NDI ), INT (  min DI  N 平均情况下的时间复杂性： k  i 1  , INet i ( i )  )~, INet ( i k i i  1 )~, INT ( T avg (N)   NDI  ()( ), INTIP  )( IP  NDI  k  i 1  ), INet i ( i 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入； 是中使 T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。 算法复杂性在渐近意义下的阶： 渐近意义下的记号：O、Ω、θ、o 设f(N)和g(N)是定义在正数集上的正函数。 O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时 上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。 根据O的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g))； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N))，则O(f)+O(g)=O(f)； (5)O(Cf(N))=O(f(N))，其中C是一个正的常数； (6)f=O(f)。 Ω的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大 第 1 页 共 14 页
    0-1 背包问题的算法设计策略对比与分析 时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。 θ的定义：定义f(N)= θ(g(N))当且仅当f(N)=O(g(N))且f(N)= Ω(g(N))。此时称f(N)与g(N)同阶。 o的定义：对于任意给定的ε＞0，都存在正整数N0，使得当NN0时有f(N)/Cg(N)ε,则称函数f(N) 当N充分大时的阶比g(N)低，记为f(N)=o(g(N))。 例如，4NlogN+7=o(3N2+4NlogN+7)。 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问 题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的 解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。由于分治法产生的子问题往 往是原来问题的较小规模，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段， 可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此 自然引出递归算法。分治与递归像是一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许 多高效的算法。 2.2 动态规划 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得 到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有 些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的 答案，就可以避免大量重复计算，从而得到多项式时间算法。 动态规划的一般步骤：找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 2.3 贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑， 它所作出的选择只是在某种意义上的局部最优选择。具有最优子结构性质的问题，用贪心算法更简 单、更直接且解题效率更高。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法 不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最 小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很 好近似。 2.4 回溯法 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使 用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这 种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间 树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树 的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空 间。 第 2 页 共 14 页
    2006 级软件方向算法设计与分析课程考查论文 2.5 分支限界法 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限 界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所 有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点 被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续 到找到所需的解或活结点表为空时为止。 从活结点表中选择下一扩展结点的不同方式导致不同的分 支限界法： 队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先 3 结合 0-1 背包问题详述动态规划、贪心算法、回溯法、分支限界法解决问题的过程 0-1 背包问题：给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包的容量是 c。 问应如何选择装入背包中的物品，使得装入背包中的物品总价值最大。在选择装入背包的物品时， 对每种物品 i 只能有两种选择，装入包或者不装入。不能物品 i 装入包多次，也不能之装入部分的 物品 i。 3.1 动态规划算法 问题描述此问题的形式化描述是，给定 c>0,Wi>0,Vi>0，1  i  n，要求找出一个 n 元 0-1 向量（x1， x2，……xn）， Xi{0,1},1  i  n，使得 iXiW c ，而且 n 1i  iXV 达到最大。因此 0-1 背包问题是一个特殊的整 i n 1i  ixv i 数规划问题： max n  i 1      x i n  Cxw i i 1 i  1},1,0{ i   n 算法描述： 设所给 0-1 背包问题的子问题 max∑(Vk * Xk) k=i..n ； ； (k=i..n )； max∑(Vk * Xk)〈= j Xk ∈{0，1}，i〈=k〈=n 的最优值为 m（i，j）是背包容量为 j，可选择物品为 i，i+1，…,n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，我们可以建立计算 m(i ,j)的递归式如下： m(i，j) = max{m(i+1，j)，m(i+1，j-wi)+ Vi} m(i，j) = m(i+1,j) m(n,j) = Vn m(n,j) = 0 程序： #include #define Max 101 int m[Max][Max],w[Max],v[Max],x[Max]; void Knapsack(int c,int n) 0 <= j < wi j >= wn 0 <= j < wn j >= wi 第 3 页 共 14 页 3
    0-1 背包问题的算法设计策略对比与分析 { int jMax=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=min(w[i]-1,c); for(int j=0;j=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } void Traceback(int c,int n) { for(int i=0;i0,1<=i<=n.这个问题称为背包问题（Knapsack problem）。 算法描述 首先计算每种物品单位重量的价值 Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重 量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过 C，则选 第 4 页 共 14 页
    2006 级软件方向算法设计与分析课程考查论文 择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 程序代码： #include struct goodinfo { float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号 }; void Insertionsort(goodinfo goods[],int n) { //物品信息结构体 int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; }} //按物品效益，重量比值做升序排列 void bag(goodinfo goods[],float M,int n) { float cu; int i,j; for(i=1;i<=n;i++) goods[i].X=0; cu=M; for(i=1;icu)//当该物品重量大与剩余容量跳出 //背包剩余容量 break; goods[i].X=1; cu=cu-goods[i].w;//确定背包新的剩余容量 } if(i<=n) goods[i].X=cu/goods[i].w;//该物品所要放的量 for(j=2;j<=n;j++) { /*按物品编号做降序排列*/ goods[0]=goods[j]; i=j-1; 第 5 页 共 14 页 5
    0-1 背包问题的算法设计策略对比与分析 while (goods[0].flag>n; goods=new struct goodinfo [n+1];// cout<<"请输入背包的最大容量："; cin>>M; cout<>goods[i].w; cout<<"请输入第"<>goods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比 cout<
    2006 级软件方向算法设计与分析课程考查论文 cout<<"press <1> to run agian"< to exit"<>j; } } 3.3 回溯算法 问题描述： 对于 0-1 背包问题回溯法的一个实例，n=4，c=7，p=[9,10,7,4],w=[3,5,2,1].这 4 个物品的单位重量价 值分别为[3,2,3,5,4].以物品为单位价值的递减序装入物品。先装入物品 4，然后装入物品 3 和 1.装入 这 3 个物品后，剩余的背包容量为 1，只能装入 0.2 的物品 2.由此可得到一个解为 x=[1,0,2,1,1],其相 应的价值为 22.尽管这不是一个可行解，但可以证明其价值是最有大的上界。因此，对于这个实例， 最优值不超过 22. 算法描述：0-l 背包问题是子集选取问题。一般情况下，0-1 背包问题是 NP 难题。0-1 背包问题的 解空间可用子集树表示。解 0-1 背包问题的回溯法与装载问题的回溯法十分类似。在搜索解空间树 时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进 入右子树搜索。否则将右子树剪去。设 r 是当前剩余物品价值总和；cp 是当前价值；bestp 是当前 最优价值。当 cp+r≤bestp 时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依 其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由 此得到的价值是右子树中解的上界。 程序： #include using namespace std; class Knap { friend int Knapsack(int p[],int w[],int c,int n ); public: void print() { for(int m=1;m<=n;m++) { cout<
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料