常用算法范文

2024-06-29

常用算法范文（精选10篇）

常用算法第1篇

1 DES

DES算法是由IBM公司研制的, 并于1977年定为美国联邦信息加密标准。它是一种分组密码, 以64位为分组对数据加密, 它的密钥长度是56位 (每个第8位作为奇偶校验) , 加密解密用同一算法。

DES算法是对密钥进行保密, 而公开算法, 包括加密和解密算法。这样, 只有掌握了和发送方相同密钥的人才能解读由DES算法加密的密文数据。因此, 破译DES算法实际上就是搜索密钥的编码。对于56位长度的密钥来说, 如果用穷举法来进行搜索的话, 其运算次数为256。

随着计算机系统能力的不断发展, DES的安全性比它刚出现时会弱得多, 然而从非关键性质的实际出发, 仍可以认为它是足够的。不过, DES现在仅用于旧系统的鉴定, 而更多地选择新的加密标准—高级加密标准 (Advanced Encryption Standard, AES) 。

2 AES

密码学中的高级加密标准 (Advanced Encryption Standard, AES) , 又称Rijndae l加密法, 为比利时密码学家Joan Dae me n和Vince nt Rijme n所设计, 结合两位作者的名字, 以Rijndae l命名。该算法采用对称分组密码体制, 密钥长度的最少支持为128、192、256, 分组长度128位, 算法应易于各种硬件和软件实现。这种算法是美国联邦政府采用的区块加密标准, 这个标准用来替代原先的DES, 已经被多方分析且广为全世界所使用。

AES算法被设计为支持128/192/256位 (/32=Nb) 数据块大小 (即分组长度) ;支持128/192/256位 (/32=Nk) 密钥长度, 在10进制里, 对应3.4×1038、6.2×1057、1.1×1077个密钥。

3 RSA

RSA是目前最有影响力的公钥加密算法, 并且被普遍认为是目前最优秀的公钥方案之一。RSA是第一个能同时用于加密和数字签名的算法, 它能够抵抗到目前为止已知的所有密码攻击, 已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易, 但那时想要对其乘积进行因式分解却极其困难, 因此可以将乘积公开作为加密密钥。

4 BASE64

Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一, Base64编码可用于在HTTP环境下传递较长的标识信息。例如, 在Java Persistence系统Hibernate中, 采用了Base64来将一个较长的唯一标识符 (一般为128-bit的UUID) 编码为一个字符串, 用作HTTP表单和HTTP GETURL中的参数。在其他应用程序中, 也常常需要把二进制数据编码为适合放在URL (包括隐藏表单域) 中的形式。此时, 采用Base64编码不仅比较简短, 同时也具有不可读性, 即所编码的数据不会被人用肉眼所直接看到。

这个编码的规则:1) 把3个字符变成4个字符;2) 每76个字符加一个换行符;3) 最后的结束符也要处理。

5 MD5

Me s s age Dige s t Algorithm MD5为计算机安全领域广泛使用的一种散列函数, 用以提供消息的完整性保护。

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息, 且每一分组又被划分为16个32位子分组, 经过了一系列的处理后, 算法的输出由四个32位分组组成, 将这四个32位分组级联后将生成一个128位散列值。

MD5被广泛用于各种软件的密码认证和钥匙识别上。MD5用的是哈希函数, 它的典型应用是对一段信息 (Message) 产生信息摘要 (Message-Digest) , 以防止被篡改。MD5的典型应用是对一段Me s s age (字节串) 产生finge rprint (指纹) , 以防止被“篡改”。如果再有一个第三方的认证机构, 用MD5还可以防止文件作者的“抵赖”, 这就是所谓的数字签名应用。MD5还广泛用于操作系统的登陆认证上, 如Unix、各类BSD系统登录密码、数字签名等诸多方。

6 SHA1

SHA1 (Se cure Has h Algorithm) 是和MD5一样流行的消息摘要算法。1995年, 联邦信息处理标准 (FIPS) 发布了180-1, 作为安全散列标准。180-1出版的算法被定义为安全散列算法1 (SHA1) 。国家标准技术研究所 (NIST) 和国家安全局 (NSA) 开发了SHA1算法。SHA1算法模仿MD4算法。现在有一个更新SHA1算法的FIPS180-2草案。SHA1设计为和数字签名算法 (DSA) 一起使用。

SHA1主要适用于数字签名标准 (Digital Signature Standard DSS) 里面定义的数字签名算法 (Digital Signature Algorithm DSA) 。对于长度小于2^64位的消息, SHA1会产生一个160位的消息摘要。当接收到消息的时候, 这个消息摘要可以用来验证数据的完整性。在传输的过程中, 数据很可能会发生变化, 那么这时候就会产生不同的消息摘要。SHA1不可以从消息摘要中复原信息, 而两个不同的消息不会产生同样的消息摘要。这样, SHA1就可以验证数据的完整性, 所以说SHA1是为了保证文件完整性的技术。

SHA1算法可以采用不超过264位的数据输入, 并产生一个160位的摘要。输入被划分为512位的块, 并单独处理。160位缓冲器用来保存散列函数的中间和最后结果。缓冲器可以由5个32位寄存器 (A、B、C、D和E) 来表示。

SHA1是一种比md5的安全性强的算法, 理论上, 凡是采取“消息摘要”方式的数字验证算法都是有“碰撞”的——也就是两个不同的东西算出的消息摘要相同, 互通作弊图就是如此。但是安全性高的算法要找到指定数据的“碰撞”很困难, 而利用公式来计算“碰撞”就更困难——目前为止通用安全算法中仅有md5被破解。

密码算法是密码技术的核心, 以上这些密码算法是常用的密码算法, 而这些算法有些已经遭到破译, 有些安全度不高, 有些强度不明, 有些待进一步分析, 有些需要深入研究, 而神秘的密码算法世界, 又会有新的成员加入, 期待更安全的算法诞生。

参考文献

[1]电子商务中常用的RSA算法实现.花蓓.商场现代化, 2008.

VB常用算法总结第2篇

一、变量值的交换

算法思想：若交换两个变量的值，必须引入第三个新的变量进行传递。以下代码是错误的：

X=12 ：Y=34 ：X=Y ：Y=X 正确的代码是：

X=12 ：Y=23 ：T=X ：X=Y ：Y=T

二、判断一个数是否能被另一个数整除

算法思想：可以用整除的定义（余数为0）或X除以Y等于X整除Y等表达式进行判断。条件表达式可以为：X mod Y=0

或

X＼ Y=X/Y

或

Int(X/Y)=X/Y 如果以上条件表达式为True，则表示X能被Y整除。

三、累加、阶乘、计数和求平均值

算法思想：使用循环语句，并用一个变量存放累加的中间及最终结果。注：累加求和时变量初值为0，计算阶乘时变量初值为1。

