最小和算法范文

2024-06-10

最小和算法范文（精选11篇）

最小和算法第1篇

为解决电磁场逆问题分析计算对计算机资源过度需求这一“瓶颈”问题,近年来人们提出了表面响应模型(Response Surface Model)法。该方法的基本原理是:首先将决策变量空间离散为一系列采样点,并利用数值计算方法计算出目标/约束函数在这些采样点的函数值;然后根据目标/约束函数在这些采样点的函数值,利用一定的表面响应模型重构目标/约束函数;最后,应用某一优化算法,对重构的优化问题进行寻优计算,得到原问题的近似解。由于表面响应模型方法仅在计算目标/约束函数采样点的函数值时需要进行电磁场的数值计算,因此与传统的分析方法相比,这种方法的计算效率大大提高。显然,表面响应模型法的计算精度取决于所采用的表面响应模型的精度。目前,在计算电磁学领域中应用的表面响应模型主要是基于径向函数(Radial Basic Function)而构造的。研究表明,基于径向函数构造的表面响应模型的主要不足是:①所构造的函数不是“某种”意义上的“最优”函数;②这种模型处理不规则的采样点比较困难;③不能自动实现算法参数的最佳匹配;④当采样点很多时,重构函数的计算仍需耗费较大的计算资源。

为解决现有表面响应模型的上述不足,本研究提出一种基于移动最小二乘法的表面响应模型,以实现对复杂电磁场逆问题的目标函数进行重构;然后将其与粒子群算法相结合,提出一种多峰函数的快速全局优化算法。

1基于MLS的表面响应模型

移动最小二乘法最早由Shepard提出,用于低维曲线的拟合问题[1],随后Lancaster和Salkauskas将其推广到高维问题[2]。因为该方法的拟合能力很强,近年来已广泛应用于曲线曲面拟合、无网格法等领域。

对于任意f(x):Rn→R,如果已知其在一系列采样点xi∈RD(i=1,2,…,N)上的函数值为fi,则在选定的基函数b={b(i)} $_{i = 1}^{n}$ (n≤N)条件下,首先定义MLS的局部近似Lxf为:

Lxf: $= \sum_{i = 1}^{n} a_{i} (x) b^{(i)}$ (1)

式中,基函数b={b(i)} $_{i = 1}^{n}$ (n≤N)满足:

(i) b(1)≡1;

(ii) b(i)∈Cm(RD) (i=1,2,…,n);

(iii) 在给定的某n个采样点上,{b(i)} $_{i = 1}^{n}$ 是相互独立的。

然后,再定义全局投影算子Gf 为:对任意一点x∈RD,

$G f (x) = L_{x} f (x) = \sum_{i = 1}^{n} a_{i} (x) b^{(i)} (x)$ (2)

为确定系数a(x),利用以下由内积定义的L2-范数,即:

(u,v)x=uTw(x)v (3)

‖u‖2=(u,u) $_{x}^{1 / 2}$ (4)

式中,z=(z(x1) z(x2) … z(xN))T(z=u,v), w(x)为一N×N对角线矩阵,其对角线元素为w(i)(x)(w(i)(x)为MLS的权函数)。

MLS的特征之一是:权函数w(i)(x)为以i个采样点为中心的紧支函数。因此,MLS近似为一种局部近似。

由Gf为函数f的最小二乘意义上的近似,有:

a(x)=A(x)-1B(x)f (5)

式中:

$f = [\begin{matrix} f_{1} & f_{2} & \dots & f_{Ν}]^{Τ} \end{matrix}$ (6)

$A (x) = \sum_{i = 1}^{Ν} w^{(i)} (x) b (x_{i}) b^{Τ} (x_{i})$ (7)

$B (x) = [\begin{matrix} w^{1} (x) b (x_{1}) & w^{2} (x) b (x_{2}) & \dots & w^{Ν} (x) b (x_{Ν})] \end{matrix} (8)$

由此得到基于移动最小二乘的表面响应模型。一般来说,MLS不是插值型的拟合方法,为使得MLS变成插值型的近似方法,对权函数修正如下:

$\frac{w^{i} (x)}{| x - x^{i} |^{α}}$ (9)

式中 α—一正数。

2基于MLS和PSO算法的快速全局优化算法

2.1粒子群算法简介

粒子群优化算法是人们通过模拟鸟、鱼等群体觅食行为和过程而提出的一种智能优化算法[3,4]。类似于基因算法,该算法也是以种群为基础进行迭代计算。在粒子群算法中,种群称之为群,个体称之为粒子。与基因算法不同,粒子群算法中没有交叉与变异等操作。该算法的基本原理是:对于由Npopsize个粒子组成的群,任一粒子i(i∈{1,2,…,Npopsize})都有一位置矢量xi=(x $_{1}^{i}$ ,x $_{2}^{i}$ ,…,x $_{D}^{i}$ )(相当于优化问题的一个可行解,D为优化变量的个数)与之对应。在迭代过程中,粒子i通过跟踪两个“极值点”实现其位置矢量的更新;其中第一个“极值点”是该粒子到目前为止搜索到的“最优点”(Pbest),记为pi=(p $_{1}^{i}$ ,p $_{2}^{i}$ ,…,p $_{D}^{i}$ );而另一个“极值点”则是第i个粒子所有相邻粒子到目前为止找到的“最好点”(Gbest),记为gi=(g $_{1}^{i}$ ,g $_{2}^{i}$ ,…,g $_{D}^{i}$ )。粒子i下一迭代步(k+1)的位置矢量xi(k+1),由该粒子当前迭代步(k)的位置矢量xi(k)加上一个矢量增量Δxi(k+1)确定;该矢量增量Δxi(k+1)又称为速度矢量vi(k+1),它决定粒子i下一迭代步移动的方向与速度。该过程的具体数学描述为:

v $_{d}^{i}$ (k+1)=v $_{d}^{i}$ (k)+c1r1(p $_{d}^{i}$ -x $_{d}^{i}$ (k))+c2r2(g $_{d}^{i}$ -x $_{d}^{i}$ (k)) (10)

$\begin{array}{l} v_{d}^{i} (k + 1) = \frac{v_{d}^{i} (k + 1) \cdot v_{d}^{\max}}{| v_{d}^{i} (k + 1) |} (i f | v_{d}^{i} (k + 1) | > v_{d}^{\max}) (11) \\ x_{d}^{i} (k + 1) = x_{d}^{i} (k) + v_{d}^{i} (k + 1) (12) \end{array}$

式中 c1,c2—两个正常量;r1,r2—[0,1]区间内的随机数;v $_{d}^{\max}$ —粒子在d坐标方向上的速度限值。

理论分析与数值实验表明,上述的原始粒子群算法不能很好地实现全局搜索和局部搜索的平衡。因此,算法的全局寻优能力较弱。为此,进行了如下的改进研究。

2.2速度矢量与位置矢量更新算法

对于前述的标准PSO算法,在速度矢量更新过程中,随机数r1和r2彼此独立产生,因而难免会发生r1和r2同大或同小的情况。对于前者,一般而言,个体认知能力和社会经验的作用被过分夸大,因此,粒子不能收敛到潜在的最优点。相反,对于后者,无论是个体认知能力还是社会经验,都没有得到很好的利用,因此算法的收敛速度将降低。事实上,在一个“智能”社会中,r1和r2这两个随机参数并不是完全独立的,智能个体可利用其“推理”能力,确定r1和r2这两个随机参数的相对大小,即决定某一时步到底根据个体经验还是群体经验确定其下一时步的搜索方向。将智能社会中个体的这一“推理”能力融入粒子群算法中,本研究提出了如下的速度矢量更新算法:

v $_{d}^{i}$ (k+1)=r2v $_{d}^{i}$ (k)+(1-r2)c1r1(p $_{d}^{i}$ -x $_{d}^{i}$ (k))+(1-r2)c2(1-r1)(g $_{d}^{i}$ -x $_{d}^{i}$ (k)) (13)

$\begin{array}{l} \begin{array}{l} v_{d}^{i} (k + 1) = \frac{v_{d}^{i} (k + 1) \cdot v_{d}^{\max}}{| v_{d}^{i} (k + 1) |} (i f | v_{d}^{i} (k + 1) | > v_{d}^{\max}) \\ v_{d}^{i} (k + 1) = \frac{v_{d}^{i} (k + 1) \cdot v_{d}^{\min}}{| v_{d}^{i} (k + 1) |} (i f | v_{d}^{i} (k + 1) | < v_{d}^{\min}) \end{array} (14) \\ x_{d}^{i} (k + 1) = x_{d}^{i} (k) + v_{d}^{i} (k + 1) (15) \end{array}$

式中 c1,c2—两个正常数;r1,r2—[0,1]区间内的随机数。

2.3 “年龄”变量的引入

尽管粒子群算法的信息共享机制可保证算法具有较快的收敛速度,但由于在寻优过程中每个粒子只追踪两个“极值”点,很难保证粒子的多样性,进而导致搜索过程中发生“stagnation”现象,即所有粒子的位置矢量都相同,算法陷于死循环状态。为避免这种现象的发生,在研究过程中对Pbest和Gbest中每个极值点设置一个“年龄”变量。每增加一代迭代,上述极值点的年龄都要增加一岁。当某个极值点的年龄足够大时,说明再在这个极值点附近寻优也不可能找到更好解。因此,在迭代过程中,如果某一极值点的年龄大于某一事先给定的正数,则在Pbest或Gbest中将该点删除,随机产生一新点代替该点。由此可避免现有PSO算法可能发生的“stagnation”现象。

2.4基于MLS和PSO算法快速全局优化算法

在上述工作的基础上,本研究提出了一种电磁装置快速全局优化设计新算法,以期在给定的计算精度要求下减少电磁场数值计算的迭代次数。其具体迭代过程如下:

