构造对角Ramsey图的DNA算法设计*

Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。     

用自同构循环图计算Ramsey数R(3,q)的下界*

确定经典Ramsey数的下界是组合数学中非常困难的问题,因而人们常用各种方法计算它的界。发现一种新的方法, 即自同构循环图的方法,计算得到三个经典Ramsey数的新下界：R(3,30)≥188,R(3,33)≥217,R(3,34)≥225。     

完全图K97的边染色与4个Ramsey数的新下界

用构造性方法研究完全图K97的边的各种染色,得到4个经典Ramsey数的新下界：R（3,3,8）≥98,R（3,4,6）≥98,R（3,5,5）≥98,R（3,18）≥98。     

Ramsey数R（3,28）新下界的并行计算*

寻找有效的参数集,构造素数阶循环图,用并行算法获得二色Ramsey数R（3,q）的新下界:R（3,28）≥164。     

基于最大Code码的极大完全子图算法

本文通过引入极大code码，提出了一种寻找图的极大完全子图的算法FMCSG，该算法用邻接矩阵表示图。在寻找极大完全子图时根据得到的code码及时剪掉非极大code码的子矩阵，从而减少对矩阵的遍历次数，提高了算法的效率。     

求解Ramsey数下界的模拟退火算法

对于图G_1、G_2,2色广义Ramsey数R(G_1,G_2)是指最小正整数P,使得每一个p阶的图G,或者G包含G_1,或者G的补图包含G_2。用改进的模拟退火算法求解得到了R(W_m,K_n),R(B_m,K_n),R(F_m,K_n),类型的一些Ramsey数的下界。     

基于有向层次图的Web服务自动组合方法

为解决多输入/输出的Web服务自动组合问题,提出了基于有向层次图的Web服务自动组合方法,主要步骤如下：1）根据用户请求的输入/输出参数集生成有向层次图;2）在有向层次图中构造完全规约图;3）在完全规约图中计算每一顶点的所有可达路径;4）为用户请求选择最优路径,并转化为Web服务组合序列。该方法能够求得最短步数内的所有Web服务组合序列,根据Web服务的服务质量(QoS)获得最优的组合序列,从而满足多输入/输出的用户请求。与基于图的Web服务组合方法相比,减少了搜索空间,适用于大规模的Web服务库。     

三个Ramsey数R(3,q)的新下界*

通过构造三个循环图,得到了三个经典Ramsey数R(3,q)的新下界:R(3,34)≥223,R(3,36)≥237,R(3,38)≥254。     

经典Ramsey数DNA计算模型(Ⅱ):基于位序列的DNA计算模型

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一．对于经典Ramsey数,至今只有9个Ramsey数得到解决．按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任．研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解．全文共分两篇,该文属第二篇,在首篇工作的基础上,建立了所谓的经典Ramsey数位序列DNA计算模型,文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论,并给出了使用该模型求解经典Ramsey数详细的方法与步骤．     

有限域与Ramsey数Rn(k)的下界

