点赋权图上固定顶点的树划分问题

考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.     

固定顶点的树划分问题

 考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问题的最优多项式算法;②证明了固定k个顶点的最小最大树划分问题是NP-难的,并利用①的结果给出了固定k个顶点的最小最大树划分问题的一个k-近似算法.     

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

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

A new approach based on PSO algorithm to find good computational encoding sequences

Computational encoding DNA sequence design is one of the most important steps in molecular computation. A lot of research work has been done to design reliable sequence library. A revised method based on the support system developed by Tanaka et al. is proposed here with different criteria to construct fitness function. Then we adapt particle swarm optimization (PSO) algorithm to our encoding problem. By using the new algorithm, a set of sequences with good quality is generated. The result also shows that our PSO-based approach could rapidly converge at the minimum level for an output of the simulation model. The celerity of the algorithm fits our requirements.     

A new approach based on PSO algorithm to find good computational encoding sequences

Computational encoding DNA sequence design is one of the most important steps in molecular computation. A lot of research work has been done to design reliable sequence library. A revised method based on the support system developed by Tanaka et al. is proposed here with different criteria to construct fitness function. Then we adapt particle swarm optimization (PSO) algorithm to our encoding problem. By using the new algorithm, a set of sequences with good quality is generated. The result also shows that our PSO-based approach could rapidly converge at the minimum level for an output of the simulation model. The celerity of the algorithm fits our requirements.     

基于因子图的Turbo码译码

Turbo码和LDPC码都可以实现接近Shannon理论极限的性能，Turbo码由于成员RSC码所固有的移位寄存器特性使得其编码较为容易实现，而对于接近Shannon容量的LDPC码，则需要大量的矩阵乘法运算才能完成信息的编码，电路实现较为复杂，另一方面，采用和积算法的LDPC码的译码过程则比采用BCJR算法（及其简化形式）的Turbo译码更加容易实现，且计算复杂度更低，将Turbo编码与LDPC码的译码相结合，对Turbo采用基于其因子图表示的和积译码算法进行译码，可以在很大程度上降低Turbo码的译码复杂度，并对交织器的设计及成员码的选择有一定的指导作用，仿真结果证明了该方案的有效性。     

用遗传算法解决博弈问题

解决博弈问题的传统算法——搜索树法所无法克服的对搜索深度的限制.以五子棋为例,提出了用遗传算法代替搜索树法解决博弈问题的基本方案,并对适应度函数的设计作了一些有益地探索,给出了设计适应度函数应满足的必要条件.实验表明,用遗传算法所设计的对弈程序优于搜索树法.     

一种新的二维细分图形变形算法

给出了一种新的二维细分图形变形算法。该算法将曲线细分算法和2D图形的变形算法结合起来,并把2D图形的变形升级到3D空间内处理。通过计算并连接对应特征点,建立空间三角面片,从而可以直观地反映初末图形特征点之间的对应关系。通过判断3D三角面片是否相交,易于推断出变形中有无自交和萎缩现象。试验结果反映出该算法变形效果自然,是一种新的有效的2D图形的变形算法。     

精馏分离序列综合邻域结构的研究

为了有效解决精馏分离序列优化综合问题,研究邻域(超级)结构是成功实现寻优算法的前提。由于精馏分离序列与二叉树之间具有同构性,在数据结构上精馏分离序列可以抽象为二叉树,进而采用图论方法对其进行研究。本文运用组合数学理论深入研究了精馏分离序列综合问题．简明分析了有序剖分问题的计算复杂性;通过二叉树相邻切分点变换机制,实现了对精馏分离序列的随机搜索;提炼出后序遍历相邻变换的等价规则,从而构造出高效演化邻域结构。     

A new algorithm for degree-constrained minimum spanning tree based on the reduction technique

The degree-constrained minimum spanning tree （DCMST） is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been preprocessed by reduction algorithm.     

