TSP邻近算法在Euclid平面上的性能比分析

旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界,本文就该方法在欧几里得平面上给出了性能比的一个对数下界。     

关于旅行商问题的若干启发式算法的性能比分析

旅行商问题的增量最小插入法、最近插入法、最近加入法的性能比已经被证明有一个上界2,本文在欧几里德平面上给出了这些方法性能比接近于2的例子。另外,我们证明了凸包选边插入法的性能比有一个关于点数的对数函数上界。     

关于满Steiner树问题的一个近似算法

满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.     

具有准备时间的流水作业时间表问题启发式算法与最坏性能比分析

本文研究具有准备时间的流水作业时间表问题，给了一个简单的启发式算法，证明了一个简单的启发式算法的最坏性能比是m 1/2(其中m是机器的台数)，且关于上界是紧的，特别当m=2时，该启发式算法的最坏性能比是3／2，此结果要好于Potts在1985年所给出的算法。     

最小费用箱子覆盖问题及其算法

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.     

旅行推销员问题凸包方法的性能比分析

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n／2,同时给出了凸包随意插入算法的性能比可以接近n／2的例子。另外,对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。     

最小顶点覆盖问题的一个近似算法

最小顶点覆盖是图论中的一个重要概念，它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法，与现有算法相比具有更优的性能比。     

相等的双目录分割问题及其随机算法

研究了相等的双目录分割问题,给出了此问题的随机算法．通过分析算法的性能,得到算法的近似性能比为0．6378．在回答Jon Kleinberg于1998年提出的一个公开问题方面取得了一定进展．     

带运输时间和单自动机的流水作业排序

本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。     

平行三阶段流水作业问题的近似算法

研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间。当m是定值时,该问题是NP困难;当m2时,问题是强NP困难。将问题分解成3种情形,情形1给出了7/3-1/(3m)的近似比;情形2给出了一个3的近似比;情形3给出了近似比为23/6-1/(3m)。结合3种情形,最终给出了性能比为23/6-1/(3m)的算法。     

一种简单的变步长自适应α—LMS滤波算法

提出了一种简单的变步长α-LMS算法(vα-LMS),并给出了它的设计方法。导出了描述α-LMS算法收敛过程的动态方程,并据此讨论了α-LMS算法的算法性能。与vα-NLMS算法相比,Vα-LMS算法的优点是简单易行、计算量小,但它对输入信噪比的稳健性(RObustncss)却劣于Vα—NLMS算法。Vα-LMS算法的性能将优于Dα-LMS算法。计算机模拟结果与理论分析结果吻合较好.     

网络化控制系统的RM调度优化研究

减少网络堵塞是提高网络化控制系统性能的有效的方法.提出了一种基于RM调度优化算法的研究方法,通过对网络化控制系统中的调度优化算法的分析,网络利用率明显好于未被调度优化的系统.结果表明,合理的调度优化算法能提高控制系统的网络利用率,同时改善了控制系统的动态性能.     

一种基于聚类算法的机会网络路由算法

在传统的历史路径算法的基础上,提出一种基于聚类算法的历史路径机会网络路由算法(RACA算法).该算法使用无监督学习中的k-means++算法对节点进行编码,并使用编码的方式更新历史路径算法,具有缓存空间占用低、节点搜索速度快和在拓扑结构多变的环境的适应性强等特点.实验结果表明:RACA算法在多个方面有着较好的表现,特别是在传输成功率和开销比率方面有较好的表现; 出色的网络性能表现使得RACA算法能够在资源有限的场景和网络环境变化较大的场景使用,例如车载网络环境.     

一种改进减小OFDM系统峰均比的PTS算法

介绍了降低OFDM系统PAPR的PTS算法,提出了将PTS算法进行限幅处理的一种方法。通过仿真,表明算法在保持原算法优点的基础上,有效降低了OFDM信号PAPR值,并对系统性能影响不大。     

基于EMD的心电信号压缩算法

针对生物医学信号特别是心电信号(ECG)的特点和数据压缩需求,提出一种基于经验模态分解(EMD)方法的ECG信号压缩算法.所提算法计算简单,无需预先或后处理.以MIT-BIH标准数据库的心律失常数据作为实验数据,通过压缩比(CR)、均方根百分差异(PRD)、归一化均方根百分差异(PRDN)、均方根(RMS)、信噪比(SNR)、质量评分(QS)6个评价参数分析所提算法性能,并与基于小波分解的压缩算法进行比较.实验结果表明,所提算法具有较好的压缩比与保真度,证明了该算法的有效性.     

LBG与SOFM应用于矢量量化的比较研究

在介绍矢量量化以及LBG算法和SOFM算法的基础上,通过实验对比了LBG算法和SOFM算法在应用于图象矢量量化压缩过程时,码书大小、码字大小以及初始码书生成方式等因素对图像压缩性能的影响,得到了相关结论:固定码字矢量维数,码书越大,压缩比越小,重建图像质量越好;固定码书,码字矢量维数越小,编码性能越好;LBG算法对初始码书敏感,而SOFM算法由于所具备的自适应特性对初始码书不敏感。论文最后提供了一些改进思路,为改进传统矢量量化算法及设计新的矢量量化算法以提供了参考。     

Canny特征在基于内容的图像检索中的应用

 在基于内容的图像检索中,枪支一类图像的检索有其自身难点.将Canny边缘检测算法应用于图像检索中,以待检图像的Canny特征作为检索特征,提出了一种结合矩阵相似度理论的基于内容的图像检索算法.并以手枪图像的检索为例,对算法进行了实验测试.实验结果表明,该图像检索算法具有较高的查准率、查全率和较低的误检率.     

基于LDPC码校验节点度的分类修正最小和算法

为了减小低密度奇偶校验(low-density parity-check,LDPC)码的译码算法复杂度,提高译码性能,该文针对致信传播(belief propagation,BP)译码算法及其简化算法的分析,提出了一种基于校验节点度的分类修正最小和译码算法。该算法将最小和译码算法中校验节点输入外信息绝对值的最小值和次小值分类,并根据该节点的度计算与BP算法的偏移量,分别选择不同的阈值和修正因子对外信息进行补偿。仿真结果表明,该算法在高信噪比区域的译码性能高于BP算法,并且计算复杂度大大低于BP算法,是一种适用于各种校验节点度分布,而且是能较好兼顾性能与实现复杂度的译码算法。     

自适应干扰对消的一种改进正交化算法

分析了传统的正交化算法在干噪比较低中，干扰对消效果佳的原因。将特征子空间分解技术与正交化算法相结合，提出了一种修正的正交化算法。仿真结果表明，所提出的算法极大地改善了低干噪比的干扰对消性能。     

几种矩阵乘并行算法的对比分析

描述了DNS、Cannon、Fox、Systolic矩阵乘并行算法的原理,并对其时间复杂度进行了理论分析。通过对并行算法的各项性能参数的对比分析,得到的结论是DNS算法的时间复杂度最好,但加速比、效率和成本不是最优的。Cannon算法和Fox算法的算法思想类似,但是Cannon算法比Fox算法在数据播送上的花费少,因此整体性能较好。Systolic算法是基于流水线技术的并行矩阵乘算法,有较好的综合性能。