统计计个数（计数）时可用一个变量作为统计个数的累加变量，每次加1即可。求平均值算法思想是先求和，再除以个数。条件求和（或计数）：在循环语句中加入If－End If判断语句。

例题：计算1到10之间所有整数的累加和以及10！。n=10 sum=0

‘累加求和时，变量的初值一定为0 prod=1

‘累乘（连乘）时，变量的初值一定为1 For i=1 To n

sum=sum+i

prod=prod*i Next i Print sum,prod

例题：统计0—100之间能被3整除的数的个数、累加和及其平均值。

s=0

n=0

For i=0 To 100

If i mod 3 =0 Then

s=s+i

n=n+1

End If

Next i

Print n,s,s/n

四、随机数的产生 [a,b]之间的随机整数 Int((b-a+1)*rnd)+a(a,b)随机数（b-a）*rnd +a

五、求若干个数中最大值或最小值

六、常用字符处理函数

Mid函数：从字符串指定位置取指定个字符，格式为Mid(字符,p,n)，从第p个字符开始，向后截取n个字符（若n省略则取到最后）。

Left和Right函数：从字符串左边或右边取指定个字符，格式为 Left(字符,n)和Right(字符,n)。Len函数：测试字符串长度。

UCase和LCase函数：UCase将小写字母转换为大写字母；LCase将大写字母转换为小写字母。

Instr([首字符位置 , ] 字符串1, 字符串2 [ , n])：在字符串1中查找字符串2，如果找到，返回字符串2的第一个字符在字符串1中出现的位置。首字符位置是可选的，如果不指定，从字符串起始位置开始查找；如果指明，从指定的位置开始查找。

Asc函数：返回字符串中第一个字符的ASCII码。Chr函数：将一个数值转换为其所对应的字符。

字符的比较规则是按ASCII码顺序比较，规则为空格<”A”～”Z”<”a”～”z” 小写字母的ASCII比大写字母的ASCII小32。

例题：

1．将所有文本转换为大写（小写）字母

可以直接使用UCase（LCase）函数转换。例如： Text2.Text=UCase(Text1.Text)2．对某个字符串的所有字符逐一处理

算法思想：如果对某个字符串的所有字符逐一处理，即从字符串的第1个字符开始到最后一个字母，每次处理1个字符。可以使用For循环实现。通用代码为：

For i=1 To Len(s)

s1=Mid(s,i,1)……

Next i 3．字符转换

算法思想：通过字符的ASCII码进行处理（使用Asc函数），然后再使用Chr函数将ASCII转换成字符。例题：将文本框Text1中字符按如下规律转换a－b、b－c……z－a，并显示在文本框Text2中。

s = Text1.Text n = Len(s)For i = 1 To n

s1 = Mid(s, i, 1)

If s1 >= “a” And s1 <= “y” Then

s2 = s2 + Chr(Asc(s1)+ 1)

ElseIf s1 = “z” Then

s2 = s2 + “a”

End If Next i Text2.Text = s2 例题：将文本框Text1中的小写字母转换其对应的大写字母，将大写字母转换成小写字母，并显示在文本框Text2中。

Private Sub Command1_Click()s = Text1.Text n = Len(s)m = Asc(“a”)m)

End If

If s1 >= “A” And s1 <= “Z” Then

s2 = s2 + Chr(Asc(s1)+ m)

End If Next i Text2.Text = s2 End Sub 5．统计某字符出现次数

算法思想：对字符串中字符逐一判断，如果是某字符，则统计变量加1。

例题：统计文本框Text1中字符i和j出现的次数（不区分大小写）。

Private Sub Command1_Click()

s = Text1.Text

n = Len(s)

For i = 1 To n

s1 = Mid(s, i, 1)

If UCase(s1)= “I” Then ni = ni + 1

If UCase(s1)= “J” Then nj = nj + 1

Next i

Print ni, nj

End Sub

八、素数

素数定义：只能被1和本身整除的正整数称为素数（或称质数）。例如11就是素数，它只能被1和11整除。算法思想：判别某数n是否是素数的方法有很多，最简单的是从素数的定义来求解。对于n，从i=2，3，…，n-1判别n能够被i整除，只要有一个能整除，n就不是素数，否则n是素数。此种算法比较简单，但速度慢，因此，可以将n被2到（或n/2）间的所有整数除，如果都除不尽，则n就是素数，否则n是非素数。

注：执行For循环时，循环变量等于终值仍进入循环，遇到Next语句，循环变量会自动加上步长，因此如果循环正常完成后，循环变量的值将大于终值。例如：

For i=1 To 4 If …… Then Exit For Next i Print i 如果循环正常结束，则输出结果为5（大于4）。如果循环过程中满足If条件，执行Exit For语句退出循环，则i的值一定小于5。

例题：判断n是否是素数。Private Sub Command2_Click()n = Val(Text1.Text)For j = 2 To n100 * a)/ 10)c = i-Int(i / 10)* 10 If i = a ^ 3 + b ^ 3 + c ^ 3 Then Print i End If Next i End Sub

Private Sub Command1_Click()For n = 100 To 999 s = 0 a = n Do While a <> 0 b = a Mod 10 s = s + b * b * b a = a＼ 10 Loop If s = n Then Print n Next n End Sub

十一、斐波那切数列的输出

该数列前两项为1，1从第三项开始，an=an-1+an-2

十二、进制转换十三、三个数排序

十四、分段函数

十五、图形输出（双重循环）

十六、百鸡百钱问题

十七、迭代法P116页

十八、输入a,b,c,的值，求方程ax2+bx+c=0的解。

注意：对象只考文本框、标签、命令按钮和窗体。

本学期计算机基础及VB程序设计复习指导如下：

1、计算机基础的50道复习题，试卷上占20分，选择15题，填空5题。

2、VB习题集第一到五章控制结构的课后习题及试题解析（其中，控件只考窗体、文本框、标签、命令按钮）试卷上占40分。

细说初中《有理数》的几种常用算法第3篇

常用算法

【中图分类号】G 【文献标识码】A

【文章编号】0450-9889（2014）08A-

0086-01

数学作为各个学科中极具挑战性的一门课程，其教学方式关系着最终的教学效果。在教学过程中，有理数的运算是初中数学学习的一个重点，也是难点，更是学生学好初中数学的一个关键点。灵活巧妙地运用有理数运算方法，可以大幅度提高学生的运算速度以及准确度，更有助于学生思维能力的锻炼。下面，笔者根据多年的教学经验，对初中数学中有理数运算的几种常见算法进行详细的介绍和简单的分析。

一、倒序相加法