研究有限域GF(p')上的循环图的结构性质，给出一些图的团数的解析表达式，并给出计算Rarnsey数Rn(k)下界的一种算法，得到一个Ramsey数的新下界：R3(8)≥4111。     

Drawing maps with advice

We study the problem of the amount of information required to draw a complete or a partial map of a graph with unlabeled nodes and arbitrarily labeled ports. A mobile agent, starting at any node of an unknown connected graph and walking in it, has to accomplish one of the following tasks: draw a complete map of the graph, i.e., find an isomorphic copy of it including port numbering, or draw a partial map, i.e., a spanning tree, again with port numbering. The agent executes a deterministic algorithm and cannot mark visited nodes in any way. None of these map drawing tasks is feasible without any additional information, unless the graph is a tree. Hence we investigate the minimum number of bits of information (minimum size of advice  ) that has to be given to the agent to complete these tasks. It turns out that this minimum size of advice depends on the number n$n$ of nodes or the number m$m$ of edges of the graph, and on a crucial parameter μ$\mu$, called the multiplicity of the graph, which measures the number of nodes that have an identical view of the graph.     

蚁群神经网络在旅行商问题中的应用

在求解旅行商问题(TSP)时,首先引入交叉策略进行预处理,将具体的地图抽象为常见的无向完全图,即把TSP抽象为求无向完全图的一条Hamilton回路;然后用蚁群算法与人工神经网络相结合的方法来求解.实验结果表明了该方法的可行性和高效性.     

经典Ramsey数DNA计算模型(Ⅰ):位序列计算模型

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一．对于经典Ramsey数,至今只有9个Ramsey数得到解决．按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任．研究表明,DNA计算在求解困难的NP一完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解．全文共分两篇,该文属首篇,建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型,其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序．文中重点对该模型的机理与使用方法进行了分析研究．     

A new construction technique of a triangle-free 3-colored K16’s

In this paper, we propose a new coloring technique of the edges of the complete graph on 16 vertices, K₁₆, with three different colors, without producing any monochromatic triangle. This method is totally different from those proposed by [R.E. Greenwood, A.M. Gleason, Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics 7 (1955) 1–7; J.G. Kalbfleish, R.G. Stanton, On the maximal triangle-free edge-chromatic graphs in three colors, Journal of Combinatorial Theory 5 (1968) 9–20; C. Laywine, L.P. Mayberry, A simple construction giving the two non-isomorphic triangle free 3-colored K₁₆’s, Journal of Combinatorial Theory Series B (1988) 120–124; B. Benhamou, Étude des Symétries et de la Cardinalité en Calcul Propoaitionel: Application aux Algorithmes Syntaxiques, Ph.D. Thesis, University of Aix-Marseilles I, France, 1993] which prove that the classical multicolor Ramsey number R(3, 3, 3) is 17. This number is the only non-trivial tricolor Ramsey number known till now in spite of more than fifty years of extensive research on Ramsey numbers [S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics DS1.Revision 11 (2006) 1–60]. We show also how we can convert the Ramsey-graph 3-coloring problem into a satisfiability instance having 2160 clauses of 3-literals each and 360 variables (i.e., a 3-SAT instance).     

基于连续－离散MRF图模型的鲁棒多机器人地图融合方法

针对多机器人同步定位与建图（MSLAM）中感知偏差会产生高度相关且互一致的异常回环,进而导致定位与地图变形等问题,提出了基于马尔可夫随机场（MRF）的通用连续－离散图模型．其中,连续图对标准位姿图（pose graph）进行建模;离散图通过对异常值相关关系的显式建模,建立剔除模型．在此基础上,进一步利用凸松弛方法,将连续－离散图代表的非凸且NP（非确定性多项式）完全的组合优化问题转化为半正定规划（SDP）问题,方便利用现有凸优化工具进行求解．仿真和实测数据实验表明,本文方法提高了位姿图对感知偏差带来异常外点的鲁棒性,且结果不依赖于位姿初始值的好坏,在异常值占比为50%的情况下,剔除率仍可达99.8%,地图融合精度优于现有主流动态协方差缩放（DCS）方法和两两一致测量集（PCM）方法．     

ARM嵌入式系统GUI开发研究

随着计算机技术与通信技术的发展,为了方便非专业人员使用各种嵌入式设备,各式各样的人机交互界面应运而生。在ARM为核心的嵌入式系统上进行了图形界面的开发。在设计中利用基本图形的绘制和窗口、汉字、图片等基本图形相互之间的交互组合,建立图形界面,并进一步对Windows界面进行了模拟。     

Salient object detection method using random graph

In this paper, a bottom-up salient object detection method is proposed by modeling image as a random graph. The proposed method starts with portioning input image into superpixels and extracting color and spatial features for each superpixel. Then, a complete graph is constructed by employing superpixels as nodes. A high edge weight is assigned into a pair of superpixels if they have high similarity. Next, a random walk prior on nodes is assumed to generate the probability distribution on edges. On the other hand, a complete directed graph is created that each edge weight represents the probability for transmitting random walker from current node to next node. By considering a threshold and eliminating edges with higher probability than the threshold, a random graph is created to model input image. The inbound degree vector of a random graph is computed to determine the most salient nodes (regions). Finally, a propagation technique is used to form saliency map. Experimental results on two challenging datasets: MSRA10K and SED2 demonstrate the efficiency of the proposed unsupervised RG method in comparison with the state-of-the-art unsupervised methods.     

全局孤立性和局部同质性图表示的随机游走显著目标检测算法

目前的显著性检测算法主要依赖像素间的相互对比,缺乏对显著目标自身特性的分析理解. 依据显著目标是显眼、紧凑和完整的思路,提出一种基于目标全局孤立性和局部同质性的 随机游走显著目标检测算法,将视觉显著性检测公式化为马尔科夫随机游走问题. 首先将输入图像进行分块,根据像素块之间颜色特征和方向特征的相似性确定边的权重, 从而构建图模型;然后通过全连通图搜索提取全局特性,突出全局较孤立的区域; 同时通过k-regular图搜索提取局部特性,增强局部较均匀的区域;最后将全局特性和局部 特性相结合得到显著图,进而确定感兴趣区域位置. 实验结果表明,相比于其他两种具有代表性的算法,所提方法检测结果更加准确、合理, 证明该算法切实可行.