求马步图Hamilton圈的最优算法

本文对骑士巡游问题进行了研究 ,提出了求棋盘马步图的 Hamilton圈的“分治 -回溯 -合并”算法 ,其时间复杂度是 O(n2 )。分析表明该算法是求棋盘马步图一条 Hamilton圈的最优算法 ,对VLSI的布线问题具有一定的应用价值     

一种基于链暗示技术的Min-CVCB问题的精确算法

随着VLSI（超大规模集成电路）技术的发展,关于可重构阵列二分图的受约束最小点覆盖（Min-CVCB）问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O（（k\\-u+k\\-l）|G|+1.26\\+\\{k\\-u+k\\-l\\}）的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用“链暗示”技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O（（k\\-u+k\\-l）|G|+1.1892\\+\\{k\\-u+k\\-l\\}）,极大地改进了目前的最好结果.     

一种对图像中给定图形的定位方法

作为模式识别的前序,需要在一幅图像中找出一个基本图形,给出这个图形的位置,再进行进一步的识别.文中提出的算法以直接匹配为基础,改进了算法的执行效率.以二值图像中的图形的定位为实验对搜索定位算法进行了讨论.试验显示出该文算法有较高的执行速度.     

一种对图像中给定图形的定位方法

作为模式识别的前序，需要在一幅图像中找出一个基本图形，给出这个图形的位置，再进行进一步的识别。文中提出的算法以直接匹配为基础，改进了算法的执行效率。以二值图像中的图形的定位为实验对搜索定位算法进行了讨论。试验显示出该文算法有较高的执行速度。     

求解Web集群文档分布的混沌搜索算法

提出Web集群文档分布方案,用M/G/1/K PS排队模型对服务器进行建模,将文档分布问题转化为0-1整数规划问题,然后求解该规划问题。针对该类0-1整数规划问题,给出一种基于混沌搜索的求解算法,该算法让多个独立的混沌变量在其各自的轨道中搜索,使得对应生成的0-1矩阵能遍历任意一种可能的分布,从而能搜索到全局最优解。设计一种基于贪婪思想的文档分布算法。测试表明,混沌搜索算法能找到全局最优解,优于传统的贪婪算法。     

A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements

We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of searching in a finite sequence of points from the Euclidean space for the subsequence with the greatest number of terms such that the quadratic spread of the elements of this subsequence with respect to its unknown centroid does not exceed a given percentage of the quadratic spread of elements of the input sequence with respect to its centroid. It is shown that the problem is strongly NP-hard. A polynomial-time approximation algorithm is proposed. This algorithm either establishes that the problem has no solution or finds a 1/2-approximate solution if the length M^* of the optimal subsequence is even, or it yields a \(\frac{1}{2}\left(\begin{array}{c}1-\frac{1}{M^*}\\ \end{array}\right)\)-approximate solution if M* is odd. The time complexity of the algorithm is O(N³(N²+q)), where N is the number of points in the input sequence and q is the space dimension. The results of numerical simulation that demonstrate the effectiveness of the algorithm are presented.     

一种改进的电子商务系统商品搜索算法

传统的电子商务系统中，使用关键字匹配的算法实现商品搜索的功能，只能得到包含顾客输入关键字的商品。文章以网上书店的实现为例，通过对商品搜索算法的改进，引入模糊系统和文本匹配算法，使得在顾客搜索商品时，不仅显示精确匹配的商品，而且叮以提供与其要求相似的商品，供其参考。这对于商家增加交易机会、发掘潜在顾客、提高个性化服务水平都有很大的促进作用。     

一种确定运动目标特征点的算法

介绍了基于物体边缘点确定特征点的算法，避免了在整个目标图像范围内寻找特征点，算法简单，速度快。仿真结果表明、该算法是有效的。     

创建者序列重建问题MFL模型的改进算法

创建者序列重建问题即根据后代基因信息推断其祖先基因信息,最大片断长度问题(the Maximum Fragment Length problem,MFL)模型是求解该问题的有效模型.Roli提出一种求解MFL模型的构造性启发式算法,该算法通过0、1取值比例来确定创建者序列的取值,且通过引入随机信息来解决0、1等比例的情形,导致求解方案的不确定性.针对该问题,提出一种有效的改进算法I-R-Heric,该算法充分利用重组体和创建者矩阵的列向0、1取值比例的相关性等启发式信息,对随机取值问题做出有效限定.实验结果显示,I-R-Heric算法能快速有效地求解MFL问题,并能获得较改进前算法更少的断点个数和更长的片段平均长度.此外,在重组体序列规模较大的情况下,I-R-Heric仍具有较高的执行效率,有很好的实用价值.     

注入攻击序列搜索算法对安全协议的验证研究

通过对D-Y攻击者模型研究,可知注入攻击是攻击者实现其攻击目标的必要手段。对注入攻击序列的性质进行分析,提出了一种在安全协议会话状态空间中搜索注入攻击序列的算法,基于该算法可实现一种新的安全协议验证方法。利用该方法实现了NS公钥协议的验证。实验表明该方法可以实现对安全协议的自动化验证,降低了验证的复杂度,并能给出安全协议漏洞的具体攻击方法。     