倒序相加法应用于有一定规律的数字求和中，具体表现在前后数字的差值一定，首尾以及距离首尾等距离的数字之和一定，这样的有理数题型就能够使用倒序相加法进行解答。例如，计算5+10+15+20+……+1990+1995的和。首先，我们可以明显地看出题目中的数字的规律性。其次，在进行题目分析时，我们不难发现，5+1995=2000，10+1990=2000……以此类推，首尾项以及距离首尾项等距的数字和都是2000。因此，本题型适用于倒序相加法。具体的解题步骤如下：首先设s1=5+10+15+……+1990+1995，其次将上式采用倒序的方法写下来，设为s2=1995+1990+……+15+10+5。这样便可以简单地将s1与s2的和算出，得出原题目的答案就是s1与s2总和的一半。从中我们不难发现，如果相邻的项之间存在固定的差值关系，那么就可以运用倒序相加法来解决。

二、错位相减

为了方便多个有理数求和，还有一种看似增加了加数，实质上却简便了算式的错位相减法。错位相减法也是解决有理数算式的重要方法。利用错位相减法解答的有理数题型也有着明显的特征。例如，计算3+6+12+24+……768+1536的和是多少。在这个题型中，我们可以很轻易地发现其中的数字排布规律，即从第一项以后，每一项都是前一项的2倍，这就是本题的突破口。试想，如果将这道题目中的每一个数字乘以2，那么得到的新的式子只有最后一项和原式第一项不同，我们就可以利用这一个特点来进行有理数的简便运算。具体的解法如下：令s=3+6+12+24+……768+1536，那么2s=6+12+24+……768+1536+3072，可以利用他们之间的相同项进行消除运算，即2s-s=-3+3072=3069，解得s=3069。从中我们可以看出，如果项与项之间存在固定的倍数关系，就可以运用错位相减法进行解决。

三、拆项法

在进行有理数运算时用对了方法，就会有一种“山重水复疑无路，柳暗花明又一村”的感觉。拆项法就是这样一种神奇的方法。它经过简化可以将相同项进行消除，让看似复杂繁琐的计算变得简洁清晰。拆项法，顾名思义，就是将题目中的项进行拆分，从而达到消除相同项的目的。因此，拆项法又叫做裂项相消法。例如，=1-、=-，利用这种性质，我们可以解决相类似的一系列有理数计算问题。例如，计算1++++……+的和是多少。这个题目就完全满足拆项法的解答条件。原式根据上述方法进行拆项后可以转化为1+1-+-+……-=1+1-=。这样，相同的项就被轻而易举的消除，原来复杂的项被拆分、简化，为有理数的计算提供了解答的可能。

四、换元法

换元法就是通过引入一个或几个新的变量来替换原来的某些变量的解题方法。利用换元法进行解题，能够简化分式，简便运算。例如，计算题：（++++……+）（1+++++……+-（1+++++……+）（++++……+）.通过观察可以发现，在这个复杂的分式混合运算中有着共同的一部分就是++++……+，为了方便计算，我们可以将这个共同的部分用M代替，那么原式就变成了（M+）（1+M）-（1+M+）M.再进行拆分，就能够让原式变成（M+M·M++）-（M+M·M+）.再进行运算就相当简单了，得出最终结果。

总之，有理数相关题型千变万化，但是万变不离其宗，学生在初中时期能够熟练地掌握有理数的解题技巧，就一定能够提高解题的速度和质量，提高教学效率。

高职常用优化算法比较分析第4篇

高职学生对优化算法的接触普遍较少, 但是在实际问题的解决中, 一些较简单的优化算法不仅能较好地解决复杂问题, 而且可以提高问题的解决效率。笔者拟介绍几种常用的比较简单的优化算法, 并对其性能进行比较分析。

几种优化算法的基本思想

对于多元函数而言, 最优值一般都会取在梯度为零的点附近。因此, 传统的优化算法就是利用梯度信息来求函数的最优值, 常用的方法有最速下降法、牛顿法等。随着实际问题规模的扩大、复杂程度的增加, 很多问题的梯度比较难计算, 随之产生了启迪算法, 如遗传算法、粒子群算法、禁忌搜索算法、模拟退火算法等。

(一) 最速下降算法

最速下降算法是求解无约束优化问题最简单的方法。利用函数的梯度信息, 在其可行域内搜索可行点, 使得该点处的梯度接近零, 从而得到函数的最优值。该算法的思想是:以负梯度为方向 (dk=-塄f (xk) ) 作为搜索方向, 按照迭代:xk+1=xk+αkdk寻找最优解。其中αk为搜索步长。

该算法的计算步骤如下: (1) 取初始点x0∈Rn, 精度ε>0, 令k:=0; (2) 计算, 若, 则停, x*=xk, 则转; (3) 线性搜索:, 令xk+1=xk+αkdk, k:=k+1, 转 (2) 。

(二) 阻尼牛顿法

阻尼牛顿法是以二次近似来逼近函数的牛顿法, 在该算法中, 取下降方向为, 即, 当αk=1时, 该算法称为牛顿法。

该算法的计算步骤如下: (1) 取初始点x0∈Rn, ε>0, 令k:=0; (2) 计算, 若, 则停:x*=xk, 否则, 转; (3) 计算; (4) 线性搜索:, 令xk+1=xk+αkdk, k:=k+1, 转 (2) 。

(三) 粒子群算法

粒子群算法是一种随机搜索的启迪式算法。它将每一个可行解看做空间中的一个粒子, 每个粒子代表空间中的一个候选解, 解的优劣程度可根据目标函数计算其适应度来判断。在D维空间中, 种群由m个粒子组成, 其中第i个粒子位置表示为xi= (xi1, xi2, …, xi D) , 它的速度为vi= (vi1, vi2, …, vi D) , 该粒子搜索到的当前个体最优值表示为:pi= (pi1, pi2, …, pi D) , 整个粒子当前的最优值表示为:pg= (pg1, pg2, …, pg D) 。在每一次迭代中, 粒子根据个体最优值和整个粒子群的最优值调整速度, 由速度来调节粒子的位置, 更新候选解。标准粒子群算法迭代公式为:

其中, i=1, 2, …, m;d=1, 2, …, D;r1和r2都是服从U (0, 1) 分布的随机数;c1, c2为非负常数, 通常取值为:c1=c2=2;vid∈[-vmax, vmax], vmax是由用户根据实际问题设定的常数, 粒子在每一维飞行的速度不能超过算法设定的最大速度vmax。

标准粒子群优化算法的计算步骤如下: (1) 在可行域内, 对粒子群进行随机初始化, 包括随机初始位置和速度。 (2) 计算每个粒子的适应度值。 (3) 对于每个粒子, 将其适应度值与所经历过最好位置的适应度值进行比较, 如果更好, 则将其作为粒子的个体历史最优值, 用当前位置更新个体历史最好位置。 (4) 对每个粒子, 将其历史最优适应度值与群体内或邻域内所经历的最好位置的适应度值进行比较, 若更好, 则将其作为当前的全局最好位置。 (5) 根据式子 (1) 、 (2) 对粒子的速度和位置进行更新。 (6) 若达到终止条件, 则停, 否则, 转 (2) 。一般将终止条件设定为一个足够好的适应值或达到一个预设的最大迭代次数。

