组合算法（精选9篇）
组合算法 篇1
1 问题提出
最近认真学习了王建德教授的“基因繁衍”题, 题目的数据量很大, 王教授采用乘法原理来计算, 看起来很是完美, 不过后来手工列出所有组合数据, 验算了一下, 竟然发现结果不吻合。于是去掉了原来的%10000操作, 为的是和手工验算的数据进行对比。当数据量小时, 运算结果则是正确的, 当数据量很大时, 则是错误的。
1.1 原始题目
某种基因按照下述规律繁衍, 即第1秒, 产生基因1号, 该基因可以繁衍其他基因, 之后每隔一秒, 基因1号都可以繁衍出一个新的基因。第m秒繁衍出的基因编号为m, 称它为m号基因 (m>=2) 。m号基因诞生后继续繁衍, 但每隔m秒会休息一次。比如3号基因, 会在第6、9、12, ...秒休息, 而其他时间都处于繁衍期。
基因休息时, 它的记忆会被移植到当时出生的基因中。比如6号基因诞生时, 2号和3号基因正在休息, 因此, 6号基因会收到2号和3号基因的记忆副本。称2号和3号基因是6号基因的父基因。显然, m号基因的父基因是它的质因子。如果两个基因没有父子关系, 且没有共同的父基因, 则成为这两个基因的编号是互质的。注意:1号基因与其他所有基因的编号是互质的 (因为只有1号才会繁衍基因) , 它也不是任何基因的父基因。
一个基因的独立数是指所有编号比它小且与它互质的不同基因的个数。比如1号基因的独立数为0, 2号基因的独立数为1 (1号基因与它互质) , 6号基因的独立数为2. (1号和5号基因与它互质, 2号和3号基因都是它的父基因, 而4号基因与它有共同的父基因---2号基因。)
新繁衍出来的基因有3种不同的类型。对于编号为m的基因, 如果能把m分解成偶数个不同奇素数的积, 则它是第一类基因。例如15号基因 (3*5) ;否则, 如果m本身就是奇素数或者能把m分解成奇数个不同奇素数的积, 则它是第二类基因, 例如3号基因, 165号基因 (3*5*11) 。其他编号的基因都是第三类基因, 例如2号基因、6号基因和9号基因。
第m秒诞生了基因m号, 我们想知道它和它的父基因中, 所有第一类基因的独立数之和, 所有第二类基因的独立数之和, 以及所有第三类基因的独立数之和。能够解决这个问题吗?
为了方便计算, 已经做了m的素因子分解。为了方便输出, 只要求输出总和除以10000的余数。例如, M有3个不同的素因子:第1个素因子为2, 指数为1;第2个素因子为3, 指数为2;第3个素因子为5, 指数为1。显然m=2*3^2*5=90。90号基因有10个父基因, 加上它自己共11个。其中第一类基因只有15号;第二类基因有3号和5号;第三类基因有8个, 它们的编号分别是2、6、9、10、18、30、45和90, 即基因90号和它的父基因中, 所有第一类基因的独立数之和除以10000的余数为8, 所有第二类基因的独立数之和除以10000的余数为6, 所有第三类基因的独立数之和除以10000的余数为75。
输入:第1行是一个正整数k (1<=k<=1000) , k是m的不同的素因子个数。以下k行, 每行两个整数, pi和ei分别表示m的第i个素因子和它的指数 (i=1, 2, ..., k) 。p1, p2, ..., pk是不同的素数, m=p1^e1*p2^e2*...pk^ek。所有素因子按照从小到大排列, 即p1
输出:包括3行, 第1行是基因m号和它的父基因中, 所有第一类基因的独立数之和除以10000的余数;第2行是基因m号和它的父基因中, 所有第二类基因的独立数之和除以10000的余数;第3行市基因m号和它的父基因中, 所有第三类基因的独立数之和除以10000的余数。
1.2 解题思路
用组合数学的方法解此题。
(1) n的独立数是欧拉函数f (n) 的一个特例
一个数n的欧拉函数f (n) 指小于n且与n互质的数的个数。将n分解成素数的乘积n=p1^e1*p2^e2...*pk^ek。f (n) = (p1-1) *p1^ (e1-1) * (p2-1) *p2^ (e2-1) ...* (pk-1) *pk^ (ek-1) 。所谓一个数n的独立数是欧拉函数f (n) 的一个特例, 指小于n且与n互质的不同数的个数。
将n分解成不同素数的乘积n=p1p2...pk, 即欧拉函数f (n) 中e1=e2=...=ek=1, p1!=p2...!=pk, 因此f (n) = (p1-1) (p2-1) ... (pk-1) 。
(2) 计算具有i个不同的奇素因子 (即i个素因子都大于2) 的独立数之和
将m分解成k个不同素数的乘积m=p1p2...pk。m的欧拉函数 (小于m且与m互质的数的个数) f (m) = (p1-1) (p2-1) ... (pk-1) 即为m号基因的独立数。例如6号基因的独立数为f (6) = (2-1) * (3-1) =2。由于试题要求计算基因编号所含的不同奇素因子的个数k', 因此p1=2时, k'=k-1;p1!=2时, k'=k。设s[i]=具有i个不同的奇素因子 (即i个素因子都大于2) 的独立数之和。显然s[0]=1。依次枚举奇素因子pt, pt+1, ..., pk (p1=2时, t=2;p1!=2时, t=1) , 每枚举一个pi, 则根据乘法原理将s[j-1][pi-1]计入s[j]。例如, k=3, p1=2, e1=1;p2=3, e2=2;p3=5, e3=1。由于p1=2, 因此依次枚举p2和p3。
枚举p2:s[3]=s[3]+s[2] (p2-1) =0, s[2]=s[2]+s[1] (p2-1) =0, s[1]=s[1]+s[0] (p2-1) =0+1*2=2。
枚举p3:s[3]=s[3]+s[2] (p3-1) =0, s[2]=s[2]+s[1] (p3-1) =0+2*4=8, s[1]=s[1]+s[0] (p3-1) =2+4=6
由此得出s[0]=1, s[1]=6, s[2]=8。S序列的计算过程如下:
(3) 计算所有第二类基因的独立数之和与所有第一类基因的独立数之和
对于编号为m的基因, 如果能把m分解成偶数个不同奇素数的积, 则它是第一类基因;如果m本身就是奇素数或者能把m分解成奇数个不用奇素数的积, 则它是第二类基因。试题要求计算基因m号和它的父基因中, 所有第一类基因的独立数之和与所有第二类基因的独立数之和。设tot1为所有第二类基因的独立数之和, tot1=∑ (s[i]|i为奇数) mod 10000;tot2为所有第一类基因的独立数之和, tot2=∑ (s[i]|i为偶数) mod 10000例如, k=3, p1=2, e1=1;p2=3, e2=2;p3=5, e3=1。按照上述方法得出s[0]=1, s[1]=6, s[2]=8。显然, 所有第二类基因的独立数之和tot1=s[1]=6;所有第一类基因的独立数之和tot2=s[2]=8。按照下述方法计算tot1和tot2:
(4) 计算所有第三类基因的独立数之和
对于第三类基因的独立数之和, 无法正面求解, 但可以通过求解n的所有约数的独立数之和来求第三类基因的独立数之和。记n的所有约数的独立数之和为tot3, 由乘法原理可得:
根据“第三类基因是除第一、第二类基因外的其他编号的基因”的题意, 所有第三类基因的独立数之和应该等于m-tot1-tot2-1。例如, k=3, p1=2, e1=1;p2=3, e2=2;p3=5, e3=1。按照上述方法得出m=2*3^2*5=90, tot1=s[1]=6, tot2=s[2]=8, tot3=m-tot1-tot2-1=90-6-8-1=75。
由于输出格式是所有第三类基因的独立数之和除以10000的余数, 因此应该计算 (m mod 10000+30000-tot1-tot2-1) mod 10000 (加30000是为了保证被除数是正整数) 。
1.3 原始算法代码
1.4 重建的算法代码
1.5 原题运算结果及验算结果
(1) 原题运算结果
所有第一类基因的独立数之和是510;
所有第二类基因的独立数之和是644;
所有第三类基因的独立数之和是16007145。
(2) 验算结果
第一类独立数之和是644;
第二类独立数之和是390;
第三类独立数之和是16008047。
2 全部组合算法
2.1 问题引入
题目的实质就是求出全部长度的组合, 然后计算独立数之和。网上见过了很多排列的算法, 包括全排列算法。组合算法也就是根据公式来计算, 只有结果, 也不实用。以前编写过一个最新组合程序, 但是算法太过复杂, 不实用。有没有既简单又实用的算法呢?于是又进一步分析。
2.2 算法思路
设置输出长度从1到n, 依次输出各种组合, 使用一个逻辑数组B[], 设置输出状态。在输出过程中要判断是否有重复输出, 使用判重函数判断单个位置是否重复输出, 使用栈保存起始位置到倒数第二个位置, 然后输出完后恢复栈中存储的位置, 设置为未输出状态。比如:1 2 3 4 5 6, 当要输出1 2 3 45 7时, 首先要保存1 2 3 4 5的位置, 输出1 2 3 4 5 6后, 恢复1 2 3 4 5位置为未输出状态 (B[i]=false) , 然后再次输出12 3 4 5, 当到6位置时, 因为前面已经输出, 所以输出1 2 34 5 7, 到n位置输出后, 起始位置start+1, 并设置从start位置到最后位置n的输出状态全部为false (B[i]=false) 。直到全部长度的组合输出完毕。
2.3 算法代码
2.4 输出结果
共有670个组合序列。
2.5 100个数 (n=100) 的输出结果
共有4416325个组合序列。
3 结语
全部组合算法简洁明了, 功能特别强大, 而且很实用。为了完善此代码, 经过多天的日夜构思算法, 调试代码, 而调试时的繁杂和艰辛 (连续6个小时) 更是要坚强的毅力才能够完成的。坚定的信念加百分的努力一定会有理想的结果。
试想一下, 这只是100个位置的全组合输出, 如果是1000个, 10000个, 100000000个呢?只要有足够的时间, 本程序都可以全部输出, 而且不会造成数据溢出。
摘要：最近认真学习了王建德教授的“基因繁衍”, 题目的数据量很大, 采用乘法原理来计算, 看起来很是完美, 不过后来手工列出所有组合数据, 验算一下, 可以发现与结果不符。采用全部组合算法, 简洁明了, 功能强大实用。
关键词：基因繁衍,乘法原理,组合,全组合
组合算法 篇2
车载SINS/GPS组合导航系统的在线标定算法
从工程实用和维护的角度出发,提出一种针对于车载组合导航系统的.在线标定算法.该算法使用卡尔曼滤波作为估计工具,通过趋于一般运动状态的路径设计对待标定的误差项进行有效激励.仿真卡尔曼滤波结果表明,该算法使得待标定的各误差项根据车行轨迹在较短的时间内逐步收敛,实现在一般跑车实验中不拆卸惯性器件而达到标定的目的.这种在线标定的处理方法在实际使用和维护具有极大便利.
作 者：白俊卿 卫育新 作者单位：中国航天科技集团第16研究所,陕西,西安,710100 刊 名：电子设计工程 ISTIC英文刊名：ELECTRONIC DESIGN ENGINEERING 年，卷(期)： 18(2) 分类号：V19 关键词：组合导航系统 在线标定 卡尔曼滤波 路径设计 激励间接模式映射组合算法研究 篇3
网络中的数据源之间存在大量映射关系。图1给出了一个数据共享网络的拓扑结构示意图。当数据源E需要获取集成模式下的数据时需要将E上的查询通过E到C、C到A和A到集成模式之间的映射关系,转发到集成模式上。当E到集成模式的映射路径不唯一时,返回的数据结果可能不同。在数据交换中,为得到可靠的数据,需要得到所有映射路径,当数据源规模庞大时,执行的代价很高。尤其当某个节点,例如C离开网络时,E到集成模式的映射路径将断开,此时会造成数据的丢失,映射组合可以较好的解决该问题,通过预先组合映射路径上的映射,可以直接得到数据交换对象之间的映射关系,节省查询在映射链上传递带来的开销。
随着时间的推移、应用需求的变更以及系统的更新换代,数据源间原有的直接映射演变成了间接映射,在映射组合时需要间接映射带来的影响。大部分组合映射的研究对象主要是直接映射[1,2,3,4,5],包括基于逻辑的方法、基于约束关系的方法以及模式转换的方法[5,6,7]等。基于转换的方法需要定义复杂的模式转换操作,不支持包含复杂模式结构元素组合运算的间接映射;现有的非直接映射的研究主要考虑目标和源模式之间的非直接映射定义以及基本操作[8],而很少考虑组合问题。
Yu和Popa等讨论了嵌套关系模式下基于SOtgd[3]的映射组合问题。提出一种映射组合算法,支持嵌套模式。Nash等[4]研究了非source-to-target情况下一阶逻辑约束描述的映射组合问题。Berstein等研究了非source-to-targe下的映射组合问题[9],扩展了Nash和Fagin等的工作。映射组合的求解主要采用逐步消除中间模式符号(记为BECA)的方式,然而Berstein等也说明了某些情况下中间模式可能无法完全被消除,此时不是完全意义上的组合映射,主要原因是间接映射的存在。本文主要研究间接映射的组合机制,给出了间接映射的组合算法和实验分析。
2 映射组合概述
定义1令R1、R2为二元关系,R1和R2的组合R1°R2定义为二元关系:,“°”为组合运算符号。
令Inst(M)表示映射的实例,下面利用二元关系Inst(M12)和Inst(M23)来定义映射M12和M23的组合。
定义2[3]令为两个映射模型,其中S1,S2,S3两两没有公共元素符号。当Inst(M)=Inst(M12)°Inst(M23)时,映射为M12和M23的组合映射,满足,其中Ii为模式Si的实例,1≤i≤3。
图2给出了以S2为中间模式、S2的实例为中间实例的直接映射组合,实现在已知M12和M23的情况下S1和S3的直接数据交换。
3 间接映射定义
间接映射是指源模式的某个或若干节点的实例经过一定的代数运算后映射到目标模式的某个或若干节点实例的代数运算结果上,如图3所示。
在映射[1]中,方框中的节点实例经过代数运算后整体映射到目标模式的一个元素的上。下面给出代数运算定义。
定义3间接模式元素关联定义为具有间接映射关系的模式元素的关联关系集合。令φS为S的公式集合,Si为S的Scheme,则代数运算具有下面的四种形式,这里用模式来代替对应的实例集合:
(1)并集映射:具有类似的形式
(2)笛卡尔积映射:
(3)投影映射,表示为:
(4)选择操作映射:
令为模式元素的代数运算操作符,间接映射下的源模式公式可表示为:。以图4为例,M12表示为:
4 间接映射组合机制
考虑图4给出的映射关系,虽然M12和M23有公共的模式S2,但无法根据M12和M23直接建立S1到S3的映射关系,更无法直接给出组合映射的表达式。如果直接进行组合,S1只能映射到S3某个元素的一部分,在数据交换时,需要S2下实例的参与才能得到S3下完整的实例,因此根据直接映射组合进行数据交换时可能丢失信息。本文提出算法的主要思想是构建一个可进行直接映射组合的扩充模式,并保证该模式实例与原有模式的实例在广义同态函数下同构。采用基于中间模式的模式元素数据回流策略,定义扩展模式,实现间接映射的组合。相比BECA方法,数据回流能够消除中间模式的影响。
定义4令为包含间接映射的映射模型,其中为形如的公式集合,从S到T为广义sound类型映射[10]。令DomM(S)为S的映射域,Dom(T)为T的有效域,有。令T参与间接映射的变量集合为yIn,S参与间接映射的变量集合为xIn,构建S下的虚拟元素集合yIn-xIn。如图5所示,记得到的新源模式为S′,则可以在映射域DomM(DomM(S))上建立T到S′的直接映射。若表示S′到T的映射,则记为的逆映射,虚拟元素的构建过程称为模式元素回流过程,简记为模式回流。
定义5令S1,S2,S3为两两没有公共符号的模式,为间接映射。根据定义4.12构建包含虚拟元素的新的源模式S′1,得到映射,同时根据逆运算构建新映射,得到新的映射模型为。若,即满足:,则称M为M12和M23的组合间接映射。
5 间接映射组合生成算法
图6中,虚线给出了新模式元素与中间模式的对应关系。可以看出,当源模式S1添加虚拟元素成为S′1时,可直接建立S′1到S3的组合映射。同直接映射不同,数据交换时,中间模式的部分元素对应的数据将首先回流到源模式下,在源模式和目标模式的数据交换过程中存在反向数据流动。
5.1 组合算法
基于模式回流的间接模式映射组合的算法(ElementsBackbasedMappingCompositionAlgorithm,简记为EBMC):
Algorithm EBMCInput:映射
Output:映射。
(1)初始化和。对和中的变量和关系进行重命名操作,保证不存在名称相同的变量和模式名称。
(2)数据回流和虚拟元素构建。若存在S1到S2的映射:andS2到S3的映射:,满足,则对所有满足条件的i,取投影操作,得到属性集合E={E1,…El},其中Ei为操作得到的属性集合。
将Ei添加到S1中,并与其对应的进行属性组合,该过程为一个模式回流过程。
(3)S12、S23构建。初始化两个空集合S12、S23,假定的蕴涵式形式为:
将每个中的公式,添加到S12中,类似的处理,得到包含的公式集合S23。对每个S12中的公式,其中x为全称量词量化变量,xj为x上的项,1≤j≤k。
用k个包含原子公式的蕴涵式来替换每个S12中的χ,得到:
(4)S12、S23组合。取S23中的形如ψ※γ的公式χ,对ψ中存在的每个R(y),通过如下步骤用S′1上的原子公式替换R(y)。
令为所有S12中的公式,且其右侧包含R,
若S12中不存在该公式则从S23中移除χ;
否则对的变量进行重命名,使其不与χ中的变量名称重复;
从S23中移除χ,通过如下方式添加p个公式到S23中:将χ中的所有R(y)替换成φi,并将结果添加到S23中(1≤i≤p)。
重复上述步骤,直到S23中的所有公式左侧的子模式符号都来自于S1。
(5)构建M13。令S23=(χ1,…,χr),其中χ1,…,χr为前面得到的蕴涵式,则,其中zi为χi出现的所有变量,1≤i≤r。。
算法给出的组合映射的生成前提是需要维护一个新的源模式,而该模式在其他组合映射中可能无法直接使用,但在大规模数据交换情况下,维护该扩展模式能够提高数据交换效率。
5.2 复杂度分析
令S1、S2和S3所包含的模式元素个数分别为N1、N2和N3,并令初始化和的重命名操作复杂度为O(N1×N2×N3)。
令S2到S3以及S1到S2的映射集合包含的映射元素分别为N23和N12,N12和N23都是原子模式元素(未参与组合运算)的个数。于是模式回流中需要构建的虚拟元素个数为N23-N12,得到构建虚拟元素的复杂度为O(N23-N12)。
组合过程的复杂度由和中所包含的原子公式数量确定。令包含的形如的公式的个数为N 12C,而每个ψi包含的原子公式为n12i个,得到的原子映射集合元素为N 12C×n12i个。若中形如的公式个数为N 23C,其中ψi为原子公式集合,则替换过程中需要匹配的原子公式对的数量为N 12C×n12i×N 23C。于是组合过程的复杂度为O(N 12C×n12i×N 23C)。由此得到模式回流策略下,组合映射生成算法的复杂度为:O(N1×N2×N3)+O(N23-N12)+O(N 12C×n12i×N 23C)。
而直接映射组合过程的复杂度为O(N1×N2×N3)+O(N 12C×n12i×N 23C),二者都是多项式级的复杂度
6 实验分析
考虑图4给出的情况,对S1到S3的数据交换效率进行实验分析,对比在不同数据实例规模下,根据非间接映射组合以及间接映射组合进行S1到S3的数据交换过程执行时间。实验数据库为Oracle,记录读写时间是记录规模与属性数量的增函数。
在非组合映射情况下,S1的数据实例{I1}根据映射M12转换到S2下,记为{I2},{I2}再根据M23转换到S3下,得到{I3}。数据读写主要发生在三个模式之间。在组合映射情况下,采用回流策略,S2部分属性的数据实例首先回流到S1下,得到新的数据实例{I′1},然后根据组合映射M13得到S3下的数据实例{I3}。图7左侧给出了不同数据实例输入规模下,数据交换执行时间的对比。
下面考虑BECA与EBMC的对比,BECA方法通过代数运算来逐步消除中间模式元素,核心思想是通过等价替换,将中间模式的符号尽量的替换成目标和源模式下的符号,因此,消除的模式元素可能分别包含了目标和源模式下元素。实验给定目标模式、源模式以及参与间接映射的中间模式元素规模,令BECA方法中可能参与消除的模式元素数量服从均匀分布,回流模式元素的数量由EBMC算法的第(2)步确定。图7右侧给出BECA消除中间模式元素数量与EBMC模式元素回流数量的对比。
7 结束语
间接映射组合过程中,中间模式对BECA与EBMC两种方式得到组合映射的影响基本相同。同时,EB-MC中回流的元素基本上等于BECA中未消除的元素数量,但IMCA能够完全消除中间模式的影响,实现真正意义的组合。
参考文献
[1]Madhavan J,Halevy A Y.Composing Mappings Among Data Sources.VLDB03,Berlin,Germany,ACM,2003,572-583
[2]Nash A.Foundations of Information Integration:学位论文.SAN DIEGO:UNIVERSITY OF CALIFORNIA,2006.
[3]Fagin R,Kolaitis PG,Popa L.Composing Schema Mappings:Second-Order Dependencies to the Rescue.ACMTODS,2005,30(4):994-1055
[4]Nash A,Berstein PA,Melnik S.Composition of Mappings Given by Embedded Dependencies.PODS2005,Baltimore,Mary-land,USA,ACM,2005.
[5]McBrien P,Poulovassilis A.Data Integration by Bi-Directional Schema Transformation Rules.ICDE03,Boston,USA,IEEE,2003,227-238
[6]Bo.M,Kittivoravitkul S,Lazanitis C,et al.AutoMed:A BAV Data Integration System for Heterogeneous Data Sources.CAiSE04,Riga Latvia,Springer Verlag LNCS,2004,82-97
[7]Bo.M,McBrien P.Comparing and Transforming Between Data Models via an Intermediate Hypergraph Data Model.COMPUT-ER SCIENCE,2005,373069-109.
[8]LiXu,Embley D W.A Composite Approach to Automating Direct and Indirect Schema Mappings.Information System,2006,31(8):697-132
[9]Berstein PA,Green TJ,Melnik S.Implementing mapping composition.VLDB Journal,2008,(17):333-353
组合算法 篇4
北斗/罗兰组合导航系统中伪距导航定位解算新算法研究
为提高北斗/罗兰组合导航系统伪距导航定位解算的.精度和改善对动态目标的实时跟踪,本文提出了一种新方法,采用镜像映射法解具有病态的矛盾方程组以提高精度,以及将伪距导航定位解算方程模型转换为具有贯序输入输出数据的系统辨识模型,然后用递推最小二乘法,对所求的北斗/罗兰组合导航系统伪距导航定位信息-接收机的三维位置参数和时钟误差参数进行动态快速实时估计.
作 者：王明福 王仕成 罗大成 张安京 WANG Ming-fu WANG Shi-cheng LUO Da-cheng ZHANG An-jing 作者单位：第二炮兵工程学院301教研室,西安,710025刊 名：电光与控制 ISTIC PKU英文刊名：ELECTRONICS OPTICS & CONTROL年，卷(期)：13(4)分类号：V474.2关键词：北斗/罗兰组合导航系统 伪距 实时 镜像影射 递推最小二乘法
组合优化问题的人工鱼群算法应用 篇5
1 人工鱼群算法
1.1 人工鱼群算法的定义
人工鱼群算法是2003年邵之江、李晓磊等人首次提出来的。它表示在一片水中,鱼一般能自行或者跟随其他鱼群找到营养物质较多的地方,所以,鱼存在数量最多的地方一般就是本片水域中物质营养最多的地方,人工鱼群算法就是利用这一特征,通过组建构造人工鱼来模拟鱼群的寻找吃食、聚集鱼群及相互追尾行为,从而实现寻优目标化。
1.2 人工鱼群算法的几大特点
简单性:在算法中仅能使用目标问题的函数值;
并行性:许多AF并行进行搜索;
快速性:算法中虽然也存在一定的随机因素,但整体是在逐步向最优搜索的;
全局性:算法具有跳出部分极值的功能,使不受局部极值的限制和影响;
跟踪性:随着工作状况或其他因素的改变而造成极值的变化,人工鱼群算法具有迅速跟踪变化的能力。
2 人工鱼的几种典型行为
1)觅食行为:一般正常情况下鱼往往在水中自由自在游动,当发现食物后,就会向食物逐步增多的方向飞速游去。
2)聚群行为:鱼在水中游动的过程,为了保证自身的生存条件,躲避外界危害,会自然而然地聚集成群,鱼聚群所遵守的原则有3条:分隔原则:尽可能避免过度与临近鱼群伙伴造成拥挤;对准原则:尽可能与附近伙伴的游动方向保持一致;内聚原则:尽可能朝附近鱼群伙伴的中心游动。
3)追尾行为:当鱼群中有鱼发现食物的地点并且快速朝食物移动时,其临近的鱼群会尾随此鱼快速来到食物点。
4)随机行为:单独的一条鱼在水中通常都是无规则游动的,这就是为了更大范围面积地寻找食物点以及身边的鱼群伙伴。
5)行为选择:根据所需要解决问题的性质,对人工鱼所生活的环境进行评价,从而选择一种行为方式。较常用的评价方法就是选择能使组合最优化的行为,亦是各个行为中使得人工鱼接下来是一个最优状态的行为,如果没能使接下来的状态最优,则采取随机行为。
3 具体人工鱼算法
综合以上的人工鱼的行为,各个人工鱼探究它目前所处的环境状况和鱼群状况,从而来选择一种适合的行为来实际执行,最终人工鱼聚集在几个极值的周围。一般情况下,在讨论求极大值时,拥有较大的适应值的人工鱼一般处于值较大的极值周围,这利于获取整体极值区域,而且较大的极值区周围一般也能集结许多的人工鱼,这有助于判断并且获取整体极值。具体的人工鱼算法步骤如下:
步骤1:确定种群规模数量结构为N,在变量可行域内生成N个个体,设定人工鱼的可视区域,步长为Step,拥挤度因子为&,尝试次数为try_number。
步骤2:计算初始鱼群各个体适应值,取最优人工鱼状态以及它的值赋在公告板。
步骤3:个体通过寻找食物,鱼群聚集,追尾行为更新自己,生成新鲜的鱼群。
步骤4:评价所有个体。如果某个个体有鱼公告板,则将公告板更新为该个体。
步骤5:当公告板上最优解达到满意的误差范围内,算法到此结束,不然,回到步骤3。
4 人工鱼群算法的实例应用
4.1 求解旅行商问题
对人工鱼群算法在组合优化问题中的应用研究,现将它应用的具体事例,通过对TSP的研究对这整个研究具有重大的实践性和理论基础。TSP问题是一个具有背景和重要理论价值的组合优化难题,许多关于TSP的工作并不是直接推动的,而是因TPS为其他算法提供平台,使得这些算法应用于离散优化的问题,再者,TSP的大量直接应用给研究分析领域带来了勃勃生机,并指引未来工作。
旅行商问题也被称作“旅行推销员问题”,就是指1名推销员要访问许多个地点时,怎样寻找在拜访每个地点一次后再回到最初起点的最短路线。原则虽然简单易懂,可是在地点数目剧增后求解就非常复杂难办。以五十二个地点为例子,要列举所有路线以后再确定最佳行径,那么总路线数目惊人,几乎不可计算。多年来全世界许多有名数学家挖空心思试图找到一个高效简单的算法。TSP问题在物流中的阐述是对应一个物流配送公司来说的,想要将N个客户的订货沿最短路线全部及时送到。
4.2 求解车间作业调度问题
车间作业调度是一个典型的NP—hard问题,亦是组合优化问题领域中研究的重要选题。对JPS的研究具有举足轻重的现实意义和理论基础。车间作业调度问题是最最普遍,最复杂和最具难度的生产调整问题。目前对车间作业调度问题的研究多采取群智能算法和启发式算法,比如例粒子群算法、蚊群算法、遗传算法等等。但采用新型的人工鱼群算发直接解决JPS。
车间作业调度问题描述:
已知:有n个工件{J1,J2,…,Jn}在m台机器{M1,M2,…,Mm}上加工,每个工件以一定的次序在所有的机器上轮流加工,每个工件分成m个工序,而每个工序对应相应的加工机器。其中,工序的加工时间是给定。工件上的约束条件为:每个工件上的工序只能在上一个工序执行结束后,才能开始执行下一个工序。
5 结语
人工鱼群算法的提出者李晓磊等人对参数算法的影响进行了探讨,总体来说,整个算法对各参数的取值范围的容纳度还是非常大的。算法采用自上而下的设计方式,每个个体的行为都具有相对的独立和互补,使得整个算法的收敛性比较稳定,注重研究组合优化问题的人工鱼群算法应用的意义非凡。
摘要：优化组合问题在现实生活中应用普遍,而且工程代表性强,可是想要实现最优化求解不容易,当今组合优化求解的主要方式采用启发式算法。人工鱼群算法是新型的群智能优化的算法,它的原理简单易懂,收敛速度快捷,求解精度颇高。最近几年得到了重视和广泛应用。
关键词：组合优化问题,人工鱼群算法,旅行商问题,车间作业调度
参考文献
[1]李晓磊,路飞,田国会,钱积新.组合优化问题的人工鱼群算法应用[J].山东大学学报(工学版),2014,05:64-67.
[2]雷娟.人工鱼群算法在组合优化问题上的应用研究[D].西安理工大学,2012.
[3]郑晓鸣.人工鱼群算法的改进及应用[D].上海海事大学,2015.
[4]张汉强.人工鱼群混合智能优化算法及其应用研究[D].浙江大学,2013.
基于新型组合算法的语音降噪系统 篇6
关键词：VSLMS,子空间,组合降噪算法,SOPC技术,硬件实现
在各类语音增强算法中,时域最小均方(LMS)算法因为其结构简单、鲁棒性好和易于硬件实现等优点,被广泛采用[1,2]。但在实际应用过程中,LMS算法有两个缺陷:一是收敛速度慢,不适用于快速收敛场合;其它的滤波性能较大程度上取决于输入信号的特性,即输入信号自相关矩阵的特征值分布[4]。当背景噪声很强时,滤波性能会急剧下降。本文以解决这两个问题为出发点,采用组合算法改善输入信号和降噪效果,采用硬件实现提高收敛速度。基本思想是首先通过子空间算法改善输入信号特性,然后采用VSLMS滤波,最后进行硬件实现。
组合算法的硬件实现是一个具有挑战性的问题。本文在研究FPGA硬件系统的基础上,试图将软件算法映射到硬件电路来实现算法要求的结构。
1 算法介绍
1.1 子空间算法
子空间语音降噪法的核心思想是通过算法将含噪语音信号分解到有效信号子空间和噪声信号子空间中。考虑到误差因素的影响,在有效信号子空间会残余部分噪声信号,而噪声子空间只包含噪声信号。分解方法理论上可以使用奇异值分解方法,或是特征值分解方法[4]。本文选用特征值分解法,在有效信号子空间内分析原始语音信号。
定义一个纯净信号d,写成矩阵形式
其中,A=[A1,A2,…,AM]为K×M的矩阵;S=[S1,S2,…,SM]T是M×1的矩阵。
d的协方差矩阵表示为
假设S的协方差矩阵RS是正定矩阵,则Rd的秩为M,正定特征值和零特征值的个数分别为M和K-M个[5]。
设x表示和语音信号无关的K维加性白噪声,均值为0,噪声信号协方差矩阵Rx已知且正定,于是有
有了以上假设,可以使带噪信号表示为
则带噪信号协方差矩阵Rdx可以表示为
令λkdx和λdk分别表示Rdx和Rd的第K个特征值,则以下表达式成立
引入正交矩阵U将Rdx和Rd对角化,可得
从式(7)可以看出,当存在加性白噪声时,带噪信号dx(n)的自相关矩阵特征值由Λdx,1和σx2组成,构成第一部分的M个特征值为纯净语音特征值。构成第二部分的K-M个特征值由白噪声产生,为噪声特征值。同时将特征向量矩阵U的列向量分为两部分
空间S称为信号子空间;空间G称为噪声子空间。由子空间构造原理[6]可知S和G相互正交,且
于是有
综上所述,子空间语音降噪法就是将带噪信号语音空间分解为有效信号子空间和噪声信号子空间。然后去除噪声子空间,在信号加噪子空间内滤波恢复出近似纯净的语音信号。
1.2 VSLMS算法
LMS算法最早由Widrow和Hoff提出,该算法实现简单且计算量小,可以取得较好的滤波效果,因此是最简单也是应用最广泛的自适应算法[7]。自适应滤波器结构如图1所示,它是一个双输入闭环反馈系统,两个输入分别是原始信号d(n)(同时为期望得到的信号)和被噪声干扰的含噪信号x(n)。采用这种方法取得的最好结果是系统输出期望的信号,即信噪比无穷大。LMS算法的基本描述如下
其中,y(n)为滤波输出;x(n)位输入的含噪信号,d(n)为期望输出;e(n)为滤波误差用于下一次更新权值;w(n+1)为下一次迭代时的权值;μ为步长。由式(14)可以看出参数μ决定了w向量的更新速度即步长。该算法收敛的条件为0<μ<2/λmax。这里λmax是输入信号自相关矩阵最大特征值[8]。当迭代次数接近于无穷大时,权矢量w(n)的期望值将逼近最优解。μ值越大,算法收敛越快,同时稳态误差也越大,μ值越小,算法收敛越慢,但稳态误差也越小。由于固定步长的μ难以平衡滤波时的收敛性和鲁棒性,所以一般采用变步长LMS算法,在开始使用较大的μ值达到快速收敛后,减小μ值,以达到稳态效果并获得较小的超调量[9]。VSLMS算法基本原理表示如下
式中,N为采样点数,0<μ2<μ1<2/λmax。由于μ(n)是变化的,在开始阶段采用较大的步长μ1,使VSLMS算法比固定步长LMS算法具有更快的收敛速度。当算法接近收敛稳定时,采用较小的步长μ2,减小稳态误差。
2 组合算法
2.1 算法原理
组合算法的结构图如图2所示,带噪信号首先由子空间过滤掉一部分噪声,再将过滤后的信号作为VSLMS的输入。由VSLMS算法进行进一步滤波。
具体步骤如下:(1)将带噪语音进行子空间滤波,计算Rx和Rdx,得到带噪语音信号的协方差函数;(2)对该函数进行特征值分解,求出大于噪声方差的特征值,由这些特征值重新构成语音信号,即为增强后的信号;(3)由于存在语音失真和噪声冗余,将得到的语音信号通过VSLMS进行滤波;(4)在VSLMS滤波中,首先进行μ值估算。μ值主要由输入信号的信噪比决定,不同的信噪比决定不同的权值更新速度。本文采用式(9)估算μ值
其中,s=6.25,μ0=4.2,SNRd B=10log10SNR;(5)滤波后的信号反馈给VSLMS模块,计算对应的误差信号e(n)和权值更新,进行下一轮迭代。
2.2 算法仿真
根据上述分析完成组合算法后,使用Matlab评估组合算法的降噪效果。为检测算法性能,将3种算法分别进行仿真对比。从TIMIT中选取一段时长为5 s的声音和高斯噪声作为样本。采用Matlab进行仿真,图3(a)为原始语音信号和带噪信号波形图。使用组合算法对带噪语音信号进行滤波,滤波效果如图3(b)所示。
如图3所示,经过子空间算法后,语音信号已有大幅改善,但存在噪声冗余和语音失真。而经过VSLMS算法后,冗余噪声和语音失真被消除。可见组合算法在去噪效果上更为优良。
3 硬件实现
3.1 硬件设计
在数字信号系统设计中,最常用的3种硬件平台是ASIC,DSP和FPGA。ASIC能达到信号处理要求,但缺乏灵活性,设计周期长。DSP适用于数学计算,但它是串行结构,不适合高采样率的应用[10]。本文采用FPGA设计平台,组合算法的硬件结构如图4所示。
该硬件结构实现过程如下:系统上电后从Flash加载启动代码,由A/D模块负责对语音信号的实时采集,随后进入组合语音降噪算法模块,最后将处理信号由D/A编码输出。
为了将软件算法移植到硬件平台,可以采用多种方法。一种是采用DSP Builder转换到IP核,另外两种分别是VHDL和Verilog HDL硬件描述语言进行设计,目前基于这两种方法实现矩阵运算都已取得了一定的成果[11,12]。本文采用Verilog HDL语言,其具有易学易用、简洁高效、占用资源少等优点。编写FIR滤波器,分别加入子空间和VSLMS算法,生成子空间去噪和VSLMS去噪模块(8抽头,μ2=0.007 8)。在完成综合、布局布线、仿真等步骤后,利用Modelsim配合进行功能验证。
3.2 功能验证
为验证上述方案的可行性,需要对系统各部分进行功能验证。用正弦波作为原始信号,高斯白噪声作为噪声信号,调用Modelsim软件进行仿真。编写激励文件,模拟时钟信号和控制信号,得到的Subspace仿真结果和VSLMS仿真结果如图5所示。
3.3 系统实验方案设计
3.3.1 系统方案分析
整个系统采用模块化的思想,通过顶层设计文件完成各个模块连接。设计过程可以裁减,方便以后添加改善算法的特征模块,提高滤波性能。
3.3.2 语音采集模块
采集模块由FPGA开发板上扩展的音频采集电路实现,通过双麦克风对语音数据进行采样、量化、模数转换,将A/D转换后的原始信号、噪声信号数据分别存入ROM1、ROM2中,利用16位加法器将原始信号和噪声信号进行叠加来作为组合降噪系统的输入。
3.3.3 滤波处理模块
根据本文描述的流程设计滤波处理模块,主要包括空间去噪和VSLMS去噪模块。在Quartus II中完成对顶层文件进行编译和管脚分配,然后下载到对应的FPGA芯片中,整个组合语音降噪系统在上电后自动完成配置。
4 结束语
基于组合混沌映射的图像加密算法 篇7
随着网络技术和多媒体技术的迅速发展, 数字图像正在成为人们网络信息交流的重要载体, 所以图像的安全性自然成为人们所关心的问题。传统的加密算法并不适合进行图像加密, 如DES, AES, RSA, 因为用它们加密之后的图象相邻像素点的相关性很大, 不适合保密。应用混沌映射进行图像加密与传统算法相比, 有很多相似但又不同的特性[1,2,3]。例如, 传统加密算法对密钥敏感, 然而混沌映射对初始值和参数值敏感;传统加密算法通过多轮加密来扰乱和扩散数据, 而混沌映射通过迭代把初始区域扩散到整个相空间。传统加密是定义在有限集合, 而混沌映射是定义在实数集。现已有很多的专家学者应用混沌映射进行图像加密, 如YEN J C使用CKBA的加密方法[4];SCHARINGER J使用kolmogorov流的图像加密算法[5];Zhi-Hong Guan使用CAT映射进行图像置换加密[6]等等。
Logistic映射和Chen映射[7]都是典型的混沌映射, 它们都具有初值敏感性和参数敏感性。用Logistic映射产生的混沌序列通过排序来改变图像中各像素点的位置, 达到混淆的目的, 在此基础上, 应用Chen混沌系统对Logistic加密的结果通过改变各点的像素值再进行加密。由于混沌系统所独有的特性, 使得双重加密的结果更加安全。
2 加密算法
2.1 应用Logistic映射进行加密
Logistic映射的表达式如 (1) 所示, 它是一个典型的混沌映射。
其中Xn∈[0, 1], 当参数b取值范围为 (3.569, 4]时, 系统具有混沌特性。
一般用它产生的混沌序列直接对信息进行加密, 但是在计算机有限的精度下, Logistic映射进行迭代的结果会出现重复, 这会给密码分析者带来攻击的机会。如在3位有效数字下, 其有一个13个值的循环, (0.109, 0.338, 0.950, 0.190, 0.610, 0.946, 0.204, 0.650, 0.910, 0.328, 0.882, 0.416, 0.972, 0.109) 。如果把Logistic映射产生的双精度序列进行一下排序, 进而对图像的各像素点位置进行排序, 以此来达到置换像素点位置的目的, 就可以避免重复所带来的不安全性。
用MATLAB进行仿真实验, 其步骤如下:
a.选取一个M×N的灰度图像。
b.给定参数b值和Logistic映射的初值x0, 让系统迭代M×N次, 产生M×N个值, 并对其进行排序。
c.把图像的二维顺序按照先行后列的顺序变成一维顺序, 并根据步骤b最后的顺序相应的对图像进行排序。
d.恢复步骤c为二维图像, 即为加密之后的图像。
经过Logistic映射加密之后的图像已经达到了图像混乱的目的, 但是并没有改变原始图像中各像素点的像素值, 为了增加系统的安全性, 将加密后的图像再送入Chen混沌系统, 改变各像素点的值。
2.2 应用Chen混沌映射进行加密
Chen混沌系统的表达式如 (2) 所示, 它也是一个典型的混沌系统。
其中 (x, y, z) 为系统轨迹; (a, b, c) 为系统参数。当a=35, b=3, c=28时, 系统有一个奇怪吸引子, 处于混沌状态。Chen混沌系统的参数更多, 相对也更安全。用此系统对Logistic映射加密后的图像再进行加密的步骤如下:
a.给定Chen的初值x0, y0, z0, 让系统迭代M×N次。
b.将每次产生的三个序列值按照公式 (3) 进行计算:
其中函数fra是求三个序列平均值的小数部分;计算机的有限精度是15位, 小数最多占用14位, 所以将其放大1014使之变成正整数;图像的灰度值是在 (0-255) 之间, 所以将放大的正整数对256求余, 使结果也在 (0-255) 这个区间。
c.将Ki转化成二进制;将第一次加密产生的图像的各像素点的值也转化成二进制, 并将Ki与其逐个进行异或处理, 共M×N次。
d.将M×N个结果再转化成十进制, 变回二维图像, 完成第二次加密。
这样, 图象中各点的位置和像素点的值都发生了变化, 从而达到了混乱和扩散的要求, 增加了加密的安全性。其安全性主要在于混沌系统对初值的极其敏感性, 系统的初值有一个微小的变化, 其混沌轨道会发生根本的变化, 即所谓的“蝴蝶效应”。为了验证算法的可行性, 我们通过实验来进行仿真分析。
3 仿真实验
选取一幅104×102的灰度图像, 令Logistic映射中的参数b=4, 初值X0=0.7, 则原始图像和第一次加密之后的图像如图1所示。
令Chen混沌系统的初始值x0=-9.036, y0=0.768, z0=29.263, 则第二次加密之后的图像如图2中 (a) 所示;用所有正确的初值进行解密图象如图2 (b) 所示。
从图1和图2中可以看出, 经过Logistic映射后, 已经把图象的各像素点的位置进行了重新的排序;经过Chen混沌系统后, 已经混乱的图象, 通过改变其像素值, 再次进行了加密。
经过大量的实验, 对两个混沌映射选择不同的参数值, 加密之后的图像效果都是“面目全非”的;选择不同的图像, 以及不同大小的图像都能得到同样的加密效果, 这说明用此方法起到了很好的加密作用。
为了验证加密算法的有效性, 可以对该方法进行安全性分析。
4 安全性分析
4.1 密钥量分析
采用Logistic映射和Chen混沌系统进行双重加密的关键技术就是混沌系统本身的初值敏感性。如果我们将Logistic映射的初值x0和Chen混沌系统的初值x0, y0, z0都进行保密, 把他们当作密钥来处理, 按照计算机的双精度来计算, 密钥量可以达到1060, 可见整个系统的密钥空间是很大的。
4.2 敏感性分析
既然混沌加密的安全性就在于它的初始值敏感性, 那么当截获者对得到的密文图像进行破解时, 如果针对两次加密的初始值有一点点偏差的情况下, 也不能还原出原始图像。图3 (a) 是对两次加密的图像图2 (a) 用x0=-9.036, y0=0.768, z0=29.263000001进行解密的图像。我们看到初始值z0仅仅和原来有微小的差异, 可是却没有还原到图1 (b) 的状态;图3 (b) 是针对图1 (b) 用X0=0.700001进行解密的图像, 同样是小的差异, 也没有还原出原始的图像。按照十进制小数双精度为15位来进行穷举攻击, 对4个参数的攻击难度也将达到1060, 所以用穷举法进行攻击显然是不行的。
4.3 统计分析
该加密方法已经改变了图像各点的像素值, 即加密后图像的灰度直方图也发生了变化, 图4是原始图像的灰度直方图, 图5是加密后图像的灰度直方图。从图中可以看出, 原始图像的像素值在某些点出现的频率很高, 比如像素值为100左右和210左右, 而加密后的直方图呈现正态分布。攻击者通过像素值出现频率的大小来破解显然是困难的, 这样就可以有效抵抗用统计方法进行的攻击。
4.4 时间复杂度分析
本算法中, 生成混沌序列主要是通过迭代, 若问题的规模为m, 则生成混沌序列的时间复杂度为O (m) 。为线性阶的时间复杂度, 而且时间复杂度较低。为检测算法的时间开销, 对不同大小的8位和24位BMP位图进行了大量的加解密实验。实验所采用的硬件系统是Pentium42.8G CPU, 512M DDR内存;软件系统为WindowsXP操作系统, MATLAB编程平台。在实验中, 对数据大小为2.25M的1024×768的24位BMP图像加密所用的时间约为0.38s, 解密所用的时间约为0.42s。该速度可以满足要求, 可见算法的效率较高。
4.5 空间复杂度分析
算法主要空间开销是保存混沌序列所使用的4个1维数组, 每个数组大小等于图像像素数。若待加密图像大小为M×N, 采用int型数组, 则总的大小为M×N×4个int型空间。可见空间开销只与图像大小有关, 与图像位数无关。例如, 对一幅1024×768的图像, 其空间开销约为1024×768×4/ (1024×1024) ≈3M。若问题规模为m, 则算法空间复杂度为O (m) 。
4.6 图像处理攻击分析
若加密图像被攻击者进行恶意破坏, 如加噪、滤波、剪切等图像操作, 测试结果表明:对加密图像轻微剪切并不影响图像解密操作。图6 (a) 是对加密图像剪切掉12.5%的图像, 图6 (b) 是相应解密图像;图6 (c) 是对加密图像剪切掉25%的图像, 图6 (d) 是相应解密图像。可见剪切12.5%对图像的恢复没有太大影响, 即便剪切掉25%, 也可清晰的看到原始图像轮廓。所以, 该方法可抵抗一定程度的剪切攻击。实验显示, 对加噪和滤波等图像处理攻击也有一定抗干扰能力。
5 结论
把混沌理论和密码学相结合是最近几年的事情, 但是已经显示出很强的发展趋势。Logistic映射和Chen映射都是典型的混沌映射, 本文利用混沌映射具有的初值敏感性对原始图像进行了双重加密。通过实验分析发现, 加密之后的图像满足了混淆和扩散, 不仅改变了像素点的位置, 还改变了像素点的值;具有密钥量大、抗初值攻击、抗统计和抗图像处理攻击等优点, 从而增加了系统的安全性。当然还有很多需要改进的地方, 如何选择一个好的混沌映射一直是人们所关心的问题。
参考文献
[1]Kocarev L.“Chaos-based cryptography:a brief overview.”IEEE Circ System Magzine, vol.1, no.3, pp.6-21, 2001.
[2]Chen G R, Mao Y B and Chui C K.“A symmetric image encryption scheme based on 3D chaotic cat maps”.Chaos, Solitons and Fractals, vol.21, pp.749-761, 2004.
[3]Kocarev L, Jakimovski G.“Chaos and cryptography:from chaotic maps to encryption algorithms”.IEEE Trans Circ System-I, vol.48, no.2, pp.163-169, 2001.
[4]Yen J C, Guo J I.“A new chaotic key-based design for image encryption anddecryption.”Proc IEEE Int Conference Circuits and Systems, vol.4, pp.49-52, 2000.
[5]Scharinger J.“Fast encryption of image data using chaotic kolmogorov flows.”Electron Imageing, vol.7, no.2, pp.318-325, 1998.
[6]Zhi-Hong Guan, Fangjun Huang and Wenjie Guan.“Chaos-based image encryption algorithm.”Physics Letters A346, pp.153-157, 2005.
基于组合四面体的模型简化算法 篇8
现代三维技术被广泛应用于多媒体和三维模拟等领域，为了模型处理和存储的方便，许多场合需要对复杂模型进行简化。一直以来，模型简化技术是一个研究热点，国内外研究人员对其进行了大量研究并先后提出了大量的模型简化算法。
Hoppe的基于边折叠渐进网格算法(PM)[1]是比较常用的一种方法，缺点是它的运算量大，对简化速度和时间产生影响。Garland提出了二次误差算法(QEM)[2]，基本思想是计算每次边折叠后的折叠误差，从而提高了简化速度并达到良好的优化效果，但容易造成复杂模型计算的最终累计误差，文献[4]中引入尖特征度的方法来简化模型，虽然能够在视觉特征上有一定的保持，但尖特征度的权值考虑尚未周全。王芳[5]等人基于三角面顶点法向量重要度提出了改进的二次误差测度边折叠算法，保证了顶点边不被折叠，李红波[6]等人在QEM算法基础上，引入顶点法向量与边长作为权值，基于八叉树的模型划分策略，进行了网格简化的算法改进。文献[7]中提出了基于法向矢量的简化算法，基本思想是计算顶点法向矢量与顶点关联三角形法矢量夹角，但忽视了顶点曲率和距离因素而不能最大化程度保持视觉特征效果。闫涛[14]通过顶点的高斯曲率来分类，将三角形网格进行重建与删除以进行优化，但顶点的定位是网格重建的重点。
根据以上问题，本文在模型几何特征以及文献[7]的基础上，采用邻近顶点组合四面体简化思想来完成对模型简化算法的改进，以保证在低三角面片时仍然较好地保持模型的重要视觉特征，最后实验结果证明了该算法的可行性和有效性。
1 经典模型简化方法的比较及选择
在经典模型简化中，主要通过三种方法来生成多层次细节模型，即细分、采样与删减方法。从现在主流方法来看，可以将其宏观地分为几何变换法和几何形体改变法，主要以三角面片作为最小单元来对复杂模型进行剖分，然后从点、线与面的角度对其进行操作，包括移去、改变位置、压缩等，从而有了顶点移去法、边折叠与边压缩法、三角形折叠法等相关算法。
1)顶点删除法删除三角面片的一个共有顶点，然后对空洞多边形重新三角剖分，如图1所示，缺点是需要重新计算新顶点。
2)边折叠法折叠两个三角形的一条公共边为一个顶点，从而消去了一个点，两条边，两个三角形，两个顶点融合成新的顶点，如图2所示。
3)三角形压缩法根据顶点聚类的思想，将符合条件的三角形折叠压缩称为一个新顶点，同时与其相邻的三个三角形被消去，如图3所示，缺点是新顶点仍然需要重新计算。
不难得出，将顶点删除或将三角形折叠后，都将引起空洞，而且重新计算新顶点的代价相对来说比较大，而对于边折叠算法，新顶点的计算代价要减小很多，新顶点可以取两个端点的中点或者是两个端点之一。因此本文采用边折叠法，并且选择被折叠边的两个顶点之一作为新顶点。
2 基于组合四面体的简化算法
模型中视觉特征比较明显的点比较凸显，即在该点的特征度比较大。为了最大化地保留简化模型的视觉特征，本文采用顶点来组合四面体的方法，通过分析其几何特征，将点面距离、法向量夹角以及顶点曲率作为三个权值因子来共同衡量顶点的尖锐程度，而不仅仅局限于文献[7]中判断法矢量夹角大小单因素，这样就确保了顶点特征度能更加精确。为了更好地阐明该算法以及对后续公式能有更清晰的理解，现在引入一些基本概念。
2.1 算法相关的基本概念
定义1如果一个顶点有三条或三条以上的邻边，那么称该顶点为相邻边或相邻顶点的一个公共顶点。
定义2对具有公共顶点的三角形三个作为一组，且与公共顶点相邻的三个顶点不共线，则把由这四个顶点组成的四面体称作组合四面体，可以记为Tcom{v1,v2,v3,v4}，其中vi为顶点。
定义3在复杂模型中，每个顶点都有一个权值，它用来衡量在整体模型中该点视觉重要性与特征是否突出的标识，将该权值在该顶点下的尖锐特征度，记为Kdeg，其中特征度由点面距离、法向量夹角均值和顶点曲率共同决定，后文将对各个参数进行详细介绍。
2.2 算法实现步骤
本文算法步骤大体如下:
1)判断顶点是否为公共顶点，默认公共顶点取第一个相邻边最多的点;
2)判断公共顶点相邻三个顶点是否共线，若共线，分别选最小最大值的两个顶点，再选取另一个与公共顶点相邻的顶点作为第四个顶点，然后组合成四面体;
3)根据四面体相关参数，计算公共顶点的三个权值因子及特征度;
4)比较并筛选出特征度大的点，优先加入非移去顶点序列;
5)对剩余顶点判断，并作相关边折叠处理;
6)重复以上步骤，直至简化完成。
组合四面体如图4所示，点P为具有多个相邻三角形的公共顶点，点A,B,C为点P相邻三角形的不共线的三点，且三点组成一个三角形平面，即ΔABC，向量n→i为P点相邻三角形的法向量，n→为底面的法向量，同时规定每个三角面遵循按逆时针方向右手定则，即所有三角面法向量朝向为外。
从图5可以看到两个不同尖锐特征度的四面体，两个四面体的公共顶点分别是P1,P2，不难看出顶点P2到底面距离值要大于P1的距离，而P2所在的四面体底面法向量与P点相邻三角形各法向量夹角θ(如图4所示)要更小，且P2的顶点曲率大于P1的顶点曲率，即最终P1的特征度要小于P2的特征度，因此本文将这三个参数作为衡量顶点特征度的权值因子。
本文中顶点的特征度权值公式可以表示为:
其中，α、β都是取0到1之间的数值，且有α+β<1，同时不会对简化效果造成影响，以便于灵活控制与调整简化后模型的层次，dv表示顶点到组合四面体Tcom{v1,v2,v3,v4}底面的距离，Qθc表示底面法向量与公共顶点相邻三角面片法向量夹角的均值，Hcuv表示公共顶点的高斯曲率。这三个权值因子共同决定了顶点特征度大小，即在复杂模型中的凸显程度。以下为这几个权值因子的详细计算步骤:
空间任意两点构成的向量可以由如下公式计算:
三角形法向量可以由任意两条三角形边构成的向量叉乘得到，如本文的ΔPAB的法向量为:
从而计算公共顶点到底面的距离公式为:
表征顶点特征度夹角权值Qθc的计算公式如下:
其中，θs为法向量与顶点相邻三角形法向量夹角之和:
当顶点的特征度越大时，顶点视觉特征越明显，底面法向量与顶点相邻三角形法向量的夹角均值越接近于，θs越小，从而权值Qθc越大。
在复杂模型中，高斯曲率表示在顶点处的弯曲程度，平均曲率表示顶点相邻三角面片的弯曲程度。本文中，顶点曲率只需采用高斯曲率作为权值因子即可，这样避免了求平均曲率而带来多余的计算代价，其计算公式可以利用文献[7]的公式:
其中，θp表示顶点夹角，表示顶点相邻三角面的面积均值，并且:
其中，分别用公共顶点相邻的三条棱的向量两两代入计算。至此，三个权值因子计算完成，得到顶点的特征度，即式
(1)。顶点均值可用公式表示，其中，min(Kdeg)表征特征度最小值，max(Kdeg)表征特征度最大值，这里取两者平均值。如果某顶点的Kdeg值较大，且大于顶点均值Gavg，则说明该点的特征度比较大，即视觉特征比较明显，应该对其标记并优先加入不可删除序列中。此外对顶点均值增加一个正负阈值，即:
可以调节模型精简中的平滑过渡性，阈值越大简化效果越粗糙，反之越平滑，以达到简化效果的微调。
2.3 算法流程图
数据存储采用顶点索引、边索引和三角形索引的方式，顶点索引列表包括特征度点索引列表和折叠点索引列表，当某个点符合特征度条件时，将其加入特征度点索引列表并从折叠点索引列表中删除该索引，然后进入下一层循环，直到找到所有表征重要视觉度的顶点为止。最后，对折叠点索引列表中的点进行边折叠操作，即进行一次折叠操作后，取待折叠边的一个顶点作为新顶点，实践证明，折叠后直接取两顶点之一的边折叠操作不仅可以减少每次循环的顶点计算代价，同时也能得到良好的模型简化效果。
算法流程如图6所示。
3 应用实例及结果
本文采用Visual C++6.0编程工具，并结合Open GL API接口将模型动态展现出来，在Windows XP SP3操作系统，AMD3.0 GHz CPU,3.0 GB内存以及ATI Radeon HD(1 GB)显卡的PC机上进行实验。采用的模型是经典的cow和happy budda模型(如图7所示)，为了从视觉保留特征结果作更好的比对，因此笔者将本文的优化算法分别与Melax算法和文献[7]中的算法做了比较。
如图8所示，前三幅是Melax算法简化图，中间三幅为文献[7]算法简化图，后三幅为本文算法简化图，简化比分别都为20%,50%,90%，本次实验中α、β分别取0.45、0.25。可以看出，当简化比不大的时候，三种算法简化结果大体一致，当简化比为50%时，文献[7]算法简化图在耳朵和眼睛处丢失了局部特征，而当简化比较大时，即三角形面片比较少时，此时本文算法能较好地保留局部特征，即保留特征度较大的那些特征点，如图8所示，当简化比为80%时，牛的角、耳朵、眼睛与鼻子部分仍然能凸显出来，文献[7]算法简化图中，牛的一只角丢失了许多特征，而采用Melax算法则相对丢失多一些特征，只保留了耳朵和一只角部分。又如图9所示，左、中、右分别为Melax算法，文献[7]算法和本文算法简化图，不难看出buddha在三种算法下大部分都保持了视觉特征，而本文算法在如鼻子、肚子以及手臂等细节特征保持完好，而前两者简化图丢失了部分特征并且部分区域产生了形变。因此，本实验结果证明了本文算法在低面片数时仍有较好的简化效果。
从表1中可看出，开始时，本文算法简化模型时间要长些，而当精简百分比增加时，即当模型三角名片为数不多时，从而后期速度总体上要略快于Melax算法和文献[7]算法，由于本文算法计算代价略高，而后期顶点保留不需重新计算，从而在一定程度上缩短了模型后期简化的时间，进一步证明本文算法是切实可行的。
4 结语
本文从顶点组合四面体角度出发，针对研究顶点的尖锐特征度并结合边折叠优化来实现模型精简算法的优化，该算法利用几何模型中的点面距离、向量夹角以及顶点曲率等参数来计算每个顶点的特征度，并且根据三个参数进行微调来控制简化过程中的效果。通过与Melax算法进行比较，实验证明，本文算法在提升模型简化速度上有一定的优势，能最大化保持模型的局部视觉特征，证明了它是切实可行的一种模型精简算法。
组合算法 篇9
1 三维表格管理基本形式
如果我们处理如图1所示三维表格管理的问题:
该图中表示的数据一共有三类,分别是代课教师姓名、课程名称、时间。如果李老师的C语言课程在星期一,则在相应位置表示为1,如果不存在则表示为0。
如果表示为相应的数学模型,则表示为三维数组A姓名,课程,星期,也可以表示为a3,3,3上图可如下所示:
若表示为相应的计算机模型,则很难表示,如果用关系数据库来表示,也存在很大的问题。我们采用全组合编码公式进行相应的编码、解码、查询,能够解决多维表格管理中存在的问题,对于存储优化、查询、信息隐蔽形成一套完整的方法。
2 维表格管理算法应用
2.1 选取最小权值
对于三维数组a3,3,3,根据(公式3):
R1最小可以为2=21∈{2i|i>=1}。
当R1=2时,R2>=R13,R2最小可以为8=23∈{2i|i>=1}。
当R2=8时,R3>=R24,R3最小可以为4096=212∈{2i|i>=1}。
2.2 权值计算
进行计算各项权值:
其他元素为0,其权重也为0。
2.3 编码
根据(公式2)最终编码Code:
进行编码合成
根据全组合编码公式最终得到Code为8003047645,在数据管理中,我们只需要存储Code这样一个数据就可以完成图1所示的数据存储。
3 数据的管理与应用
3.1 数据增加
根据示例a2,1,1=0表示王老师的C语言在星期一没有课,如果数据变更为有课则a2,1,1=1。根据(公式4)Code=Code+Array'k1k2……km
‘数据由a2,1,1=0改变为a2,1,1=1只需要给Code增加a2,1,1的值。
3.2 数据减少
根据示例a2,3,1=1表示王老师的数据库在星期一有课,如果数据变更为没有课则a2,3,1=0。
根据(公式5)
数据由a2,3,1=1改变为a2,3,1=0只需要给Code减去a2‘,3,1的值。
3.3 数据查询
如果我们要查询张老师的C语言在星期二有没有课,也就是a3,1,2是不是等于1,则根据(公式6)
对于任意元素Arrayk1k2……km的存在判断依据:
用以下程序进行判断:
如果要判断a3,1,2是否为真,应用(公式6):
证明张老师的C语言在星期二有课。程序查询结果如图2所示。
如果我们要查询王老师的数据库在星期二有没有课,也就是a2,3,2是不是等于1,则根据(公式6)
如果要判断a2,3,2是否为真,应用(公式6):
证明王老师的数据库在星期二没有课。程序查询结果如图3所示:
4 结束语
多维表格在计算机中的数据模型很难表示,在存储中也存在很多问题,采用全组合编码公式可以对多维表格管理的数据进行编码、存储、维护、查询等操作。存储结构简单,只需要使用一个数据就能够存储整个表格,在数据安全性上达到了数据隐蔽的效果,该文根据三维表格实例进行了分析,并形成一套完整的处理方法,解决了多维表格在计算机中的管理问题。
参考文献
[1]刘正岐郭涛.基于逻辑运算的多维数据全组合编码算法研究[J].物联网技术,2011(9).
[2]明亮,王宇平.n进制编码遗传算法的收敛速度[J].系统工程理论与实践,2006(03).
[3]Zisman M D.数据存储技术的走向[J].现代制造,2002(14).
[4]唐伟,施永香,文巨峰.基于.NET的通用查询组件的开发[J].计算机工程与设计,2006(14).
[5]杨立平.信息检索中逻辑运算算法的改进——双向双对分算法[J].山西大学学报:自然科学版,2007(04).
[6]白春清.面向对象的非线性加权逻辑运算辨证模型[J].中国中医药信息杂志,2003(08).
[7]刘宏岚,高庆狮,杨炳儒.多值逻辑中的命题相关性与逻辑运算研究[J].北京科技大学学报,2007(S2).
[8]冯小峰.K进制广义吉祥数的计数定理及其推论[C]//中国当代教育理论文献——第四届中国教育家大会成果汇编(上),2007.
[9]孙红艳,张鹏.改进的遗传算法在聚类分析中的应用[J].电脑知识与技术,2011(36).
[10]薛蕾,李林,李翔.多维数据索引方法研究综述[C]//第一届国际计算机及计算技术在农业中的应用研讨会”暨“第一届中国农村信息化发展论坛”论文集,2007.