发布时间 : 星期一 文章基于算法本科最新毕业论文更新完毕开始阅读6a4eaa660166f5335a8102d276a20029bd64638e
第5章 删数问题
5.1 问题的提出
问题提出：给定n位正整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。 5.2 贪心算法策略
分析：n位数a可表示为x1x2?xixjxk?xn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为T，其最优解A=(y1，y2?yk)表示依次删去的k个数，在删去k个数后剩下的数字按原次序排成的新数。即最优值记为TA。
本问题采用贪心算法求解，采用最近下降点优先的贪心策略：即x1 先来证明该问题具有贪心选择性质，即对问题T删除最近下降点的数xj后得到的N1是n一1位数是中最小的数。 根据数的进制特点，对a按权展开得： a=x1*10n-1+x2*10n-2+?+xi*10n-i+xj*10n-j+xk*10n-k+?+xn 则有：Nl=x1*10n-2+x2*10n-3+?+xi*10n-i-1+xk*10n-k+?+xn 假设删去的不是xj而是其它位，则有 N2=x1*10n-2+x2*10n-3+?+xi*10n-i-1+xj*10n-k+?+xn 因为有x1 在进行了贪心选择后，原问题T就变成了对N1如何删去k-1个数的问题T’，是原问题的子问题。若A=(xj，A’)是原问题T的最优解，则A’是子问题T’的最优解， 其最优值为TA’。 证明：假设A’不是子问题T’的最优解，其子问题的最优解为B’，其最优值记为TB’，则有TB’ 因此，删数问题满足最优子结构性质。 从以上贪心选择及最优子结构性质的证明可知删数问题用贪心算法可以求得最优解。 5.5 编码 该问题使用C++编程实现，其时间复杂性为O(n)，空间复杂性为O(n)。 第6章 汽车加油问题 6.1 问题的提出 一辆汽车加满油后，可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少，设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。 6.2 编码分析 把两加油站的距离放在数组中，a[1..k]表示从起始位置开始跑，经过k个加油站，a[i]表示第i－1个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。 对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3??n （1）始点到终点的距离小于N，则加油次数k=0； （2）始点到终点的距离大于N时： A 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n； B 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点； C 加油站间的距离相等，即ａ[i]=a[j]=L D 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过贪心算法求解。 6.3 贪心算法策略 该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。 由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。 提出问题是解决的开始。为了着手解决遇到的困难，取得最优方案。我们可以假设 不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。 6.4 贪心算法正确性证明 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，因为m+N 最优子结构性质： 当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于（b[1]，b[2]，??b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1，则（b[2]，b[3]，??b[n]）是从a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2]，a[3]，??a[n]）的最优解，即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。 6.5 贪心算法时间复杂度分析 由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)。