(1) 产生采样点,计算这些采样点上的目标函数和约束函数的函数值;

(2) 利用本研究提出的基于MLS的表面响应模型重构原优化问题;

(3) 应用改进的粒子群算法求解该重构的优化问题,得到原问题的近似解;

(4) 以得到的近似解为初值,应用某一确定类的搜索方法,直接对原优化问题进行优化,得到优化问题的改进解。

3应用实例

以文献[5]中的三参数优化问题作为电磁场逆问题的应用实例。TEAM (testing of Electromagnetic Analysis Method) Workshop Problem是国际计算电磁学界的学者和研究者提出的一系列以相关工程问题为背景的基准问题,藉以校验和比较各种算法的正确性和有效性。其中的问题22为超导磁储能系统SMES(Superconducting Magnetic Energy Storage)优化设计问题。SMES系统利用SMES装置将交流电网供电、励磁所产生的磁场能量储存起来,在需要时再将储存的能量回馈交流电网或另作他用。因此,SMES系统一般由SMES 线圈(装置)和电力电子逆变器组成,如图1所示。

该问题的超导线圈为双螺管结构,其中一个线圈为位于内侧的主线圈,另一个是位于外侧的屏蔽线圈,如图2所示。主线圈的尺寸不变,而屏蔽线圈的尺寸(即R2、h2和d2)为优化变量。为减小线圈周围环境电磁场的幅值,两个线圈施加方向相的电流。在进行SMES装置优化设计时,主要考虑的因素包括:

(1) 装置中存储的能量应该是180 MJ;

(2) 磁场绝不能违背“确保超导性”的物理条件;

(3) 远离储能装置10 m处的漏磁场应该尽可能小。

对于给定的超导材料,为保证超导体不失超,两个线圈中的电流密度和磁感强度之间应该满足下面的约束方程:

Ji≤(-6.4|(Bmax)i|+56)(A/mm2) (i=1,2) (16)

式中 Ji,|Bmax|i—第i个线圈中的电流密度,最大磁感应强度。

对于三参数问题,两个线圈中的电流密度为定值(22.5 A/mm2),所以式(16)可以变为:

|Bmax|≤4.92T (17)

综上所述,该优化问题的数学模型为:

$\min f = w_{1} \frac{B_{s t r a y}^{2}}{B_{n o r m}^{2}} + w_{2} \frac{| E n e r g y - E_{r e f} |}{E_{r e f}} (18)$

|Bmax|≤4.92T (19)

式中 Eref=180 MJ; Bnorm=3×10-3T; Energy—超导系统的实际储能;w1,w2—权系数;Bmax—线圈中的最大磁通密度;B $_{s t r a y}^{2}$ —衡量SMES装置磁场对周围电磁环境影响的一个指标,其大小等于图2中直线A和直线B上22个等距点上磁通密度平方的平均值,即:

$B_{s t r a y}^{2} = \frac{\sum_{i = 1}^{22} B_{s t, i}^{2}}{22}$ (20)

采用有限元法计算SMES装置中的轴对称电磁场及其存储的电磁场能量。对于该问题,采用本研究提出的快速全局优化算法进行分析和计算。应用本研究算法搜索到的最优解及其迭代次数,以及迄今为止文献中给出的最佳研究成果[6],如表1所示。在最优解条件下SMES线圈中磁场的等位线分布,如图3所示。显然,采用本研究的优化技术,通过电磁场逆问题的求解计算,经过有限次的有限元分析和计算,不仅能够保证SMES系统中的储能为180 MJ,而且系统产生的电磁污染远远小于电磁兼容标准规定的限值。

4结束语

根据实际工程电磁场逆问题的特点,提出了一种求解复杂电磁装置优化设计问题的快速全局优化算法。通过典型工程问题的分析和计算,验证了本研究所提出算法的有效性和优越性。因而,本研究的算法为求解复杂的电磁场逆问题提供了一种可供选择的新方法。

参考文献

[1] SHEPARD D. A Two-dimensional Interpolation Function for irregularly Spaced Points[C]. Proc. 1968 ACM national Conference,1968:517-524.

[2]LANCASTER P,SALKAUSKAS K.Surface generated bymoving least squares methods[J].Mathematics of Com-putation,1981,37(155):141-58.

[3]KENNEDY J,EBERHART R.Particle Swarm Optimization[C].Proceedings of IEEE International Conference on Neu-ral Networks,Perth,Australia,IV,1995:1941-1948.

[4] EBERHART R C, KENNEDY J. A New Optimizer Using Particle Swarm theory[C]. Proceedings of 6th International Symposium on Micro Machine and Human Science, Nagoya, Japan, Piscataway,1995:39-43.

[5]SME S.Optimisation Benchmark Problem Description[EB/OL].[2006-01-01].http://www.igte.tugraz.at/ar-chive/team_new/description.php.

网络最小树的一种矩阵算法第2篇

网络最小树的一种矩阵算法