A new algorithm for degree-constrained minimum spanning tree based on the reduction technique

The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been pre-processed by reduction algorithm.     

求解满瓶颈Steiner树

首先对Steiner树,瓶颈Steiner树研究现状加以介绍,指出满瓶颈Steiner树就是在已知图中找一颗树S,使给定的点集在S中的点都为叶子,且最大的边权值最小,然后给出满瓶颈Steiner树的定义,利用分解,转化,组合的思想,给出求解满瓶颈Steiner树问题的一个多项式算法,证明算法正确性,说明该算法的时间复杂性,最后给出相应的数值例子,说明算法正确性.     

广义树网络中的多端割

给定一个边赋权图和k个顶点(称为终端)的集合,多端割问题是要找到一个最小 权的边集,该边集使得每一个终端与其他所有的终端分离.对于一般图来说,当k为不小于3的常数时,这一问题是NP-难解的.对于广义树网络给出了这一问题的一个多项式时间精确算法.     

一类树问题的快速并行算法

本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

基于遗传优化的WSNs多源单汇路由算法

针对无线传感器网络中的多源单汇路由问题,综合考虑无线传感器网络中链路带宽、延迟和路径节点最小剩余能量三种度量,建立了多源单汇路由问题的系统模型,将其转化为求解多约束最小Steiner树问题,已知该问题是NP难的问题,给出了基于遗传优化的求解算法,采用基于备选路径集的整数序列编码表示一棵生成树,设计相应的交叉和变异算子,以及对非法染色体进行修复的机制,最后在遗传算法的计算过程中选择合理的适应度函数,找到一棵满足多约束的能耗趋于最小且状态稳定Steiner树.理论分析和数值试验结果表明所提出的遗传求解算法收敛速度快、可靠性高,为无线传感器网络中的多源单汇路由提供了一种新的有效途径.     

最小生成树的又一种生成法

提出一种关于最小生成树的生成法, 此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的 2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则, 保留此边,再寻找所剩余的权最大的边, 作类似的处理,直到在原网络中剩下的边为顶点数减 1 为止, 由此即得最小生成树.与传统的 Prim 算法及 Kruskal 算法相比较, 此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树.     

寻求多边形链顶点凸壳的算法

提出一种计算简单多边形链顶点凸壳的算法，基本思想是分段计算，在每段的计算中，先分4种不同情况计算出边链L1，然后利用一种技巧将L1上的部分顶点排列成顶点角递增序列，构成边链L2，最后对L2进行倒查，删去非凸壳顶点，剩下的点即凸壳顶点，该算法不仅易于实现，而且其时间复杂性是线性的。     

BWC着色问题的一种启发式算法研究

无向图的BWC着色问题是给定两个正整数b和w,判断是否存在这样的着色方案:对b个顶点着黑色,对w个顶点着白色,其它顶点不着色,着黑色顶点集合与着白色顶点集合之间没有任何边相连。BWC的最优化问题,是找出一种最优化着色方案,使得与所有黑色顶点不相连接的着白色顶点数最大。该问题被证明是NP-完全问题。提出了一种基于禁忌表和局部搜索机制的混合启发式算法(BTLSBWC),通过对部分网络图进行测试,结果达到了现有文献计算出的最好值。     

面向异质可扩展标记语言文档的近似查询算法

提出了一种面向异质可扩展标记语言（XML）文档的近似查询算法（TPQR）．利用模式重写策略，通过对XML模式之间语义相似度及节点映射关系的求解，将原始查询树改写为多种XML模式下的重写查询树，从而解决了XML数据的多样性带来的查询语义缺失问题．将经变异操作序列得到的变异查询树精确地嵌入在XML数据树之中，即可将XML近似查询问题转变为多棵变异查询树的精确查询问题．在汽车外形智能化设计的实验中比较了TPQR算法和静态有序选择算法，结果表明，在查准率、查全率上，前者比后者分别提高了5％～10％和10%～30%．