最近正在接受数模班的超高强度培训,原来遵循的还是临时磨枪,不快也光的培训准则啊~~~~
92年全国数模大赛试题有一题是这样的:
组成生命蛋白质的若干种氨基酸可以形成不同的组合。通过质谱实验测定分子量来分析某个生命蛋白质分子的组成时，遇到的首要问题如何将它的分子量X(正整数)分解为n个氨基酸的已知分子量之和。某实验研究所研究的问题中，n=18，
a[1:18]={57,71,87,97,99,101,103,113,114,115,128,129,131,137,147,156,163,186}
给定某以蛋白质的分子量X(x=<1000)为正整数 。要求对该实验室拥有或不拥有计算机的情况作出解答。
我只节选了拥有计算机的情况的求解，里面的生物学相关部分由我们小组成员Luna Huang完成.
习作论文下载地址:
http://emilmatthew.51.net/lunwen1.rar
主要的想法就是用一棵搜索树来决定搜索的区间,我一时间也没有细想,用了n叉树,算法效率当然变得很低了.
还有关于这个算法的复杂度分析也一定不正确,希望大家给出点好的改进意见并指出不足.
算法部分简摘如下.(有些用公式编辑打的东东可能没有及时补上,希谅解,可以下word原文)
本问题可以抽像成下面这个算法模型:
给定一个序数字序列a[1…n],可以从中选出任意个数进行组合(如某组合为c[j]={a[i1],…,[im]}).序列a中的同一个数允许重复选择且重复次数没有限定.每个组均要满足一定的约束条件.
算法的组合依据:
如果按照遍历出序列中所有满足条件的组的思路,显然,这就是一个和组合相关的题目,不妨先假定对于升序的数字序列a[1-3], 从中选出任意个数组合成组.约束条件为:每个组的元素之和<=某个上限值X.既然元素是可以重复选择,很容易想到下面这个思路.
1)由于是和排列的位置无关,所以,先找出序列a[1…n]中所有有a[1](a[1]允许重复)的组的情况:
一个元素:a[1]
两个元素:a[1]a[1],a[1][2]…,a[1]a[3]
三个元素a[1]a[1]a[1], a[1]a[1]a[2] , a[1]a[1]a[3],a[1]a[2]a[1],…,a[3]a[3]a[3]
….
每个组停止继续扩展的条件为假设中的约束条件.
如:若a[1]+a[1]+a[1]>L,则a[1]a[1]a[1]组就不可能扩展更多的组了(因为序列是升序排列的),因而停止扩展.
又若a[1]a[1]a[2]<=L,则a[1]a[1]a[2]组就还能扩展出更多的组,
如a[1]a[1]a[2]a[2],a[1]a[1]a[2]a[3]
2)接下来,是在剩余的所有满足约束条件的组中找出有含有a[2]的组,由于前面已找完了所有有a[1]的组情况,所以,这里不用再考虑a[1]了.
一个元素:a[2]
两个元素:a[2]a[2],a[2][3],…,a[2]a[n]
三个元素a[1]a[1]a[1], a[1]a[1]a[2] , a[1]a[1]a[3],a[1]a[2]a[1],…,a[3]a[3]a[3]
….
每个组停止继续扩展的条件同上.
3)最后是a[3]: 由于前面已找完了所有有a[1],a[2]的组情况,所以,这里不用再考虑a[1],a[2]了.
一个元素:a[3]
两个元素:a[3]a[3]
三个元素a[3]a[3]a[3]
…
当a中的元素个数为n时,可按同样的原理使其中的元素成组.
根据组合中的知识,可以肯定,这样的搜索方式,可以完全的将所有的情况遍历到.这是下面算法正确的前提.而由n个元素的成组情况依赖于n-1个元素的成组情况,可以很容易的看出,这样的关系可以完全的用一棵搜索树来表示.于是,有了下面的算法思路.
３算法思路
假设约束条件同上,将序列a[1-3]改成a[1…n].
1）．首先,要保证这是一个按升序排列的序列(可用一个排序算法实现),这是实现本算法的前提.因为约束条件上限的给定是必须的,否则搜索将无法终止.又由于是对组中元素求和,所以升序保证了不会有结果遗漏.
2）．1对这个问题的求解,采用深度优先遍历算法,对n(n为序列的长度)棵生成树(每棵生成树的规模依次为i(i=n,n-1,…1)叉树)实现前序遍历搜索,至到所有树均达到搜索终止条件时,算法终止,并完成了对所有符合条件组合的遍历.
2）．2对所产生的搜索树作如下说明:
a)搜索树中各结点所标注的整数i (i=1,2,3…n),代表该结点的权值对应的是序列中a[i]
的权值,即w(a[i]).
b)这里所说的路径,除非特别注明是从a结点到b结点的路径,均指从根父结点出发的,到某个终止根子结点的路径.
c)搜索树的某条路径的终止条件：
自这棵树的根父结点起,沿该条路径的各个根子结点的权值之和:
大于了限定值X时,即终止该条路径的继续搜索.
d)每条搜索路径的生成方式：
如v结点代表的是序列中的第i个元素，在该结点满足了继续搜索的前提条件下（见2.2.c），在其下生成n-i+1个长度为1的子路径,每个子路径的结点依次代表a[i],a[i+1]…a[n].其余结点的生成方式依次类推。
2）.3搜索树中路径对应的组合结果的说明：
a)由于某路径的终止条件是在访问了该路径的根子结点之后产生的，所以，生成的n棵树的根子结点全部要剔除，不能算作最后的组合序列。下面所指的有效路径，均指剔除了根子结点的路径。
b)根据成的结果树对应的有效组的说明：
在每一棵结果树中，自父根结点
在这条子路径上，取其中的任何一个结点作为终止结点
现举数序列为a[1..4]={1,2,3,4},上限值Ｌ为4的情况，来说明算法:
根据算法所产生的搜索树是这样的:
由2）.3.a得到最后的有效组合的结果树:
通过程序得到的输出结果的表示形式为
--1
--1
--1
--1
--2
--2
--3
--2
--2
--3
--4
这种表示类似于书的目录格式，相当于把上面这棵树左转90度后，再上下翻转180度,即得.
４算法正确性的说明:
１）约束条件是否能达到的证明：
对于某树中的第k条路径的第h+1个结点,在程序中可以通过递归函数,得到到前一次的路径的权值和(
则若d1&&d2
若e1||e2
故约束条件是完全可达的．
２）是否能遍历所有情况的说明：
根据算法的组合依据可以说明本算法是正确的．
３）是否有重复计算情况的说明（所有情况是否独立）：
a)由于采用的是树的前序遍历的算法，所以可以保证树上的每个结点仅会被访问到一次，不会出现重复计算访问次数的情况。
b)可以参考算法的组合依据的说明.
５算法效率分析:
仍取序列为a[1…n], 约束条件::每个组的元素之和
最好情况下搜索树高度：
最坏情况下搜索树高度：