求网络最小树问题,人们熟知常用的方法有“避圈法”和“破圈法”,这些方法有其直观易解的优点,然而它们毕竟是要在图上作业(在图上完成).由于网络与距离矩阵的`对应关系,本文将利用矩阵性质给出该问题的一个矩阵解法.

作者：吴振奎唐文广王全文罗蕴玲 WU Zhen-kui TANG Wen-guang WANG Quan-wen LUO Yun-ling 作者单位：天津商业大学,理学院,天津,300134刊名：运筹与管理 ISTIC PKU英文刊名：OPERATIONS RESEARCH AND MANAGEMENT SCIENCE年，卷(期)：200817(3)分类号：O157.5关键词：运筹学网络树最小树距离矩阵

泊松化图像复原的交替最小化算法第3篇

关键词图像复原；泊松噪声；全变差；交替最小化算法

中图分类号 TP391 文献标识码 A

Alternating Minimization Algorithm

for Poissonian Image Restoration

LIU Xinwu

（School of Mathematics and Computational Science， Hunan University of Science

and Technology， Xiangtan， Hunan 411201，China）

Abstract To quickly remove Poisson noise， based on the traditional alternating direction method， this paper combined the relaxation method and proposed an improved alternating minimization algorithm. Compared with the classical numerical algorithm， numerical simulations demonstrate that the proposed strategy not only removes Poisson noise efficiently， but improves the speed of calculation substantially and reduces the computer CPU time noticeably.

Key words image restoration； Poisson noise； total variation； alternating minimization algorithm

1 引言

图像在形成、传输和存储过程中，不可避免地会受到噪声的影响. 譬如，在天文成像[1]和电子显微镜成像[2，3]中，获得的图像就往往会受到泊松噪声污染，并出现明显的降质现象，因此图像复原就显得尤为重要. 目前，图像复原技术已在天文学、医学、刑侦、军事以及金融学等领域得到了广泛的应用. 例如，在商业和金融行业中，一个新兴的融合信息科学、金融学和管理学的先进金融信息技术（如模式识别、人工智能等）已有效地应用于金融票据识别、金融票据影像处理及打印中，并成功地解决了一系列经济领域中的热点和难点问题.

4 结论

本文研究了一个基于TV正则化模型的泊松化图像复原问题. 为了提高数值计算的速率，本文结合传统的交替方向法和松弛算法，提出了一个改进的交替最小化算法. 数值试验表明，新算法在泊松去噪中具有显著的优越性和高效性.同时，该算法也必将在金融行业中的金融票据识别和票据影像处理中得到进一步的发展和应用.

参考文献

[1] E BRATSOLIS， M SIGELLA. A spatial regularization method preserving local photometry for RichardsonLucy restoration [J]. Astronomy Astrophysics， 2001， 375（3）： 1120-1128.

[2] N DAY， L BLANCFERAUD， C ZIMMER， et al. RichardsonLucy algorithm with total variation regularization for 3D confocal microscope deconvolution [J]. Microscopy Research and Technique， 2006， 69（4）： 260-266.

[3] A KRYVANOS， J HESSER， G STEIDL. Nonlinear image restoration methods for marker extraction in 3D fluorescent microscopy[C]//Proceedings of SPIE， San Jose， CA， USA. Computational Imaging III， 2005， 5674： 432-443.

[4] T LE， R CHARTRAND， T ASAKI. A variational approach to constructing images corrupted by Poisson noise [J]. Journal of Mathematical Imaging and Vision， 2007， 27（3）： 257-263.

[5] A SAWATZKY， C BRUNE， F WUBBELING， T KOSTERS， K SCHAFERS， M BURGER. Accurate EMTV algorithm in PET with low SNR[C]//IEEE Nuclear Science Symposium Conference Record， Dresden， Germany， 2008， 5133-5137.

[6] C BRUNE， A SAWATZKY， M BURGER. Primal and dual Bregman methods with application to optical nanoscopy [J]. International Journal of Computer Vision， 2011， 92（2）： 211-229.

[7] M FIGUEIREDO， J BIOUCASDIAS. Restoration of Poissonian images using alternating direction optimization [J]. IEEE Transactions on Image Processing， 2010， 19（12）： 3133-3145.

[8] S SETZER， G STEIDL， T TEUBER. Deblurring Poissonian images by split Bregman techniques [J]. Journal of Visual Communication and Image Representation， 2010， 21（3）： 193-199.

[9] X LIU， L HUANG. Total bounded variationbased Poissonian images recovery by split Bregman iteration [J]. Mathematical Methods in the Applied Sciences， 2012， 35（5）： 520-529.

[10]T F CHAN， P MULET. On the convergence of the lagged diffusivity fixed point method in total variation image restoration [J]. SIAM Journal on Numerical Analysis， 1999， 36（2）： 354-367.

[11]C VOGEL， M OMAN. Iteration methods for total variation denoising [J]. SIAM Journal on Scientific Computing， 1996， 17（1）： 227-238.

[12]A CHAMBOLLE. An algorithm for total variation minimization and application [J]. Journal of Mathematical Imaging and Vision， 2004， 20（1-2）： 89-97.

[13]M K NG， L QI， Y YANG， Y HUANG. On semismooth Newton’s methods for total variation minimization [J]. Journal of Mathematical Imaging and Vision， 2007， 27（3）： 265-276.

[14]T GOLDSTEIN， S OSHER. The split Bregman algorithm for L1 regularized problems [J]. SIAM Journal on Imaging Sciences， 2009， 2（2）： 323-343.

[15]J F CAI， S OSHER， Z SHEN. Split Bregman methods and frame based image restoration [J]. Multiscale Modeling & Simulation， 2009， 8（2）： 337-369.

[16]X LIU， L HUANG. Split Bregman iteration algorithm for total bounded variation regularization based image deblurring [J]. Journal of Mathematical Analysis and Applications， 2010， 372（2）： 486-495.

[17]W YIN， S OSHER， D GOLDFARB， J DARBON. Bregman iterative algorithms for L1minimization with applications to compressed sensing [J]. SIAM Journal on Imaging Sciences， 2008， 1（1）： 143-168.

最小和算法第4篇

随着信息化的发展, 人们对低密度奇偶校验(Low Density Parity Check , LDPC ) 码有了重新的认识。 LDPC码作为高效的信道纠错编码,具有较低的译码复杂度,系统吞吐量较大, 已在电力线载波(Power Line Carrier ,PLC) 通信、第三代和第四代无线移动通信等方面得到了广泛应用[1]。相对于turbo译码算法[2],采用LDPC编码和置信传播(Belief Propagation ,BP)译码算法更受人们的青睐[3]。但是BP算法存在对硬件存储量的需求较大以及对信道情况较为敏感等问题。人们更趋向于鲁棒性更好和复杂度更低的译码算法, 最典型的就是并行最小和(Parallel Min - Sum , PMS ) 算法[4]。这类算法在实现中只需要加法和比较运算, 且不需要知道信道情况, 可以获得性能和复杂度的良好折衷。考虑到PMS算法前后两次迭代译码过程中,参与信息交换的置信度被过高估计, 文献[5] 通过引入归一化权重因子来减少这种负面影响,使其性能逼近最优BP算法的性能, 可称之为归一化并行最小和( Normalized Parallel Min - Sum , N - PMS ) 算法。随着研究的深入,人们提出了不同的译码机制来提高置信传播的效率,其中较为重要的一类是采用权重因子的串行最小和( Normalized Serial Min - Sum , N - SMS ) 算法[6]。在电力线载波通信中,收发模块通常采用具有低存储量和低复杂度的编、译码算法。 N-SMS算法虽然在存储上较N-PMS算法有一定减少, 但N-SMS算法由于每次迭代都采用min操作来更新最小值, 复杂度相对较高。

为实现可靠通信, 并综合考虑实现成本、器件功耗以及处理复杂度的问题, 针对N-SMS算法提出了一种基于竞争机制的归一化的串行最小和(Normalized Com- petitive Min - Sum , N - CMS ) 算法。该算法在按照自然顺序更新变量节点对校验节点消息的同时,还利用竞争关系更新变量节点对校验节点消息集合中的最小值。与文献[ 6 ] 类似的是, N - CMS在更新某一变量节点时, 同时利用了与该节点之前已更新的软信息和该节点之后还未更新的软信息,所以N-SMS算法与N-CMS算法的性能相同。不同的是,N-CMS通过采用竞争机制来更新属于同一校验式的变量节点集合中的最小值, 避免了文献[6] 中采用min操作的复杂运算,并进一步减少了存储量。

1 N -PMS算法简介

为了简化叙述, 该文沿用文献[7] 中的部分符号定义。设m和n分别表示校验节点和变量节点,H为LDPC码对应的校验矩阵, 当变量节点和校验节点有边相连接时,则hmn= 1 , 它是H中的第m行和n列的元素。 N(m)={n|hmn=1} 表示参与校验方程m的变量节点的集合, N ( m ) n为N ( m ) 中除去元素n后构成的集合; 相应地, M ( n ) = {m|hmn=1} 表示与变量节点n相连的校验节点的集合,M (n)m为集合M (n) 中除去元素m后构成的集合。设Qxnm是从变量节点n传递给校验节点m的软信息 ,表示在给定接收序列y , 并且除了第m个校验方程外 ,其他与n相关的校验方程都满足的条件下 ,xn= x的概率 ; Rxmn是由校验节点m传递给变量节点n的软信息 , 表示在xn= x , 且参加第m个校验方程的除n外的其他变量节点的概率已知的条件下 , 该校验方程成立的概率 ,其中

设s为长为N的编码序列x =[x1, x2, … , xN]T经过BPSK调制后的信号, g是均值为0 、方差为 σ2的高斯噪声。设s经过AWGN信道后的接收序列为y=[y1,y2,… ,yN]T, BP译码后的序列为其中 :

定义变量信息、校验信息和后验信息分别为:

传统的N-PMS算法可归纳如下:

初始化:令先验信息L(Pn) = yn, L( Qnm) = L( Pn)

步骤1: 判断是否达到设定的最大迭代次数MT, 若是则程序结束;否则执行步骤(2)。

步骤2:对m=1,2,… ,M和所有的n∈N(m) 计算:

在上式中,αnm= sign ( L( Qnm) ) 和 βnm= abs ( L( Qnm) ) , 分别表示L(Qnm) 的符号和绝对值, λ 为归一化权重因子, 满足0 ≤ λ ≤ 1 。

步骤3:对n=1,2,… ,N和所有的m∈M(n) 计算:

步骤4 : 对译码软信息进行硬判决, 若L (Qn) < 0 , 则, 否, n= 1 , 2 , … , N。若, 则译码成功 ,程序结束 ,否则转到步骤(1)。

2 N -CMS算法的原理与实现步骤

在N-PMS中, 校验节点和变量节点是分别并行更新的。文献[4]指出,对于H矩阵中的第m个校验式,N-PMS在计算所有n ∈N (m) 集合中的最小值时 , 可以通过找出该集合中最小的两个量 γ1和 γ2来简化运算。

初始化 : 令先验信息L(Pn) = yn, L ( Qnm) = L ( Pn) , 对m =1 , 2 , … , M, 采用操作计算对应于各个m的最小的两个值 γ1和 γ2, 且 γ1≤γ2。

步骤1: 判断是否达到设定的最大迭代次数MT, 若是则程序结束 ; 否则按照n=1,2, … ,N的顺序更新变量节点对校验节点的消息 ,执行步骤(2)。

步骤2: 对特定的n和每一个m ∈M (n) 按照式 (5) 计算L(Rmn) , 此处的min操作由 γ1和 γ2取代。

步骤3: 对特定的n和每一个m ∈M (n) 依据式 (6)、式(7)算出L(Qn) 和L( Qnm) , 由更新后的L( Qnm) 得出 β ′nm后 , 再根据竞争模式更新 γ1和 γ2。

步骤4 : 若n ≤ N , 对译码软信息进行硬判决 , 若L( Qn) < 0 , 则, 反之转到步骤 ( 2 ) 。否则执行步骤(5)。

3复杂度及存储量分析

对于操作 ,N-PMS算法在每次迭代中借助二进制树图需要N/2 (2J +「log22J骎 - 2 ) 次加法运算 [6] ; N - SMS算法则需要更大的计算量 , 为NJ ( 2J + 「 log22J - 2 ) 次加法运算 ;N -CMS算法只在初始化时计算一次而在之后的迭代过程中 , 按照竞争机制对 γ1和 γ2更新即可 ,其运算量相对于N-SMS可大为简化。在竞争机制中 , 更新 γ1和 γ2时 ,β ′nm与 γ1和 γ2的比较关系需要2次操作 , 所以对每个校验式来说 ,2J个变量节点总共要4J次操作 , 从而N/2个校验式共需2NJ次操作。设N-PMS、N-SMS和N-CMS所需的平均迭代译码次数分别为, 注意到N - CMS只是N - SMS算法复杂度的简化 , 所以有表1归纳了其在计算时的平均译码复杂度 , 可以看出 , 当相差不大时 ,N-PMS的平均译码复杂度最低 ,N-CMS次之 ,而N-SMS较高。

另一方面 ,N-PMS需要较大的存储 , 根据式 (5), 对于每个校验式m,需要2个单元来存储2个最小值 ,所以对于N/2个校验式 ,L(Rmn) 总共需N个存储单元 ;根据式(6)、式(7),L(Qn) 、 L( Qnm) 分别需N和NJ个存储单元。再来看N-SMS算法 , 由于变量节点串行更新 , L(Rmn) 只需2J个存储 , 但N - SMS算法每次迭代都要进行min操作 , 对于每个校验式m ,L (Qnm) 仍需2J个 βnm来计算从而L ( Qn) 、 L ( Qnm) 分别仍需N和NJ个存储单元。在N-CMS算法中,L(Rmn) 也只需2J个存储 , 由于N-CMS算法采用了竞争机制 , 每计算出一个 β ′nm, 便用于 γ1和 γ2的更新。所以对于每个校验式m,只需分配1个临时单元用于存储 β ′nm, 从而L ( Qnm) 共需N / 2个单元 ,L(Qn) 需N个存储单元。综上所述 , N - PMS 、 N - SMS和N -CMS所需存储总量分别为2N +NJ 、N +(N +2)J和3N / 2 + 2J 。显而易见 , 相对于N - PMS算法和N - SMS算法 ,N-CMS算法具有极低的存储需求 , 这对于设计成本低廉的译码模块具有重要意义。

4算法仿真与测试

仿真中选取码率1/2的(512,3,6)规则LDPC码通过AWGN信道, 译码分别采用N - PMS算法和N - CMS算法。为了使得信息得到充分的传播,在仿真中令最大迭代译码次数MT= 30 。下面从归一化权重因子的选取、误比特率(Bit Error Rate ,BER)、误帧率(Frame Error Rate , FER ) 、收敛速率和译码平均译码复杂度几个方面来进行对比分析。

为简化讨论,此处利用蒙特卡罗方法来获得N-PMS和N-CMS的归一化权重因子。如图1和图2所示,两者都在 λ=0.8时表现出最佳的性能,因此将 λ=0.8作为最佳归一化权重因子用于之后的仿真。

图3和图4分别对比了PMS、N-PMS、CMS和N-CMS系统的BER和FER性能, 按照是否引入归一化权重因子分为两组,即PMS和N-PMS,CMS和N-CMS。可以看出,不论哪一组归一化算法均比非归一化的算法性能要好得多, 约有0.5~0.7 d B的性能差距。此外,即使都是归一化算法,N-CMS较N-PMS也有0.1~0.2 dB的性能提升。

由图5可知知,CMS所所需需的的平平均均迭迭代代译译码码次数要少于PMS , 类似的, N - CMS所需的平均迭代译码次数也少于N - PMS 。从图6可以得出, N - CMS在中低信噪比时译码复杂度较N-SMS有明显的优势, 但比N-PMS略高; 在高信噪比时N-CMS与N-PMS复杂度接近,而且两者都比N-SMS的复杂度低。

5结论

本文提出了一种按照变量节点更新的归一化串行最小和算法 ———N-CMS。 N-CMS算法采用竞争机制实时更新变量节点对校验节点消息集合中最小的两个值, 它在保持与N-SMS算法相同性能的前提下大幅降低了运算量。相对N-PMS算法而言,N-CMS算法不论是在收敛速度, 还是在译码性能上都更有优势, 其复杂度只有略微增加。最为重要的是N-CMS算法具有极低的存储需求,尤其是在电力线载波通信所需的译码模块的设计中,表现出巨大的实用价值。

摘要：针对译码模块设计成本和功耗的问题,提出了一种LDPC码串行最小和算法。该算法是一种采用权重因子的基于变量节点更新的串行算法,它基于竞争机制来更新变量节点对校验节点消息集合中的最小值。与传统串行算法相比,在不损失性能的前提下,它大幅降低了译码所需的复杂度。另一方面,与并行最小和算法相比,新算法不仅大幅降低了所需存储量,而且性能也有一定的提升,复杂度只有略微增加。

关键词：电力线载波通信,串行最小和算法,低密度奇偶校验码,迭代译码,归一化权重因子

参考文献

[1]DEVELI I,KABALCI Y.Analysis of the use of different decoding schemes in LDPC coded OFDM systems over indoor PLC channel[J].Electronics&Electrical Engineering,2014,20(1):76-80.

[2]BERROU C,GLAVIEUX A,THITIMAJSHIMA P.Near Shannon limit error-correcting coding:turbo codes[C].In ICC93,1993(5):1064-1070.

[3]MACKAY D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Trans.Inform.Theory,1999(45):399-431.

[4]FOSSORIER M P C,MIHALJEVIC M,IMAI H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation[J].IEEE Trans.Commun,1999(47):673-680.

[5]CHEN J,FOSSORIER M P C.Decoding low-density parity check codes with normalized APP-based algorithm[C].Proc.IEEE Global Communications Conference,2001,9(1):1026-1030.

[6]刘原华,王新梅,胡树楷,等.一种改进的卷积LDPC码置信传播译码算法[J].西安电子科技大学学报,2009,36(3):424-428.

最小和算法第5篇

最小二乘方法用于多站测向定位的算法

文中讨论了测向定位中的若干问题,包括双站交会定位及其定位误差分析、三站交会定位、多站交会定位,最后首次尝试将最小二乘方法和递推最小二乘方法用于多站测向定位的算法,对于提高测向定位的`精度和简化运算量有很大的作用,有相当的实用性.

