一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

模幂运算的一个递归算法

模幂算法广泛应用于公开密钥加密技术。在分析已有模幂算法基础上,提出模幂算法的递归实现,省去了模幂算法中指数的二进制化过程已经对指数的扫描过程,简化了算法。     

免疫进化模糊聚类算法在边缘检测中的应用

针对图像处理中的模糊边缘检测问题,提出一种免疫进化模糊聚类算法.该算法在传统遗传算法全局随机搜索的基础上,借鉴了生物免疫机制中抗体的多样性保持策略,改善了遗传算法的群体多样性,具有更好的全局搜索能力.实验结果表明,该算法不仅具有很强的模糊边缘和微细边缘检测能力,而且可以减弱基于遗传算法的模糊聚类算法在遗传后期的波动现象.     

一类基于冒泡排序的改进算法的分析与比较

排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且还直接影响着计算机的工作效率．目前排序领域许多最简单的算法都是基于冒泡排序算法，该文对这些算法的基本原理进行了介绍和分析，并对它们的算法性能进行了比较．     

一种求单源单汇点无环图最短路径的新算法

用Ｄｉｊｋｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ２）．笔者提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）（其中ｎ是图中顶点数，ｅ是边数），且两种算法的空间复杂性基本相同。     

订单编组问题的一类特殊模型的有效算法

工业生产中常遇到按大批量的订单要求加工其所需的产品问题;而把订单要求的一些相同或相似产品合并成批进行批量生产是提高生产效率的一种手段.要考虑的问题是如何分解合并订单使得总的批数达到最大.证明每批的订单总数量均为常数λ的订单合并问题的复杂性,讨论一类特殊的订单合并编组问题并设计其有效算法.     

改进的基于拓扑分析的Steiner树近似算法

针对Berman近似算法k为3情况下的求解思想进行了改进。在使用Fibonacci堆求解出相应点对间最短距离的基础上，通过构建Voronoi域求出元组子树的耗费，并分析了Steiner树的网络拓扑结构以去除无用元组，从而简化拓扑，降低总体时间复杂度。在实验结果中，每个实例的过滤因子均大于0．9，有的甚至高达0．999，这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉，同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效。     

一种新型快速排序算法的设计与实现

本给出了一种具有比传统快速排序算法性能更高的排序方法,该方法既不需要关键字之间的比较,也不需要记录的移动,全给出了该算法的描述,时间/空间复杂度分析和实验比较数据,实验表明,该算法特别适合于大数据量大记录的排序工作。     

Immune Genetic Algorithm for Optimal Design

A computing model employing the immune and genetic algorithm (IGA) for the optimization of part design is presented. This model operates on a population of points in search space simultaneously, not on just one point. It uses the objective function itself, not derivative or any other additional information and guarantees the fast convergence toward the global optimum. This method avoids some weak points in genetic algorithm, such as inefficient to some local searching problems and its convergence is too early. Based on this model, an optimal design support system (IGBODS) is developed. IGBODS has been used in practice and the result shows that this model has great advantage than traditional one and promises good application in optimal design.     

寻找进化树中限长最大密集度路径的一种新算法

针对进化树中的限长最大密集度路径的求解问题提出一种更优的算法。该算法能以伪多项式时间O(wmaxnL)在节点数目为n,且每个节点携带值-权重向量(βv,γv)的进化树中找到一条长度至少为L的路径P,其密集度为最大且满足wmin≤∑v∈Pγv≤wmax.     

混沌免疫模糊聚类算法在图像边缘检测中的应用

针对图像处理中的模糊边缘检测问题,提出一种混沌免疫模糊聚类算法.该算法把混沌变量加载于免疫算法的变量群体中,利用混沌搜索的特点对群体进行微小扰动并逐步调整扰动幅度,明显改善了免疫算法的群体多样性.实验结果表明,该算法不仅具有很强的模糊边缘和微细边缘检测能力,而且可以提高基于人工免疫进化算法的模糊聚类算法的搜索效率.     

Vandermonde矩阵求逆的并行算法及其复杂度

分析Ｖａｎｄｅｒｍｏｎｄｅ矩阵的一种求逆递推式,利用卷积技术研究递推式求解的并行计算方法,给出了并行算法的实现方案,该算法的时间复杂度为Ｏ（ｌｏｇ２ｎ＾２）。     

算法性能分析技术研究

文章论述了算法性能分析的基本理论,分析了一个典型的算法分析实例,提出了几种用于算法分析的技术,解决了一大类算法性能分析的问题。     

采用进化算法优化向量量化

把进化策略引入到矢量量化设计中,提出了一种选择优良后代码书矢量的判据和方法,在使用LBG算法进行聚类的前提下,利用所选择出来的后代矢量调整各个区域的子误差,从而进一步改善期望误差,以获得全局最优码书,实验结果证明,此方法能克服局部最优,改善码书矢量。     

一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位,这个问题的最直接解法是先将序列排序,从而能得到第K个元素,最少需O(nlogn)次比较,即时间复杂度为O(nlogn)．比较好的方法是采用分治策略解决该同题,但其最坏时间复杂度为O(n^2),平均时间复杂度为O(2n)．本文提出一种Byte解决第K个元素问题的算法,该算法的平均时间复杂度为O(n n／255),优于以前对该问题的求解方法,而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集．     

一种快速单模式准确匹配算法

引入连续跳跃查找文本的思想,提出了一种新的单模式精确匹配算法,其最优条件下的时间复杂度为O[n/(m 1)],新算法的平均时间复杂度分析表明其具有优越的查找性能,对比实验结果显示,新算法的性能优于目前所见的同类算法,特别是在模式较短的情况下,优势更为明显,这一特点非常适合于自然语言文本的检索。     

进化算法时间复杂度估算的一般流程

进化算法的时间复杂度分析是当前进化计算领域研究的热点难题。通过总结最新进化算法理论研究,介绍了进化算法时间复杂度分析方法,并讨论了分析关键之处:距离函数的确定方法。最后,给出了进化算法时间复杂度分析的一般流程,且以分析范例演示了方法的执行过程。     

一种判定树同构的BULT算法

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.     

工件带到达时间和服务器的平行机排序问题复杂性和启发式算法

研究带到达时间和单服务器的平行机排序问题，工件在加工之前均有一定的安装时间，且所有安装时间均由单服务器来完成．证明在只有两台平行机的情况下，带到达时间和单服务器的平行机排序问题是强NP-困难的，对于有m台平行机的情况，给出一种改进的启发式算法，并证明该算法的紧界为2．