An Algorithm for the Exact Numerical Integration of a Special Class of Functions

The classical Gaussian quadrature rules yield very inaccurate results when they are used for the integration of functions of the form f(x)=P(x,\cos(cx+d))\exp(-a^{2}x^{2}+bx) over the infinite interval (-\infty, \infty) , where a\gt 0, b, c, d are real numbers and P is a polynomial. In this paper we propose a new algorithm that computes this type of integrals without error in the machine precision. The algorithm can also be used for the multiple integrals. We give some numerical examples to compare the results obtained by the new algorithm and those obtained by some other methods including the classical Gauss-Hermite integration rules.     

A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI

Haplotypes play an important role in genetic association studies of complex diseases. Recently, computational techniques helping to determine human haplotypes were studied extensively. Given the genotype and the aligned single nucleotide polymorphism (SNP) fragments of an individual, Minimum Error Correction with Genotype Information (MEC/GI) is an important computational model to infer a pair of haplotypes compatible with the genotype by correcting minimum number of SNPs in the given SNP fragments. The MEC/GI problem has been proven NP-hard, for which there is no practical exact algorithm. Despite the rapid advances in molecular biological techniques, modern high-throughput sequencers cannot sequence directly a DNA fragment that contains more than 1200 nucleotide bases. With low SNP density, current available data reveal that the number k of SNP sites that a DNA fragment covers is usually smaller than 10. Based on the above fact, we develop a new dynamic programming algorithm with running time O(mk2 ^k +mlog m+mk), where m is the number of fragments. Since k is small in real biological applications, the algorithm is practical and efficient.     

精确求解进港飞机调度双目标优化问题的epsilon约束算法

随着机场客流的持续增长,航班延误日益严重。同时,对于机场最重要的跑道资源而言,积雪结冰等会造成 飞机 打滑,从而出现事故。对于机场管理者,周期性地维护跑道至关重要,以防雨雪天气出现飞机打滑事故。该研究主要针对跑道上的 航班调度问题,考虑恶劣天气环境下跑道的周期性维护(如周期性喷洒除雪盐等)。为了在保证航班的服务质量的同时提高机场跑道的使用效率,文中以最小化航班总延误和跑道使用时间为优化的双目标。首先,提出该双目标优化问题混合整数规划模型;其次,为了精确求解出Pareto前沿,开发出epsilon约束算法;最后,给出算例来说明模型和算法的可行性。通过数学规划理论建模并开发精确求解算法,为机场资源优化研究提供参考。     

一种改进的基于键聚类的P2P网络搜索算法

P2P搜索问题已成为目前学术界的研究热点,Key clustering算法将路由空间分成HUB和AUT两层,从全局角度进行有序搜索,借鉴Small-world领域的研究成果,在路由表中以一定概率插入连接远距离节点的快捷连接,以缩短平均路径长度.仿真试验表明,引入快捷连接的Key clustering算法具有良好的搜索能力、扩展性和容错能力.     

一般贝叶斯网络分类器及其学习算法

贝叶斯网络（BN）应用于分类应用时对目标变量预测有直接贡献的局部模型称作一般贝叶斯网络分类器（GBNC）。推导GBNC的传统途径是先学习完整的BN,而现有推导BN结构的算法限制了应用规模。为了避免学习全局BN,提出仅执行局部搜索的结构学习算法IPC-GBNC,它以目标变量节点为中心执行广度优先搜索,且将搜索深度控制在不超过2层。理论上可证明算法IPC-GBNC是正确的,而基于仿真和真实数据的实验进一步验证了其学习效果和效率的优势：（1）可输出和执行全局搜索的PC算法相同甚至更高质量的结构;（2）较全局搜索消耗少得多的计算量;（3）同时实现了降维（类似决策树学习算法）。相比于绝大多数经典分类器,GBNC的分类性能相当,但兼具直观、紧凑表达和强大推理的能力（且支持不完整观测值）。     

背包问题的一种自适应算法

背包问题是经典的NP-hard组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极重要的应用．基于求解背包问题著名的二表算法和动态二表算法,利用归并原理和4个非平衡的子表,提出一种求解该问题的自适应算法,算法可根据计算资源和问题实例规模的大小,允许使用O(2^n/2-ε)的存储空间(1≤ε≤n／4),在O(ε(2^n/2))的时间内求解背包问题．对算法性能的理论分析和数值实验结果表明,自适应算法可显著扩大背包实例的求解规模,从时间和空间上改进背包问题现有算法的性能．     

一种改进的集群动态负载均衡算法

在集群系统的研究中,负载均衡算法是一个重要的方向,因为它关系到多台服务器在整合成一个集群系统后能否很好地相互协作,以更好地完成用户交予的任务。为实现上述目的,本文在分析已有的负载均衡算法基础上,提出一种改进的能够实时收集服务器负载指标,进而动态地计算出服务器在分配用户连接中的权重的方法。测试结果表明,该方法能够有效地防止服务器倾斜,达到良好的负载均衡效果。     

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups

In this paper we show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm is an extension of our earlier method for extraspecial groups in Ivanyos et al. (Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science (STACS), vol. 4393, pp. 586–597, 2007), but it has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a p-group of exponent p and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.