作者：徐济仁薛磊作者单位：电子工程学院,刊名：电波科学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF RADIO SCIENCE年，卷(期)：16(2)分类号：P225.1关键词：双站交会定位多站交会定位最小二乘方法

例谈线段和的最小值问题的解法第6篇

1.如图1，要在街道旁修建一个奶站P，向居民区A、B提供牛奶，奶站P应建在什么地方，才能使从A，B到它的距离之和最短？为什么？

2.如图2，要在街道旁修建一个奶站P，向居民区A、B提供牛奶，奶站P应建在什么地方，才能使从A，B到它的距离之和最短？为什么？

这就是我们所说的几条线段和的最小值问题。今天，我们将结合几个典型的例题，用三个不同的模型，从三个方面谈一谈线段和的最小值问题的基本解题思想，总结切实可行的解题方法，以期帮助初三学生提高复习的效率。

模型一：两定一动型。解题原理：两点之间，线段最短。

说明：在一条直线的同侧有两个定点，在直线上找一个动点P，使点P到另两点的距离之和最短。

例1：如图3，在直角坐标系中，点A的坐标是（2，4），点B的坐标是（6，2），在y轴和x轴上找两点P、Q，使得A，B，P，Q四点组成的四边形周长最小，请画出示意图，并求出P、Q两点的坐标。

思路分析：分别作点A关于Y轴的对称点A′，点B关于X轴的对称点B′，连接A′B′，分别交Y轴于P′，交X轴于点Q′，点P′、Q′即为所求。

模型二：一定两动型。解题原理：直线外一点到直线的所有距离中，垂线段最短。

说明：在一条直线的同侧有一个定点，一个动点，在直线上找一个动点P，使点P到另两点的距离之和最短。

例2：如图4，在锐角三角形ABC中，AB=4，∠CAB=45°，AD平分∠CAB，M、N分别是AD、AB上的动点，试求MN+MB的最小值。

思路分析：在AC上截取AE=AN，连接BE.∵∠BAC的平分线交BC于点D，

∴∠EAM=∠NAM，在△AME与△AMN中，AE=AN∠EAM=∠NAMAM=AM，∴△AME≌△AMN（SAS），

∴ME=MN.∴BM+MN=BM+ME≥BE.∵BM+MN有最小值.当BE是点B到直线AC的距离时，BE⊥AC，又AB=4，∠BAC=45°。

此时，△ABE为等腰直角三角形

∴BE=4，即BE取最小值为4，∴BM+MN的最小值是4.

启示：解决本题的核心环节，是作点B或者点N关于AD的对称点，再找B到直线的最小距离。本题比例1又增加了一定的难度，需要同学们在解题时，适度展开思维，灵活应用。

模型三：三點运动型。解题原理：两条平行间的所有距离中，垂线段最短。

说明：在一条直线的同侧有两个动点，在直线上找一个动点P，使点P到另两点的距离之和最短。

例3：如图5，菱形ABCD的较小内角为60度，菱形的边长为5，点P是对角线AC上的一个动点，点M、N分别是边AB、BC上的动点，则PM+PN的最小值是_______.

思路分析：由菱形的性质可知，菱形关于对角线AC轴对称。作点M关于AC的对称点M′，连接M′N，交AC于点P′，则PM+PN的最小值为P′M+P′N=M′N，要使M′N最小，只有M′N与AD垂直，即PM+PN的最小值为菱形ABCD的高。

启示：在这道变式题里，求PM+PN的最小值，已不是简单的两条线段之和最小，它已升华为两条平行线之间的距离最短的问题，这需要同学们在解题过程中不要机械套用，而应该随机应变，灵活运用，化腐朽为神奇。

通过以上三道典型例题的分析和讲解，我们可以得出线段和的最小值的基本解题思想和解题步骤：

1.求线段和最小值的一般步骤，如下图：

（1）点P所在直线l为对称轴；画出点A的对称点A′；

（2）连接对称点A′与B之间的线段，交直线l于点P，点P即为所求的点，线段A′B的长就是AP+BP的最小值。

2.基本图形：两点一线。

3.基本解法：利用对称性，将“折”转“直”。

4.出题背景变式有：角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。

5.核心解题思路：找点关于线的对称点，和通过轴对称实现“散”变“集”，“折”转“直”。

最后，请同学们用今天所学的知识，试一试你的身手，看你是否真的掌握了用对称法来解决与线段和最小值的问题。

1.已知：如图6，AB是⊙O的直径，AB=4，点C是半圆的三等份点，点D是弧BC的中点，AB上有一动点P，连接PC，PD，则PC+PD的最小值是多少？并画出点P的位置。

最小和算法第7篇

关键词：基因选择,粒子群优化,信息度

0 引言

人类基因组计划将人类对生命机理的认识延伸到分子级别, 越来越多的科学工作者参与到基因组计划的后续研究当中, 由此产生了一系列新兴的研究领域。其中微阵列技术研究已成为当前新兴领域研究的代表, 而微阵列数据研究中基因级别的疾病检测与治疗的基因选择这一研究方向已然成为微阵列数据研究中的热点课题。