(四) 禁忌搜索算法

禁忌搜索算法是一种亚启发式搜索算法, 所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足, 禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点, 在下一次的搜索中, 利用禁忌表中的信息不再或有选择地搜索这些点, 以此来跳出局部最优点。就好比人的短时记忆, 走过的路不再重复或有选择地重复;同时“遗忘”又使得这些禁止是弱禁止, 即在一定的时间之后这些禁止将失效, 最终达到全局优化之目的。

禁忌搜索算法的计算步骤如下: (1) 给定初始解x0, 分配禁忌表长度L, 设定初始解为当前的最优解xbest; (2) 在初始解邻域内产生n个测试解 (n>L) , 将测试解依次与禁忌表中的解比较, 若测试解不在禁忌表中, 计算其目标函数值, 并求出这些解中的最优解, 记为当前较优解xc;并将xc存入禁忌表, 若禁忌表满, 则按先进先出的原则更新禁忌表; (3) 若f (xc)

几种算法的比较分析

(一) 最速下降算法

该算法是1847年由著名数学家柯西 (Cauchy) 给出的。它是解析法中最古老的一种, 其他解析方法或是它的变形, 或是受它的启发而得到的。它的优点在于操作简单, 所需存储空间少, 对初始点要求较低, 在最初阶段的搜索速度快, 可以很快到达函数极值附近。但在搜索的最后阶段, 由于步长的影响, 算法的搜索路线常呈现“锯齿状”, 使得算法不能很快达到最优值, 而且由于该算法是按照负梯度的方向不断搜索的, 当达到函数的某一极值点后, 算法很难跳出极值点, 从而会使得找到的点只是某个极值点, 并不是函数的整体最优点, 即算法容易陷入局部最优。该算法是以一次近似来逼近函数的, 因此得到的最优解精度不高。因此该算法常用于比较简单的、连续的、单极值目标函数, 这一类函数用该算法通常会在很短的迭代次数后产生最优点。或者可以在搜索的初始阶段使用该算法, 并在后期结合另一种算法计算。

(二) 阻尼牛顿法

该算法是牛顿法的改进。它以函数的二次逼近为基础, 因此较之最速下降算法, 其搜索精度较高。而且对于严格凸函数, 该算法可以搜索到其全局最优解, 且有较快的收敛速度。但是该算法对目标函数要求较高, 一般需要具有一阶、二阶偏导数, 同时其海森阵必须正定且非奇异, 在每次迭代中, 计算量较大, 对于较复杂的目标函数而言, 搜索速度会受到严重影响。因而, 此算法适用于一些精度要求较高, 目标函数的梯度较简单的问题, 是传统优化算法中性能较好的一种。

(三) 粒子群算法

该算法是由肯尼迪 (Kennedy) 和埃伯哈特 (Eberhart) 于1995年提出的。它操作简单, 不需要目标函数的梯度信息, 甚至不要求目标函数的连续性, 对于复杂函数有很好的优化能力, 有较快的收敛速度, 且该算法所需参数少, 易于实现, 是最常用的优化算法之一。通过给定不同的参数值, 可以灵活修正算法的搜索速度和收敛精度, 且其搜索机制简单, 可以很容易地进行算法改进或者与其他算法结合解决大型复杂问题。目前, 该算法已广泛应用于函数优化、神经网络训练、模式分类、模糊系统控制, 在其他应用领域也受到广泛欢迎。但是基本粒子群算法的稳定性和全局搜索能力较差, 很多学者从不同方面对基本粒子群算法进行了改进, 如马翠、周先东等人的分层粒子群优化算法, 将搜索分为局部和全局同时并行进行;褚国娟、马春丽等人的基于差分及模拟退火的混合粒子群算法, 将模拟退火算法与粒子群算法结合, 可以更好地提高算法的全局搜索能力。另外, 粒子群算法的理论证明较少, 参数对算法性能的影响、算法对不同问题解决能力的差异等问题都是通过实验检验的, 理论的证明几乎没有, 这也是该算法未来研究的方向之一。

(四) 禁忌搜索算法

禁忌搜索算法最早由美国工程院院士, 科罗拉多大学教授福瑞德·格洛弗 (Fred Glover) 提出, 它是一种亚启发式算法, 它在搜索过程中避免重复工作, 禁忌当前较优解, 可以很好地跳出局部最优, 提高算法的搜索精度。同时, 该算法所需参数少, 操作简单, 适合求解较复杂的多极值函数最优值。禁忌搜索算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功, 近年来又在函数全局优化方面得到较多的研究。但是, 该算法对初始解的依赖性较强, 初始解的选取会影响到算法的搜索速度甚至精度。同时, 该算法更新机制不是很完善, 理论证明方面也很欠缺, 因而单独使用时灵活度较差, 成功率也较低, 通常可以将该算法与其他算法 (如粒子群算法) 结合, 在每次迭代的后期使用禁忌搜索算法, 既可保证算法的灵活度, 提高其搜索速度, 又可提高算法的收敛精度。

综上所述, 前两种是传统优化算法, 利用梯度信息进行求解, 操作简单, 经理论证明, 对于连续函数有较好的收敛性, 但对于梯度信息较复杂甚至无法求梯度的目标函数而言, 这两种算法较难实现。后两种算法属于随机搜索的启迪式智能算法, 通常是模拟自然界中动物的习性进行优化搜索, 算法操作简单, 不需要梯度信息, 易于实现, 较易与其他算法结合, 且有很强的解决大型复杂问题的能力, 是目前工程、通信等领域广泛使用的智能优化算法。但是现代的很多智能优化算法理论研究方面较薄弱, 没有办法严格说明其收敛速度和精度的依赖因素, 只能通过大量实验进行验证, 这也极大地限制了算法的发展。

参考文献

[1]陈开周.最优化计算方法[M].西安:西安交通大学出版社, 2003:53-55.

[2]徐成贤, 陈志平, 李乃成.近代优化方法[M].北京:科学出版社, 2002:85-88.

[3]Kennedy J, Eberhart R C.Particle swarm optimization[J].Proceedings of IEEE international Conference on Neural Networks, 1995:1942-1948.

[4]陈冬芳, 薛继伟, 张漫.全局最优化算法及其应用[J].大庆石油学院学报, 2005 (1) :23-25.

[5]马翠, 周先东, 杨大地.分层粒子群优化算法[J].计算机工程, 2009 (20) :194-196.

[6]褚国娟, 马春丽, 宁必锋.基于差分及模拟退火的混合粒子群算法[J].计算机与现代化, 2010 (5) :19-20.

[7]刘嘉敏, 董宗然, 马广焜.基于禁忌搜索算法求解集装箱装载问题[J].沈阳工业大学学报, 2009 (2) :212-216.