基因选择算法的主流研究也经历着不同的阶段, 从早期的基于简单的统计模型的研究到近年来广泛的研究基于复杂的混合的模型的基因选择算法。2001年Xu等对前列腺癌研究中总结出著名的SAGE的标签[1]。2001年Waghray等用SAGE研究正常人和前列腺患者的前列腺微阵列数据并作比较, 发现156个差异表达的基因, 其中在肿瘤组织中88个上调而68个下调[2]。2006年Yuhang等设计了一个称之为Hyk Gene的分类方法, 该方法的主要特点是能够在不损伤准确率的前提下获得最小的包含最大信息的基因集合[3]。2007年Edmundo等提出一种结合模糊逻辑、遗传算法和SVM分类器的基因选择及分类方法。在该方法中先通过模糊逻辑实现冗余基因剔除, 初步选出一个基因子集, 然后应用遗传算法和SVM分类器进行进一步的基因选择[4]。2008年王树林等采用因子分析方法从信息基因子集中抽取因子, 并从信息基因子集中抽取独立分量, 依据这些综合属性采用SVM完成微阵列数据分类[5]。

将最小熵理论用于基因选择这一研究领域。最小熵方法最早是在1945年由比利时科学家普利高津提出, 起初主要用于非平衡热力学的线性解析。这一原理论概括地可以理解为, 对于一个开放的系统, 其在不同的状态之间进行转化着, 这是一个不可逆过程。这个不可逆过程是向着熵减小的方向变化着的, 而当这个系统在不受外界因素作用时, 系统状态将不再变化, 此时系统的状态熵最小。由于该理论的抽象程度较高, 使得该理论的泛化受到一定的限制, 将其应用于工程或科研领域的例子相对较少。如Munirathnam Srikanth和H.K.Kesavan于2000年用信息测度对概率论中函数概率密度分布的拟合[6], 可以认为这是该领域最小熵理论应用的开端, 而国内学者对该方法的研究尚处于起步阶段。

将基因选择过程作为一个个的“态”, 而基因选择的过程就是在不同的“态”之间进行转化。由最小熵理论可得, 当一个基因组包含有最大的分类信息时, 此时对于基因选择过程而言, 选择该基因组的状态可以理解为具有最小熵的一个“态”。而基因选择的整个过程可以理解成寻找到一组基因。相应地, 通过建立评价基因选择过程的“态”的熵的度量, 并基于最小熵理论, 就可以实现基因选择, 且所选择的基因具有很好的可解释性。在最小熵理论中, 有很多的用于评价这种“态”所带有的熵的测度。选择将协方差作为最小熵理论中评价“态”之间转化过程中的信息度, 通过对各个选择出的基因组的协方差进行计算和比较来实现基因选择过程。由于微阵列数据中包含有大量的冗余基因, 使得各种的基因组合数目非常庞大, 故本文选择粒子群优化算法, 并与信息度相结合来实现对最优基因组合的选择。

1 基于协方差的信息测度

基因表达数据分析的主要难点在于选择小的能代表所有特征信息的基因子集。而在基因选择中我们更想知道的是一个小的子集是否带有足够的分类信息, 这也是评价一般应用于基因分类算法是否带有统计学意义上的准确性的基础。这里, 为了完全的利用分类信息, 我们将所选基因组的协方差作为判别该基因组所携带分类信息的信息测度, 这一算法主要受Jessica C[7]所提出的信息度的启发。其理论主要通过比较不同基因表达值在不同表达类型间基于协方差所体现出的表达模式, 且在分析和比较过程中更倾向于研究不同类别间的信息度。由于该方法以统计为基础, 使得这种信息度量同时具有对数据分析的充分性以及稳定性。为方便讨论, 本文只选择白血病[8]和结肠癌[9]这两类微阵列数据集, 并使用基于协方差的信息测度方法来进行评价。假设一个微阵列数据由n个样本以及s个基因组成。在n个样本中有m个来自癌症样本, 其他的n-m个样本来自正常样本。假设选出的基因子集中的基因数由g表示:

式中, 表示的是第k个表达式类别中第j个样本的第i个基因的表达值, i=1, 2, …;j=1, 2, 3…, m或n-m。k表示该样本来自患者还是正常人类别。表示的是第k类中第j个样本对于所选出的基因子集的g个基因的平均表达值:

式中表示癌症患者或者正常人类别中所有基因的表达平均值。表达式下标中的两个点分别表示先对类别中的所有基因的表达平均, 然后对该类别中所有样本的表达值求平均:

下标中的三个点分别表示先对所选出的基因组中的g个基因的表达值做平均, 然后对所有样本取平均, 并对两个类别做评价。对选出的基因组, 基因类表达的协方差可以得到一个包含了不同类别之间分布差异情况的信息度量值 (MMS) , 对于两类数据而言, 表达式如下:

由不同类别间表达值的协方差可以定义出另一个信息度, 该信息度表示还残留在数据中的信息度量, 用RSS表示。

根据最小熵理论可知, 一个包含有最大分类信息基因, 应该表现出具有最大的类内的信息MMS的同时包含最小的类间的残留信息RSS。基因选择过程就是找出MMS和RSS二者之间的差别最大的基因组合, 该组合即包含有统计意义上最大的分类信息。

2 混合的特征基因选取方法

如上述的信息度模型, 如果在一组微阵列数据中包含有清晰的分类信息, 那么, 对于包含有该微阵列数据全部分类信息的基因组一定有最大的MMS以及相对很小的RSS。在涉及到具体微阵列数据分析时, 由于基因数目过多导致不同基因组数目过于庞大, 可将粒子群优化算法与信息度模型相结合, 在由不同的基因组合构成粒子群个体, 将各个基因组的信息度作为粒子群优化进化过程中的适应度函数来完成粒子群优化的移动以及进化过程[10,11]。具体流程如图1所示。基于粒子群的运动和进化规则, 在一定的迭代次数之后, 将粒子群优化中的最好位置个体输出, 也就是完成最优信息度基因组的选择过程。算法具体的步骤如下:

(1) 粒子群初始化。将不同的基因组作为粒子群优化中的粒子个体进行粒子群的初始化, 第i个粒子Xi= (xi1, xi2, …, xi D) 代表随机生成备选的基因组合。

(2) 粒子群的进化, 将粒子群中各个粒子的信息度MMS以及RSS作为粒子群进化中的评价函数。在粒子完成一次位移之后, 计算每个粒子Xi= (xi1, xi2, …, xi D) 的信息度MMS以及RSS, 每个粒子当前的最好位置Pi= (Pi1, Pi2, …, Pi D) 记录着该粒子取得最好信息度的位置, Pg= (Pg1, Pg2, …, Pg D) 记录着所有粒子中具有最好信息度的位置。在每一次迭代以及粒子群完成位移之后, 更新每个粒子所经历过的最好位置Pg= (Pg1, Pg2, …, Pg D) , 并将所有粒子的历史最好位置作为全局最好位置, 所有粒子都根据下式完成位移更新[12,13]。

式中, 下标“j”表示粒子的第j维;“i”表示粒子i;t代表第t代;c1、c2为加速常数;v表示粒子的速度。

(3) 粒子群进化结束, 输出最好全局位置。如果在很多次迭代中各个粒子的历史最好位置不再改变且全局最好位置保持不变, 或者已经达到最大迭代次数, 则粒子群进化结束并输出全局最好位置, 即具有最大信息度的基因组。

(4) 计算具有最大信息度基因组的分类准确率。

3 实验结果

3.1 实验数据集

使用公开的白血病和结肠癌的数据集对本文的算法进行验证, 在白血病数据集中包含了72个不同肿瘤类别个体的基因表达值, 其中包括25个急性髓细胞白血病 (AML) 样本以及47例急性淋巴细胞白血病 (ALL) 。共有7129个基因的表达水平。在结肠癌数据集中, 包含了来自62个个体的微阵列数据, 共包含有2000个基因的表达水平, 在这62个个体中, 其中40个样本来自肿瘤患者, 其余的22个样本来自正常个体的组织。采用4折交叉验证的方法来验证算法的分类准确率, 将所有的样本, 包括各个不同的类别, 平均分为4份, 将其中的1份作为分类器的训练样本, 而将其余的样本作为验证准确率的验证样本集。这种验证方法能非常客观且准确验算法所选出的基因组所能获得的分类准确率, 避免分类过程中由于分类器的不稳定性带来的偏差以及由噪声带来的偏差等等[14]。

3.2 实验结果与讨论

由于整个算法的重点在于讨论某个基因组是否包含有最大的分类信息。而具体而言, 基于上文讨论, 包含有最大分类信息的基因组必然会得到一个较大的信息度MMS, 同时会有一个相对较小的RSS, 即这两者之间的差别最大。在具体实验中, 由于备选基因组的组合数量过于庞大, 以现有计算机处理能力几乎不可能计算出所有的基因组合然后获得具有最大信息度的基因组。故采用粒子群优化算法与信息度相耦合的方法, 将每个基因组合作为粒子群中的一个粒子, 通过粒子群的移动和进化来完成对最优基因组合的搜索过程。验证过程中, 第一步将讨论对于一个微阵列数据集而言, 有多少个基因组成的基因组能包含有一个微阵列数据的最大分类信息, 具体通过在粒子群每次进化过程某一维数基因组所形成的空间进行搜索来实现。在白血病数据集中, 搜索维数从1维到80维的实验结果如图2所示, 最上面子图所表示的是各个不同维数的基因组合在粒子群完成进化之后所获得的最大的MMS的值。相对应地, 图2中间的子图所示是对于从1维到80维数的基因组, 在粒子群完成进化之后对于该维数的基因组所获得的信息度RSS的大小。根据最大熵理论, 包含有最大分类信息的基因组必然得到最大的MMS同时保持RSS相对得小, 即两者之间差别最大。最下一子图所示为相应的选出的基因组的分类准确率, 从分类准确率可以看出, 当所选基因数大于30时, 可以达到很高的分类准确率。结合这三个图进行纵向分析, 同时由最大熵理论可以得到, 当选择的基因组的维数为59时, 信息度MMS曲线达到最大, 而同时信息度RSS相对较小, 因此可以得出这59个基因所组成的基因组可能包含有白血病数据集中最大的分类信息。

同理对于结肠癌数据集, 通过粒子群耦合信息度选择出的从1维至80维基因组的信息度MMS, RSS以及分类准确率如图3所示。与白血病数据集中的分析相同, 当所选基因维数大于25时, 可以得到99%的分类准确率, 但此时该组基因所包含的信息度并未达到最大, 该组基因并不包含有最大的分类信息。而当所选基因数大于65时, 与此同时, 可以获得最高的分类准确率, 同时该组基因组的MMS值最大且RSS值较小, 即该组基因包含的信息度最大。基于最小熵理论我们可以得出这65个基因所组成的基因组包含了该数据集的所有分类信息。

从基因选择的角度来说, 无论59个基因以及62个基因组成的基因组都过于庞大。在基因选择的过程中往往希望找到一个或者几个关键基因, 这几个基因直接与某种癌症的发病相关联。而基于最小熵理论, 对白血病数据集中所选出的59个基因以及结肠癌数据集中选出的62个基因包含了最大的分类信息, 故关键基因可以从这些选出的包含有最大分类信息的基因组中进行进一步的选择。应用粒子群算法耦合信息度的基因选择算法从之前已经选择出基因组中继续选出数目为3到5个的基因组成的小的基因组, 然后验证这些小基因组的分类准确率。

表1列出了在两组数据中获得最高分类准确率的基因组的基因名字以及相应的分类准确率。

在白血病数据集中, 只须{M27878_at U50327_s_at U05237_at}这个三个基因便获得最高的100%的分类准确率。相应的在结肠癌数据集中, {J00231T57619T72175H64489}{T92451T57619T58861H64489}{M87789 T57619 T72175 H64489}这三组由4个基因组成的基因组可以获得最高的96.2%的分类准确率。为了横向地比较提出算法的效果, 表2列出了本文提出算法与近年来一些类似的经典方法在同样两个数据集上分类性能的比较情况。这些经典方法包括有Two-Phase EA/k-NN[15]、SVM[16]、GA-SVM[17]、进化算法[18]、冗余统计法[19]以及PSO-SVM[20]。

表2中, 前面的数字代表最好分类准确率, 括号内的数字表示获得该分类准确率用到的基因数目。相对来说, 对于基因选择算法而言, 能找到最小的基因组合同时获得最高的分类准确率是最终的目的。从表中可以看出, 对于白血病数据集, 本文提出算法只须3个基因便能获得100%准确率, 这与最好的经典SVM算法持平。而对于结肠癌数据集, 本文提出算法在用到最小的4个基因的同时获得了仅次于经典SVM算法的分类准确率。

4 结语

最小和算法第8篇

关键词：精准施药,1.8R-G-B法,骨架提取,最小相切圆,形态学细化

0引言

精准施药技术是实现精准农业的重要部分,有利于减少环境污染、保障人类健康安全。在农业机械精准施药过程中,为了提高施药的精准度,作物行提取是关键,对农业机械自动对行行走起着至关重要的作用［1］。日本东京大学［2］研究者对作物行进行边缘检测,将运用最小二乘法拟合出的导航线应用于精密喷洒系统。马红霞等［3］针对单一作物行采取水平分割图像的方法找到定位点,从而拟合出作物行线。

本文对多行玉米植株图像通过改进的超绿灰度化法、中值滤波及Otsu阈值算法3个步骤使背景与作物行完全分割开来; 运用作物行呈线型的特点,采用5 × 1像素的线型结构元素和3 × 3像素的方形结构元素两者相结合的方法对二值图像进行腐蚀、膨胀运算; 最后运用最小相切圆与形态学相结合的方法进行中央玉米作物行提取,对不同区域的玉米作物行进行了实验分析。结果表明: 该算法具有较好的适应性和准确度。

1玉米作物行图像采集

1. 1颜色模型选取

农田图像的获取是图像处理的第一步。实验以北方玉米作物行为研究对象,采用维视数字图像技术有限公司生产的型号为MV - VD030SM /SC的USB2. 0接口的CCD工业数字相机及艾菲特光电技术有限公司生产的型号为AFT - 0641MP的工业镜头对田间自然环境下的玉米作物行图像进行采集。相机拍摄的高度距地面约为1. 8m,输出的图像是8位RGB彩色图像。由于RGB模型颜色信息获取比较直接,无需转换,所以本算法选择RGB彩色图像进行直接处理。

1. 2实验开发平台

本研究用于处理玉米作物行图像的计算机环境设置为Intel( R) Core( TM) i3,3. 1GHz,2G内存。以WI- IN7系统下Microsoft Visual C + + 6. 0为实验平台,基于MFC应用程序框架对作物行骨架提取算法进行研究和开发。

2玉米作物行图像分割

2. 1图像灰度化

采集到的玉米作物行图像包含了许多彩色信息, 但在对图像进行处理和分析时并不需要这些信息,而把彩色图像转换为灰度图像更有利于后续作物行的提取。本文对常用过的绿特征灰度化法［4］和改进的灰度化算法分别进行了对比,如图1所示。采用普通的超绿灰度化算法［5］虽然可以区分出作物行,但行间仍夹杂着许多噪声。本文对2G - R - B算法进行了改进,改进后的具体灰度化算法为

从改进后的算法处理的图像可以看出: 使用本文改进的算法玉米作物行更为突出,且行间噪声有明显的减少; 处理同一幅图片,改进后的算法处理时间为2ms,改进前为5. 6ms,运算效率明显有了提高。

2. 2滤波除噪

由于灰度化后的图像上仍有噪声存在,影响对目标的处理,所以本文选取3 × 3数组窗口对其进行中值滤波,并采用冒泡法对数组进行排序后返回数组元素的中值。经2次滤波后图像中的噪声基本去除,满足了后续对作物行处理的需求,如图2所示。

2. 3灰度二值化

为了将背景和作物行完全分割开来,进一步提取行信息,需要进行二值化处理。本文将大于设定阈值的像素值设为255; 相反,将小于它的像素值设为0。由于行目标与背景有较大的差别,可以采用设定阈值和Otsu算法［6］对其二值化处理,处理后的图像如图3所示。

经比较发现: 当阈值设定为185时,两种方法处理效果差不多,对后期处理没影响。Otsu算法不需要人为设定阈值,是一种自适应阈值确定的方法,计算方法简单、适应性强且稳定,所以本文采用Otsu算法对图像进行二值化处理。

3作物行提取

3. 1改进的形态学去噪

玉米作物行图像经二值化处理后,背景与行信息很清晰地分割开来,但选取的玉米植株叶片较大且相互交叉。影响作物行中心骨架的提取,为了能更准确地提取出作物行骨架,依据作物行本身为线型的特点,在保证不改变和消除作物行有用信息的前提下, 本文采用5 × 1线型结构元素和3 × 3方形结构元素两者相结合的形态学方法对其进行腐蚀、膨胀操作。特别针对同行玉米植株间有间断的地方,运用5 × 1线型结构元素可以很好地连接间断区域,保持了连通性; 针对较大叶片玉米植株运用5 × 1线型结构元素进行腐蚀处理可以有效地避免大叶片对行中心线骨架的提取造成的误差［7］。与此同时,运用3 × 3方形结构元素可以填补图像中的孔洞和孤立点,弥合细小缝隙。通过实验,本文先对二值化后的图像进行5 × 1的垂直方向2次腐蚀,再进行3 × 3的8次膨胀运算, 然后进行5 × 1水平方向2次膨胀,最后再进行3 × 3的8次腐蚀操作,得到的作物行轮廓如图4所示。从图4中可以看出: 本文采用的5 × 1和3 × 3结构元素相结合的方法,很好地连通了中央玉米植株间有间断的地方,为后续准确提取中央作物行做了准备工作。

3. 2中央作物行骨架提取

3. 2. 1最小相切圆原理

农业机械导航在玉米精准施药时要对准中间两行［8］。导航的路径是一种线性结构信息,所以本文在检测玉米作物行时,首先应对作物行轮廓进行细化处理,也就是所谓的骨架化。骨架提取的算法有多种, 如最大圆盘法、数字距离变换法和拓扑细化法是常用的骨架提取法。最大圆盘法所提取的骨架不仅连通性差,而且通常较粗,无法满足单一像素宽度的需求; 距离变换法是利用距离场中的局部极值点的集合作为骨架,虽然在准确度上有明显优势,但难以保证连通性; 拓扑细化法虽然能保持提取骨架的连通性及拓扑结构性,但提取的骨架位置不精确。

针对以上问题,本文提出一种最小相切圆原理与形态学相结合的方法来提取中央作物行骨架,图5为最小相切圆的原理模型图。假设a、b、c、d 4条线为玉米作物行,以作物行( 即a、b、c、d 4条线) 底部中心为基准找与作物行相切的所有圆,则圆O1即为要找的最小相切圆,切点M、N就是所要找的点,也即是中央作物行上的点。

3. 2. 2提取步骤

由于精准施药的农业机械是不断行走的,进行精准施药时只需对准中间两作物行即可,则可以运用上述提出的最小相切圆原理进行中央作物行的骨架提取。其步骤如下:

1) 首先,运用形态学细化法提取出所有作物行的骨架,如图6( a) 所示;

2) 然后,从图像底部中心向作物行两边自下向上进行扫描,找出能与作物行两边相切的最小圆;

3) 记下所有与最小圆相切的切点。与此同时,腐蚀掉其余不满足条件的像素点,那么这些满足条件的像素点的集合就组成了中央作物行的骨架。提取结果如图6( b) 所示。

3. 3中央作物行直线拟合

中央作物行的直线拟合方法有多种,而随机Hough变换具有计算简便、运算速度快等优点,因此采取常用的随机Hough变换算法把主干骨架拟合成直线,如图7所示。