常用算法第5篇

本文首先综述了实现运动检测的几种传统常用算法.最后对这种技术在高速公路上的`运用作了一个简略的介绍.

作者：侯丹红钟雄作者单位：侯丹红(广州医学院从化学院计算机教研室,510900)

钟雄(广东机电职业技术学院工商外语系,510515)

图像信息隐藏技术常用算法浅析第6篇

信息隐藏技术是一门具有渊源历史背景的新兴学科, 涉及感知科学、信息论、密码学等多个学科, 涵盖信号处理、扩频通信等多个专业技术的研究方向。随着近几年来以Internet为代表的全球信息化迅速发展, 信息安全的要求也变得多样化。由此引起了信息隐藏技术的迅速发展。

密码技术是解决信息安全问题的一种有效手段, 它通过特殊的编码将要传送的秘密信息转变为随机的乱码, 以对通信双方之外的第三方隐藏其通信内容。但信息加密是利用随机性来对抗密码攻击的, 密文的随机性同时也暴露了消息的重要性, 即使密码的强度足以使攻击者无法破解出明文, 但他仍有足够的手段来对其进行破坏, 使得合法的接收者也无法阅读信息内容;此外, 加密算法不能保证授权用户的非法再分发传播等不良行为。随着软硬件技术的发展, 加密算法的安全性受到了严重挑战。

由于加密技术的局限性, 信息隐藏技术引起了人们的研究兴趣。信息隐藏技术是利用载体信息的冗余性, 将秘密信息隐藏于普通信息之中, 通过普通信息的发布而将秘密信息发布出去, 即将重要的信息隐藏于其他信息里面从而掩饰它的存在。它隐藏的是信息的“存在性”, 使它们看起来与一般非机密资料没有区别, 可以避免引起其他人注意, 从而具有更大的隐蔽性和安全性, 十分容易逃过拦截者的破解。为了提高信息的安全性, 还可以把加密技术和隐藏技术结合起来, 即首先对信息加密形成密文, 然后再把密文隐藏起来。

二、信息隐藏技术的特点

信息隐藏不同于传统的加密, 因为其目的不在于限制正常的资料存取, 而在于保证隐藏数据不被侵犯和发现。因此, 信息隐藏技术必须考虑正常的信息操作所造成的威胁, 即要使机密资料对正常的数据操作技术具有免疫能力。这种免疫力的关键是要使隐藏信息部分不易被正常的数据操作 (如通常的信号变换操作或数据压缩) 所破坏。根据信息隐藏的目的和技术要求, 该技术存在以下特性:

鲁棒性 (Robustness) :指不因图像文件的某种改动而导致隐藏信息丢失的能力。这里所谓“改动”包括传输过程中的信道噪音、滤波操作、重采样、有损编码压缩、D/A或A/D转换等。

不可检测性 (Undetectability) :指隐蔽载体与原始载体具有一致的特性。如具有一致的统计噪声分布等, 以便使非法拦截者无法判断是否有隐蔽信息。

透明性 (Invisibility) :利用人类视觉系统或人类听觉系统属性, 经过一系列隐藏处理, 使目标数据没有明显的降质现象, 而隐藏的数据却无法人为地看见或听见。

安全性 (Security) :指隐藏算法有较强的抗攻击能力, 即它必须能够承受一定程度的人为攻击, 而使隐藏信息不会被破坏。

自恢复性 (Self-Recoverability) :由于经过一些操作或变换后, 可能会使原图产生较大的破坏, 如果只从留下的片段数据, 仍能恢复隐藏信号, 而且恢复过程不需要宿主信号, 这就是所谓的自恢复。

基于多媒体载体的信息隐藏技术, 目前研究最深入、成果最丰富的是图像信息的隐藏技术。其典型算法主要有:空间域隐藏算法、变换域隐藏算法。

三、图像信息隐藏的典型算法

(一) 空间域算法

空间域算法就是直接改变图象元素的值, 一般是在图象元素的亮度或色带中加入隐藏的内容。常见的具体算法有:

1. 最低有效位算法LSB。

计算机用三个字节来表示颜色的红、绿、蓝三原色的分量数值, 每个字节的最低位的变化对颜色的视觉影响很小而无法察觉, 因此可以把红、绿、蓝三原色的分量数值的最低位 (最小意义位) 视为冗余空间, 把信息隐藏在这里。LSB算法通过调整宿主数据的最低1、2位有效位来隐藏信息, 致使所隐藏的信息在视觉和听觉上很难被发现。这种方法有较大的信息隐藏量。但从基本原理上看, 该算法所隐藏的信息是极为脆弱的, 因为它无法承受某些无意有意信号处理。

2.Patchwork算法。这种方法是任选N对图像点, 在增加其一点亮度的同时, 将相应的另一点的亮度降低, 以在这一调整过程中隐藏1bit的信息于宿主媒体之中, 该算法具有较高的不易察觉性, 并对有损压缩编码 (JEPG) , 和一些带有恶意攻击的处理有抵抗能力。

空域类算法的特点是只需对隐秘载体进行很小的、不易察觉的改变就能隐藏很大的信息量, 计算速度较快。但从基本原理上看, 该算法所隐藏的信息是极为脆弱的, 若载体图像有微小的改变, 隐藏信息就可能丢失。

(二) 变换域算法

变换域算法也叫频域算法, 就是利用某种数学变换, 将图像等用频域表示, 通过改变某些频域系数加入待隐藏消息, 然后再利用反变换来生成隐藏有其它信息的图像等。常用的具体算法有:

1.DCT域嵌入算法。这种算法是将图像分割成为8×8的不重迭的像块, 经DCT变换后, 对其部分交流系数进行调整并嵌入隐藏信息。这一算法旨在兼顾了嵌入信息的不可察觉性和鲁棒性, 提出了应将水印信息嵌入图像信息中被感知的重要部分。因为这些部分在有损压缩时还会重点保留, 因此可以提高水印的鲁棒性。该算法利用一个平均能量很低的正态分布的随机数字序列作为水印信息, 并选取DCT系数中除DC系数外的部分较低的频率系数进行调制作为水印信息的嵌入点, 所以可抗拒有损编码并对一些会引起失真的信号进行处理。

2. 小波域嵌入算法。

这种算法通过多分辨率分析的小波分解, 将宿主信号分解到对数间隔的子频带之中, 然后对宿主图像在每个分辨率等级上进行分割, 形成互不相交的像块, 再对各像块按照对视觉效果影响的程度嵌入相应比例的水印信息, 最后, 对嵌入水印后的小波域图像进行小波反变换。

3. 图像自适应嵌入算法。

随着数字水印研究的深入, 一些有图像编码背景的学者选用已有的视觉模型研究的成果, 提出了图像自适应DCT和图像自适应小波水印的算法。这种技术充分运用了人眼在不同变换域的视觉特性, 例如, DCT域和小波域的可觉察性差, 能最大限度地挖掘信息嵌入的潜力, 同时使水印的嵌入对各种图像都有一定的适应能力, 从而提高了水印信息的抗攻击能力。

信息隐藏技术作为一个跨多领域、多学科的技术体系, 由于它与具体的应用密切相关, 这也决定了信息隐藏技术研究成果的多样性以及信息隐藏技术研究的不完善性, 仍有许多尚需拓展的领域和有待解决的课题, 而且其产品也不十分成熟, 还不能完全替代传统的加密技术, 它与人工智能、混沌理论、密码学、数字媒体压缩等领域和技术还需有更进一步的融合。但可以相信, 随着科学技术越来越发达, 信息隐藏将有更多巧夺天工的新创意、新方法和新技术, 将有更加广阔的发展空间。

摘要：信息隐藏是一个十分活跃的研究领域, 其载体可以是文字、图像、语音或视频等不同格式的文件。基于多媒体载体的信息隐藏技术, 目前研究最深入、成果最丰富的是图像信息的隐藏技术。其典型算法主要有:空间域隐藏算法、变换域隐藏算法。

关键词：图像信息隐藏,空间域算法,变换域算法

参考文献

[1]李黎, 潘志庚.一种稳健性好的图象盲水印算法.中国图象图形学报, 2003, 8 (5) :567～571

[2]张新鹏, 王朔中, 张开文.抗统计分析的LSB密写力案.中国图象图形学报, 2003, 8A (9) :1055～LOGO

[3]曹长修, 柏森, 张邦礼.改进的图象小波域水印算法.贵州科学, 2002, 20 (4) :5～9

几种常用排序算法的比较第7篇

排序是计算机程序设计工作中最为常见的操作。它是将一个无序序列,按照一定的关键字排成一个有序的序列。据统计,在计算机的运行时间中,大约有1/4的时间是用到了排序上的。因此寻找高效率的排序算法就显得非常重要了。本文就这几种排序算法的时间复杂度进行对比,帮助我们选择合适的排序算法。

2算法介绍

具体问题举例:给定n个数,要求按照递增对其排序。

(1)直接排序算法

直接排序就是从n个元素中选出最大值ai,让ai和an进行交换,此时an就变成了序列中的最大值。然后再从a1到an-1选出新的最大值ai,让ai再与an-1进行交换,此时an-1就成为了仅次于an的第二大数。经过n-1次之后,就完成了序列的排序。

(2)合并排序算法

合并排序算法就是采用计算机算法思想中的分治策略,实现对个元素进行排序的算法。其基本思想是:先将n个数分成a1……an/2和a(n+1)/2……an两组(两组的元素个数并非完全一样多,大致相同即可),再针对这两个组进行排序,最后再将排好序的两个组进行合并成为所要求的排好序的集合。

(3)快速排序算法

快速排序算法是分治策略的另一个排序算法,它也是一种递归算法。其基本思想是:先选出一个数ai,用其它数分别和ai进行对比,将大于ai的数放到ai的右边,将小于ai的数放到ai的左边,然后再让左右两个子序列进行同样的操作,直至完成整体排序。

3算法分析

(1)直接排序算法分析

令T(n)表示排序的次数,则第一步选出最大值需要做n-1次比较,第二步则需要进行n-2次比较,第三步需要n-3次比较,直至n-1步需要1次比较。根据加法原理,T(n)满足以下关系:

通过计算可得

由此可以看出,不论原来序列元素的大小是如何排列的,用直接排序算法要做次比较,才能得到指定的排序。也就是说,比较的次数只与序列中元素的个数n有关。

(2)合并算法分析

该算法是递归进行的。长度为n/2的两个已排好序的序列,其合并成一个序列的比较次数最好情况下为n/2次,最差情况为n-1次。

根据加法原理,采用合并排序算法在最坏情况时比较的次数如下:

解此递归方程可得知。

同样,采用该算法在最好情况下,需要比较的次数。

由此可以看出合并排序算法是一个渐进最优算法。即当n足够大时,本算法比较次数远远小于直接排序算法的比较次数。

(3)快速排序算法分析

对n个元素进行左右序列划分时,需要做n-1次比较。快速的运行时间与选择的基准元素关系很大。

(1)在最坏情况下,本应分成左序列、右序列和基准元素三个部分,变成了只有左序列或右序列和基本数两个部分,即变成了n-1个元素(左或右序列)和1个元素(基准元素)两部分。假设每一步都不出现了这种极端情况,根据加法原理,则其比较次数T(n)如下:

即便原有需要排序的序列已经是排好顺序的序列,其比较次数也不会减少。

(2)在最好情况下,每次划分所选取的基准元素刚好都是中值,即每次划分都产生了两个都长度基本相等的左右序列。此时其比较次数T(n)如下:

通过解此递归方程,可得出:。

(3)在平均情况下,设T(n)为排序所需比较的平均次数。序列中n个元素被选中为基准元素的概率均为1/n,那么取第i个最小元素为基本元素时,分成的两个子序列分别有i-1个数和n-i个数,则平均比较次数T(n)如下:

求解之后可得出:

可以看出快速排序算法在平均情况下的时间复杂性也是O(n log n),这在基于比较的排序算法中算是比较快速的,快速排序也就因此得名。

4总结

排序算法在算法不仅仅在数学领域,也在计算机、金融、经济、商业等领域有着广泛的应用。本文仅对直接排序、合并排序和快速排序三种算法运用数学方法进行了时间复杂度的比较。通过比较可以知道直接排序效率最差,合并排序和快速排序的效率较高,但快速排序的极端最差情况下,效率也会比较低。通过对这几种算法的详细分析和了解,在实际的工作中能带来较大的帮助。

参考文献

[1]姜建国,岳建国.组合数学[M].西安:西安电子科技大学出版社,2007.

[2]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2001.

常用数据挖掘算法的分析对比第8篇

1 C4.5算法

C4.5算法是数据挖掘中用于分类的算法, 它是在以往的决策树核心算法ID3的基础上进行改进的一个新的决策树算法。所以一般来说, 只要充分了解决策树的构造方法, 就了解C4.5算法的构造。决策树的基本原理是递归地将数据拆分成一个个子集, 使每一个子集都能够包含变量类似的状态, 而这些变量是可以预测属性。这样一来每一次对数据的拆分都要评价输入属性对可预测属性影响, 当递归过程技术时, 决策树也就完成了。在以往的决策树构造中, 往往采用ID3算法作为核心算法, 而ID3算法选择属性用的是子树的信息增益, 也就是熵的变化值, C4.5算法使用的则是信息增益率。虽然从字面上看C4.5算法相比于ID3算法只多了一个“率”, 但是结果却是截然不同的。例如有两个跑步的人, 一个起点是10m/s, 1s后为20m/s;另一个起速是1m/s, 1s后为2m/s。如果我们仅仅只算信息增益的话, 那么这两个人差距就很大了, 但是如果使用速度增加率来衡量, 二者就是一样的了, 所以说在这里, C4.5算法有效地克服了使用信息增益选择属性时偏向选择取值多的属性的不足。

相比于其它算法, C4.5算法具有产生的分类规则易于理解、准确率较高的优势, 但其缺点也是显而易见的。在构造决策树的过程中, C4.5算法需要对数据集进行多次的顺序扫描和排序, 因而导致算法的低效, 因此C4.5算法多用在关联分析、回归任务上。

2 贝叶斯算法

贝叶斯算法是一种利用概率统计知识进行分类的算法, 常被用于预测性建模上。具体来说, 贝叶斯算法可以分成两大类。一是朴素贝叶斯算法, 这种算法成立的一个重要前提就是各个属性之间互相独立。只有当数据集满足这个独立性假设时, 使用朴素贝叶斯算法得到的分类才能够比较准确, 否则的话就可能较低。二是TAN算法, 这种算法是通过发现属性对之间的依赖关系来降低朴素贝叶斯算法中任意属性之间独立的假设。它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。虽然说TAN算法对属性之间独立性的假设有了一定程度的降低, 但是对于属性之间可能存在更多其它的关联性仍没有多加考虑, 因此其适用范围仍然受到限制。

与其它算法相比, 贝叶斯算法所需要的运算量是比较小的, 因此能够快速地建立起挖掘模型, 以发现输入列和可预测列之间的关系。在数据挖掘的初期阶段, 利用贝叶斯算法可以迅速有效地获得参数, 进而可以根据参数选择其它运算量较大、精确度更高的算法来建立模型。一般来说, 贝叶斯算法主要用于分类任务和预测任务上。

3 人工神经网络算法

人工神经网络算法是创建由三层神经元组成的网络, 这些层分别是输入层、可选隐藏层和输出层。其中输入层是指输入神经元定义数据挖掘模型的所有输入属性值及其概率。隐藏层则指的是隐藏神经元接收来自输入神经元的输入, 并向输出神经元提供输出, 隐藏层是向各种输入概率分配权重的位置。权重说明某一特定输入对于隐藏神经元的相关性或重要性。输入所分配的权重越大, 则输入的值越重要。权重可为负值, 表示输入抑制而不是促进某一特定结果。输出层是用来表明输出神经元代表数据挖掘模型的可预测属性值。在多层网络中, 每一个神经元接收一个或多个输入, 产生一个或多个相同输出, 每一个输出都是神经元输入之和的简单非线性函数。

相比其它算法构造的数据挖掘模型, 人工神经网络算法构造的挖掘模型可以包含多个网络, 这取决于输入和预测的数量。因此主要适用于回归任务和分类任务, 但是并不支持数据挖掘维度, 这是因为挖掘模型中节点的结构不一定直接与基础数据对应。

4 K-means算法

数据挖掘算法中, “k-means”最早是由James Mac Queen在1967年提出的, 这一观点可以追溯到1957年Hugo Steinhaus所提出的想法。1957年, 斯图亚特·劳埃德最先提出这一标准算法, 当初是作为一门应用于脉码调制的技术, 直到1982年, 这一算法才在贝尔实验室被正式提出。1965年, E.W.Forgy发表了一个本质上是相同的方法, 1975年和1979年, Hartigan和Wong分别提出了一个更高效的版本。具体来说, K-means算法分成以下几个步骤: (1) 从D中任意选择k个对象作为初始簇中心; (2) 根据簇中对象的均值, 将每个对象指派到最相似的簇; (3) 使用每个簇的样本来计算每个簇新的平均值; (4) 计算准则函数一直到准则函数不再发生变化。

K-means算法简单、快速, 是解决聚类问题的一种经典算法, 在处理大数据集时, 这种算法是相对可伸缩和高效率的, 因为它的复杂度大约是O (nkt) 。其中n是所有对象的数目, k是簇的数目, t是迭代的次数, 通常k<<n。这个算法经常以局部最优结束, 但是相比于其它数据挖掘算法来说, K-means算法由于只有在簇的平均值被定义的情况下才能使用, 要求用户必须事先给出要生成的簇的数目k, 因此不适用于涉及有分类属性的数据。

5 遗传算法

遗传算法是模拟生物进化的过程, 利用复制 (选择) 、交叉 (重组) 和变异 (异变) 三个基本算子优化求解的技术。遗传算法把问题的解表示成“染色体”, 在执行遗传算法之前, 先给出一群“染色体”也就是假设解。然后根据适者生存的自然规律, 从这群染色体中选择一个能够适应环境的“染色体”, 并对这个染色体进行复制, 再通过交叉、变异过程进而产生更能适应环境的新一代“染色体”群。经过这样一次次的循环进化, 最后得到一个最合适的“染色体”, 这个“染色体”就是问题的最优解。

相比于传统的优化算法, 遗传算法的操作对象是一群假设解, 即群体中的各个个体, 是利用遗传信息和竞争机制来指导搜索方向。因此遗传算法具有潜在的并行性, 可以进行多个个体的同时比较, 并且拥有很大的可扩展性, 很容易和其它算法相结合。但是遗传算法的编程实现比较复杂, 首先需要对问题进行编码, 找到最优解之后还需要对问题进行解码。另外三个算子的实现也有许多参数, 如交叉率和变异率, 并且这些参数的选择严重影响解的品质, 而目前这些参数的选择大部分是依靠经验, 这增加了在数据挖掘上应用遗传算法的难度。

6 结语

数据挖掘是当今计算机领域的一个热门课题, 在各个领域中都有着广阔的应用空间, 而数据挖掘算法对数据挖掘有着决定性的影响。笔者对常见的几种数据挖掘算法进行了分析和比较, 初步探讨了几种数据挖掘算法的应用范围。总而言之, 每一种数据挖掘算法的应用范围是有限的, 因此单一地采取一种数据挖掘算法是无法满足决策需求的, 将各种数据挖掘算法有机地组合起来将成为数据挖掘算法的发展趋势。

摘要：当今社会, 数据挖掘在商业领域和工业领域中所起的作用越来越大。但是随着科学技术的发展, 知识也出现了爆炸式增长, 在这种情况下, 研究数据挖掘算法, 以便根据不同的需求选择不同的数据挖掘算法, 从而降低成本、提高效率成为一件刻不容缓的事。笔者对C4.5、K-means算法、贝叶斯算法、人工神经网络算法等常用的数据挖掘算法进行了研究探讨, 希望能够为数据挖掘研究者们提供一些借鉴。

关键词：数据挖掘,算法,分析

参考文献

[1]刘华元, 袁琴琴, 王保保.并行数据挖掘算法综述[J].电子科技, 2006 (01) .

[2]王海涛, 陈树宁.常用数据挖掘算法研究[J].电子设计工程, 2011 (06) .

电子商务中常用的RSA算法实现第9篇

一、RSA算法描述

密钥对的产生。选择两个大素数p和q。计算:n=p*q, 然后随机选择加密密钥e, 要求e和 (p-1) * (q-1) 互质。最后, 利用Euclid算法计算解密密钥d, 满足e*d=1mod ( (p-1) * (q-1) ) , 其中n和d也要互质。{e, n}是公钥, {d, n}是私钥。加密信息m (二进制表示) 时, 首先把m分成等长数据块m1, m2, …, mi, 块长s, 其中2∧s<=n, s尽可能的大。对应的密文是:ci= (mi∧e) mod n, 解密时作如下计算:mi= (ci∧d) mod n

二、程序实现的主要思想

Java中的Big Integer类提供了实施RSA公钥加密系统所必需的全部可能性。本程序根据生成公钥/私钥对来论证RSA。用户输入一串字符串, 用公钥加密字符串, 用私钥解密字符串, 所有的结果被输出。

三、主要算法流程和框图

1. 主要算法流程

随机生成p, q→计算N=p*q→计算p1=p-1, q1=q-1→计算p1q1=p1*q1→随机生成e, e须满足gcd (p1q1, e) =1, 1

2. 主要框图

四、主要模块说明

1. 主函数模块

生成公钥/私钥对, 调用加密模块对明文进行加密, 然后调用解密模块对密文进行解密。

2. 转换字符串为大整数模块

转换字符串为大整数。字符串应该仅由ASCII字符组成。简单地将ASCII代码连接而形成整数。

3. 转换大整数为ASCII字符串模块

转换大整数为ASCII字符串。整数里的各个字节简单地被转换成对应的ASCII代码。

4. 加密模块

用公钥 (N, e) , 应用RSA加密算法对字符串进行加密。字符串被分成多个数据块, 每一个数据块被转换为一个整数, 然后这个整数x用算式:x∧e (mod N) 被编码 (加密) 。

5. 解密模块

用私钥 (N, d) , 应用RSA解密算法对字符串进行解密。首先用算式:x∧d (mod N) 解码整数列里的每一个整数x, 然后每个被解码的整数被转换为一个字符串, 且所有的字符串被连接成一个单一的字符串。

五、程序使用说明

在Textpad中, 输入源程序后, 保存源程序 (假若源程序文件名为RSA.java) , 编译源程序, 编译成功后, 在原RSA.java程序所在的文件夹中生成RSA.class文件, 然后运行该程序, 如果一切运行正常, 则输出正确结果。

六、结束语

本文用Java语言实现了RSA算法。由于用到java中的Big Integer类, 因此运行效率较高。如果用C语言编程, 一个运行结果大约需要2个多小时才能算出, 而用java中的Big Integer类编程则几秒钟结果就出来了, 因此, 对RSA算法用Java编程显然比用C语言编程的效率要高得多。

参考文献

[1][美]William Stallings著.密码编码学与网络安全:原理与实践 (第二版) [M].杨明等译.北京:电子工业出版社, 2001

[2]唐大仕编著:Java程序设计[M].北京:北方交通大学出版社, 清华大学出版社, 2003

[3]田文春韦岗:RSA算法的Java实现[J].计算机工程与应用.2001, (24) :43～44, 62

TSP问题的几种常用求解算法比较第10篇

1 TSP问题描述

2 TSP问题几种常用求解方法

TSP问题有着很多求解算法, 主要有。

2.1 贪婪算法

贪婪算法[2] (Greedy algorithm) 是求解大规模TSP问题的常用算法之一, 是一种求解优化问题的简单、迅速的求解办法。贪婪法有限考虑当前情况下最优的优化测度, 自顶向下, 逐步迭代, 具有算法简单, 耗时短的特点。但贪婪算法的求解结果往往不是最优的, 甚至可能与全局最优解间有不小的差距。

2.2 模拟退火算法

模拟退火 (Simulated Annealing, SA) 算法是求解TSP问题的有效方法之一, 容易编程实现, 求解速度快。模拟退火是一种全局优化算法, 加入了随机状态模型, 使算法以概率选择的方式逼近最优状态, 其收敛性可以得到严格的理论证明。模拟退火算法具有一整套完整的退火搜索计划, 包括足够高的初始温度、缓慢的退火速度、大量的迭代次数及足够的概率扰动[3]。

2.3 遗传算法

遗传算法 (Genetic Algorithm, GA) 是一种常用的智能算法, 具有全局搜索能力, 对TSP问题有良好的效果。遗传算法是由Michigan大学的J.Holland教授于1975年提出, 算法通常由编码、个体适应度评估和遗传运算三部分构成, 其中遗传运算包括染色体复制、交叉、变异和倒位等[4]。

2.4 粒子群算法

粒子群算法 (Particle Swarm Optimization, PSO) 是依据鸟类觅食的群体性模型而发明的新型智能算法, 是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出, 具有通用性强, 参数少, 容易实现, 收敛速度快等优点, 也是解决TSP问题的有效算法之一[5]。

2.5 蚁群算法

蚁群算法 (Ant Colony Optimization, ACO) 是根据蚂蚁发现路径的行为的而发明的用于寻求优化路径的机率型算法, 由Marco Dorigo于1992年在他的博士论文中提出。蚁群算法是一种模拟进化算法, 具有包括较强的鲁棒性在内的许多优良性质, 在本质上是一种并行的分布式算法, 容易实现, 可以较好地求解TSP问题[6]。

3 实例计算

选取我国北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌等十个城市, 分别使用1-10对十个城市进行编号, 获取十个城市的距离矩阵, 使用上节所述算法进行求解。已知路径最小长度为12055, 最优路径为2-1-8-9-6-3-5-4-10-7-2, 求解结果如表1所示。

图1为四种智能算法的收敛状态。

4 各种求解算法的比较

根据本文的实例计算和相关文献[7], 可以给出各算法的比较。

5 结语

TSP问题有着很大的求解难度, 但并不意味着无法进行有效的求解, 使用一些比较成熟的智能化算法进行求解, 可以获得较好的解答。当然各种近似求解算法还有着一些固有的缺陷, 在不同情况下有着不同的性能表现, 需要在使用时加以选择。

摘要：本文介绍了TSP问题及其常见的解法, 给出了计算实例, 并结合计算实例对各求解算法进行了比较。本文对于各种算法的比较对于TSP问题的求解具有一定的参考价值。

关键词：TSP问题,0-1规划,智能算法

参考文献

[1]谢金星, 薛毅.优化建模与Lindo/Lingo软件.北京:清华大学出版社, 2005.

[2]黄辉, 梁国宏等.求解一类线性规划问题的原始贪婪算法和对偶贪婪算法及其相互关系[J].兰州交通大学学报, 2007, 26 (1) :149-152.