3. 4其他区域提取结果

为了验证该算法同样对其他区域玉米作物行也有效,选取了160cm × 135cm的玉米作物行图像进行了相同的处理,处理的结果如图8所示。

4实验偏差分析

由于相机安装在精准施药机械上,当机械进行作业行走时,相机拍摄到的图像底部是呈垂直拍摄的, 所以选取中央作物行直线的底端中点与相机的位置偏差来分析作物行检测的精准度更能说明问题。

针对两幅不同区域内的玉米作物行图像,分别进行了偏差分析,结果如表1所示。

5结论

1) 运用改进的超绿算法对玉米作物行图像进行了灰度化处理,大大减小了行间噪声,为后续形态学去噪减少了不必要的麻烦。

2) 运用5 × 1线型结构元素和3 × 3方形结构元素相结合的方法对二值化图像进行腐蚀、膨胀运算,得到作物行的大概轮廓,并对其进行细化处理。

3) 运用最小相切圆和形态学相结合的方法提取中央作物行骨架,并对其进行直线拟合; 运用实际地理偏差与理论地理偏差的差值来判断作物行检测的准确度。

多最小分类支持度算法研究第9篇

1 关联规则算法

设I={i1,i2,…,im}是所有项目的集合,D是所有事务的集合,X为项目的集合,如果X属于T,则称事务T包含X,关联规则可表示为,其中。

支持度S表示事务出现的频率。其中,|T(X∪Y)|是数据集中包含的(X∪Y)事务数;|T|表示数据集中的事务总数。

置信度C表示的强度:。其中,|T(X)|表示数据集中包含X的事务数。

关联规则的挖掘就是发现具有用户指定的最小支持度minS和最小置信度minC的关联规则,即。为实现这一目的,首先,求出D中满足最小支持度的所有项目集;然后检测满足minS的项目集是否满足minC,并生成相应的关联规则。

2 Apriori算法

Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。Apriori中心思想是首先通过对事务数据库进行扫描,找出支持度不小于最小支持度的所有项目,即频繁1-项集。接下来的工作是循环的,每次循环分2步进行:

(1)连接:对频繁k-项集中的项进行连接。首先,找出频繁1-项集,以L1表示。L1用来寻找L2,即频繁2-项集的集合。L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现。

(2)剪枝:对连接后的项目集进行筛选,删除那些子集不是频繁集的项目集,得出候选(k+1)-项集。即对数据库进行扫描,计算候选项的支持度,从候选集中删除支持度小于最小支持度的候选项,进而得出频繁(k+1)-项集。循环的终止条件是频繁k-项集为空。

3 多最小分类支持度算法

3.1 多最小分类支持度算法思想

设T为一个包含几个事务的事务数据集,每个事务都标有一个分类yi(i=1,2,3,…),设I为T中所有项目的集合,Y为所有分类标识(目标项目),且有,一个多最小分类关联规则的关系:X→yi(i=1,2,3,…),其中且yi(i=1,2,3,…,且i∈Y)。多最小支持度算法的目标就是生产完整满足指定要求的由多最小支持度限制的关联规则集合。

3.2 多最小分类支持度挖掘算法

多最小支持度挖掘可以直接一步生成,关键是找出支持度高于所属类的最小支持度阈值规则项,表示为:(condset,y)。其中,condset是一个项目集合,称为条件集;yi(i=1,2,3,…,且i∈Y)是一个类标。T中包含条件集condest的事务数量,称为条件集支持计数,表示为condsetCount。T中包含条件集condset且类标为yi(i=1,2,3,…)的事务数量,称为规则支持计数,表示为rulesupCount。每个规则项代表一条规则:condest→y。规则的支持度为(rulesupCount/n)。其中n为T中的事务总数量,置信度为(rulesupCount/condsetCount)。

多最小支持度算法(设多最小分类支持度的1-前件为CAR,k-前件为CARk)为:

3.3 多最小分类支持度算法分析

多最小分类支持度算法也是基于Apriori算法进行改进的一种新算法,该算法通过对数据集进行分类,并为不同的类标指定不同的最小支持度阈值来对数据集进行挖掘,从而避免了只有一个最小支持度时漏掉稀有项目规则的问题,可以挖掘出完整的规则项,使算法在实际应用中显得更加灵活。在多最小分类支持度算法中,假如有n个类标,所有事务可划分为n类,若需要挖掘的项目为m,则最多有2m个项集,设每一次对数据库的扫描时间为t,在串行情况下,即Apriori算法中扫描时间为2m×t,时间复杂度为O(2m)。在并行情况下,即多最小分类支持度算法中,每类的运行时间为2m×t/n,时间复杂度为O(2m),只有该算法在挖掘关联规则时出现最不理想的运行情况时,两种算法才需要相同的运行时间。

4 结语

本文针对Apriori算法的效率比较低的问题,提出了一个新的算法,即多最小分类支持度算法,该算法可以减少候选集中的候选项及减少扫描数据库的次数,从而大大提高挖掘的效率。该算法具有较好的时间效率。

参考文献

[1]Mehmed Kantardzic.数据挖掘:概念、模型、方法和算法[M].北京:清华大学出版社,2003.

[2]史忠值.知识发现[M].北京:清华大学出版社,2002.

[3]邢化玲,刘思伟,高社生,等.不完备信息系统的数据挖掘方法研究[J].计算机应用研究,2008,25(1):90-92.

[4]孙云,李舟军,陈火旺.孤立点检测算法及其在数据流挖掘中的可用性[J].计算机科学,2007,34(10):200-203.

[5]苏云辉,张莹,白清源,等.基于访问兴趣度的用户事务聚类方法[J].广西师范大学学报:自然科学版,2007,25(4): 150-152.

[6]吴振光.一个改进的关联规则的频繁项目集数据挖掘算法[J].计算机科学,2007,34(9):145-147.

[7]席景科,张辰,谢红侠.基于数据仓库的Web日志挖掘技术研究[J].计算机工程与技术,2007,28(24):5890-5892.

[8]李锦泽,叶晓俊.基于链表的元规则制导的多维量化关联规则挖掘算法研究[J].四川大学学报:工程科学版,2007,39 (5):124-128.

[9]李明华,刘全,刘忠,等.数据挖掘中聚类算法的新发展[J].计算机应用研究,2008,25(1):13-17.

[10]刘先锋,李钒.基于半结构化数据模型的频繁模式挖掘研究[J].计算机工程与应用,2007,43(36):173-176.

基于节点编码的最小生成树算法第10篇

关键词：遗传算法,最小生成树,节点编码,Prufer数

1 概述

树是图论中的一个重要概念, 也是图论中结构简单, 用途广泛的一种连通图。在许多工程问题中, 如通讯网络设计、电力、煤气和排水管道系统设计等, 通常都可以转化为求最小生成树问题。

对于一个给定的带权无向连通图G来说, 应用图论中的传统算法, 如:Kruskal算法、prim算法、Sollin算法、Dijkstra算法等求解最小生成树。但采用这类算法一般只能得到唯一的一棵最小生成树, 而在实际应用中, 不同形式的最小生成树代表不同的设计方案, 有时权值次小的生成树, 也可能是实际问题的一个较好的设计方案。如果仅选其中一个, 可能会丢失或忽略更优的方案。因此, 在实际应用中希望能够同时获得若干个权最小或次小的生成树作为待选方案。

遗传算法求最小树的常见编码方法有边编码、节点编码。采用二进制的边编码方式表示最小生成树, 其生成树的概率较低。因此, 提出基于节点整数编码来求最小生成树。

2 基于节点编码的遗传算法

图论计算中的一个经典定理是Cayley定理, 即在一个有n个顶点的完全图中, 有nn-2个不同的树。这些树和n-2个数字的所有排列的集合是一一对应关系。这表明可以仅用n-2个数字的排列来唯一地表达一棵树, 其中每个数字都是1到n之间的整数。这个排列通常称为Prufer数。基于这种现象, 可以很容易地构造如下节点编码方法 (得到一个Prufer数) :

2.1 令节点i是标定树T上的标号最小的叶子节点。

2.2 令唯一与i相连的节点j作为编码的第一个数字。编码顺序从左到右。

2.3 删除节点i及i到j的边, 于是得到一棵n-1个节点的树。重复上述运算, 直到只剩下一条边。于是得到一个Prufer数或一个n-2个1和n之间的数字的排列。

3 算法设计

3.1 编码设计

设某一无向图中共有N个顶点、N (N-1) /2条边, 对图中的节点进行编号。以图中的节点编号为编码变量, 各个编码变量的取值范围是1~N之间的整数, 则以N-2个整数为Prufer数可以唯一表示一棵树。N-2个Prufer数是就是树中的枝节点, 其大小在1~N之间;而不在Prufer数中的整数是树的叶子节点。例如, 图1 (a) 所示的无向图最多可以有7!条边, 图1 (b) 是该图的一个生成树, 由7条边组成。生成该树的Prufer数是{5 2 5 2 6 2}。

3.2 遗传算子的设计

3.2.1 交叉算子Pc

本文采用单点交叉方式, 首先将群体中的M个个体以随机的方式组成[M/2]对配对个体组, 然后在每对个体组中随机设置一个交叉点, 在该点相互交换两个配对个体的基因值。

单点交叉的示意图如下:

交叉算子的的设计和实现与所研究的问题密切相关, 一般要求它既不要太多地破坏个体编码串中表示优良性状的优良模式, 又要能够有效地产出出一些较好的新个体模式。

3.2.2 变异算子Pm

本文采用基本位变异操作, 具体思路是:对个体编码串中以变异概率Pm随机指定的某一位或某几位基因座上的基因值作变异运算。具体执行过程是:

a.对个体的每一个基因座, 依变异概率Pm指定其为变异点。

b.对每一个指定的变异点, 对其基因值用[1, N]范围内的一个随机数去替换。

基本位变异的示意图如下所示:

3.3 算法的相关参数及流程图

最小生成树的算法流程图如下:

4 实例应用

如下图所示的一个网络图, 图中连线上的数据表示各边的权值。应用单亲遗传算法求该网络图的最小值。

解:该网络图的权矩阵如下:

运行可知, 当Pc=0.6, Pt=0.1, Pm=0.05;Popsize=100;Maxgen=20时, 可得最小树长87。此时Prufer=[1 8 6 7 1 7]。对应的树枝是:2-1, 3-8, 4-6, 5-7, 6-1, 1-7, 7-8。

5 结论

采用基于节点编码的遗传算法求最小生成树可用于不同类型的最小树问题研究, 能够在较短的时间内以较高的概率获得一批最小树或次最小树, 为进行实际工程的方案评价和决策提供更多的选择依据。

参考文献

[1]周明, 孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 1998, 12.

求所有最小点成本最短路径算法第11篇

最短路径(SP)问题一直是运筹学、计算机科学、交通运输等领域的研究热点。很多实际问题都可以转化为网络中的最短路径问题,如道路交通网络中的出行路线选取问题、计算机网络中的路由选择问题等。针对网络的最短路径问题研究具有重要的理论和现实意义。早期专家学者研究的算法有Dijkstra算法[1]、Bellman算法[2]、Floyd算法等,现阶段对最短路径算法的研究呈现以下几个特点:1并行化,如文献[4]-[6]等;2将遗传算法、神经网络、启发式算法等引入最短路径算法设计中,如文献 [7]-[9]等;3对各种约束条件下的最短路径算法进行研究,如文献[10]-[13]等;4研究最短路径算法的各种优化实现,如文献[14]。

早期文献[10]对点带成本约束的最短路径算法进行了研究,文献[10]首先证明了点带约束成本SP问题是一个NP完全问题,然后用动态规划法给出一个时间复杂度为O(Cmn)的伪多项式时间算法。对最小点成本最短路径问题,文献[10]把主要目标(路径长度最短)的最优解作为次要目标(点成本最小)的约束条件进行求解,需要两次调用Dijkstra算法求最短路径,并且需要构造网络G′ = (V,A′,L′),造成一些不必要的时间和空间开销。本文对Dijkstra算法进行了改进,使其适合于求解最小点成本最短路问题,然后只调用一次修改后的Dijkstra算法,完成对最小点成本最短路问题的求解,在求解过程中不需要构造新的网络,本质上是一个贪心算法。

1问题描述

定义1:图G = (V,A,L)称为点带成本带权图,给它的每条边(vi、vj)∈A赋一个非负参数li,j,称作长度;给它的每一vi∈V赋一个正参数ci,称作点成本。点带成本带权图G中一个特殊点s称为源点。

定义2:设P是点带成本带权图中一条路径,记P = v1v2…vrvr+1,定义P的长度为L(P)=l1,2+l2,3+ … + lr,r+1。定义P上的点成本为C(P)=a1+a2+ … +ar。

定义3:点带约束成本的SP问题:求点带成本带权图中给定的两顶点间一条路径P,使得P在满足C(P)≤C的前提下,路径长度最短.这里C是一个正有理数。

定义4:最小点成本最短路径(MCSP)问题是从源点到其余各个顶点的所有最短路中求点成本最小的最短路径,即求:min{C(P):P是v1→vn的最短路径}。

定义5:设G=(V,A,L)是点带成本带权图,SV且源点s∈S ,任意vi∈V -S,从s到vi除了vi以外其它顶点都属于S的路径,称为从s到vi的受S限制路径。把从s到vi的受S限制的所有路径中长度最短且在满足长度最短的条件下,点成本最小的路径称为s到vi的受S限制最小点成本最短路径。记s到vi的受S限制点成本最小最短路径的长度和点成本构成的二元组为 (Li,Ci)i, 简称LC二元组,其中Li为路径长度,Ci为点成本。

定义6:(Li,Ci)i<(Lj,Cj)j,当且仅当Li<Lj或者Li=Lj并且Ci<Cj。当Li=Lj并且Ci=Cj时,记 (Li, Ci)i= (Lj,Cj)j。当 (Li,Ci)i<(Lj,Cj)j或 (Li,Ci)i= (Lj,Cj)j时,记 (Li,Ci)i≤(Lj,Cj)j。

显然集合 {(Li,Ci)i|vi∈V-S}上的“≤ ”关系具有自反性、反对称性和传递性。又由于任意两个实数都可以比较大小,所以集合 {(Li,Ci)i|vi∈V-S}和它上面的关系“≤”构成一个全序关系,总有最小元存在。

2算法基本思想

设P=sv2,…,vk,…,vL是图G的一条最小点成本最短路径,则P′ =v1v2,…,vk是图G中从s到顶点vk的最小点成本最短路径,否则设P'=sv′2v′3…vk是从s到vk的最小点成本最短路。把路径P中顶点vk前面的部分用P'替换会得到一条可能比P更短或者与P长度相同、但点成本更小的路径,这些都与P是从v1到vL的最小点成本最短路径矛盾。这说明最小点成本最短路问题具有最优子结构性质,可以使用动态规划法或贪心法进行求解。

又由于 {(Li,Ci)i|vi∈V-S}是有限全序集,最小元总是存在的,所以可以采用如下贪心策略:设置一个集合S,初始时S中仅含有源s,然后每次找到V-S中最小的 (Li,Ci)i,将vi添加到S中,同时对数组 (Lj,Cj)j按如下方式修改:(Lj,Cj)j= min{(Lj,Cj)j,(Lj,Cj)j+ (li,j, aj)},如果 (vi,vj)∈ E ,这一过程直至S中包含所有V中顶点为止。

同时若有 (Lj,Cj)j= (Lj,Cj)j+ (li,j,aj),其中 (vi,vj)∈ E ,则vi一定会出现在从s到vj的最小点成本最短路径上。可以利用LC数组的这一特性构造出所有点成本最小最短路径,这是文献[10]未给出的。

3算法描述

算法1:

功能:计算LC数组。

算法2:

功能:构造出所有的最小点成本最短路径。

算法正确性证明:

定理1:每次选择一个顶点放入S中并执行完更新操作后,得到新的、正确的LC二元组。

证明:在算法初始化时,得到的LC数组显然是正确的。放入S的顶点vi,除了vi的邻接点外,其余顶点不会经过vi。vi的邻接点可能会经过vi,但已经对其LC进行了更新。所以,每次选择一个顶点放入S中并且执行完更新操作后,会得到新的、正确的LC二元组。

定理2:算法1能正确求出从源点到各个顶点的LC二元组。

证明:对放入S中的定点次序k进行归纳:

当k=1时,首先放入S的源点s,(Ls,Cs)s的Ls是从s到s最短路径长度,Cs是从s到s的长度最短的最小点权。

设当k≤h时,前h个放入S中的顶点,其相应的LC二元组分别是从s到该顶点的最短路径长度,及从s到该顶点的所有最短路径中的最小点权。

现在证明第h+1个放入S中的顶点vi,(Li,Ci)i的Li是从s到vi最短路径长度,Ci是从s到vi的长度最短的最小点权。设P是从s到vi长度最短、且在长度最短的前提下点权最小的路径。根据贪心选择策略,P必经过S外至少一个顶点才能到达vi,不妨将P从s出发,第一个经过S外的顶点为vx。结合定理1,这时必然有 (Lx,Cx)x<(Li,Ci)i。这与贪心选择策略矛盾。

算法1的正确性可以保障算法2是正确的。

4算法性能分析和实例

算法1:有一个二重循环,每重循环最多循环|V|次, 在整个算法运行过程中最多访问每条边一次,所以其时间复杂度为O(|V|2+|E|)。设最小点成本最短路径的数目为w,则算法2的时间复杂度为O(w|V|)。算法1的空间消耗主要在邻接表存储和LC数组存储,其空间复杂度为O(|V|+|E|)。算法2的空间消耗主要在邻接表、 LC数组、栈的存储和递归调用栈上,递归调用栈的深度最多为|V|,所以其空间复杂度为O(|V|+|E|)。

图1为一个点带成本带权图,用算法1和算法2求出从源点s到其余各个顶点的点成本最短路径,如表1。

5结语

本文在文献[10]的基础上对点带成本问题进行了研究 ,结合问题的特点给出了求所有点带成本最短路径算法。在点带成本最短路径问题中,把所有点的成本都设为1,则点带成本路径问题就变成了顶点数最少的路径问题。虽然本文给出了一个求解点带成本问题的多项式时间算法,但如果图中定点数过多,其二阶的时间消耗仍然是难以接受的。所以,下一步的研究方向是点带权最短路径问题的并行化算法和线性近似算法。

摘要：对点带成本的最短路径问题进行了研究。根据点带成本最短路径问题特点,对Dijkstra算法进行修改后给出一个时间复杂度为O(|V|2|2+|E|)|)、空间复杂度为O(|V|+|+|E|E|)|)的算法,并在此基础上充分利用问题的特点,给出一个时间复杂度为O(w|V|V|)|)、空间复杂度为O(|V|+|+|E|E|)|)、构造所有点带成本最短路径的算法。

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【最小和算法】相关文章：

混合遗传算法和支持向量机的股票预测模型09-12

《新预算法》下省属高校预算编制的新要求和应对策略09-12

算法与算法思想05-13

国外新颖优化算法——排超联赛算法09-12

国外新型智能优化算法——海鸥优化算法01-28

国外新型智能优化算法——口孵鱼算法09-11