最省刻度尺设计的组合差集递推算法

在长度为n(n≥2为正整数)的直尺上最少刻多少个刻度就能度量1到n的所有长度,这便是至今未解决的最省刻度尺问题。阐明了最省刻度尺与极小优美图之间的关系,给出了计算最省刻度尺的所有最省刻度值的组合差集递推算法,得到长度为3~40的最省刻度尺的所有最省刻度值,同时,结合图论模型,给出了长度为41~82的最省刻度尺的最省刻度值。

基于倒排索引的正则路径查询算法

对于图数据上的正则路径查询(regular path query, RPQ)问题,其使用正则表达式定义图中两个节点之间的约束。针对现有的RPQ在图上遍历匹配方法效率低下这一问题,提出一种基于倒排索引的RPQ算法,在图上构建标签的倒排索引,匹配过程中快速检索标签的相应倒排列表。设计的IRPQ算法将查询转化为面向倒排列表的查询计划树,经过优化以减少冗余列表合并操作。在真实数据集上进行了实验,其结果表明,IRPQ及其优化算法相比现有方法显著提高了查询性能。

Improved Approximation of Layout Problems on Random Graphs

Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.

串并有向图的判定算法及应用实例

串并有向图常作为单机排序问题研究中的约束条件,针对目前并未有一个确切算法判定任意一个有向图是否为串并有向图的问题,提出了串并有向图的判定算法H。算法H利用数学中的递归法,对有向图进行逐层递归分解,对分解结果进行分析判定该有向图是否为串并有向图。结果表明:该问题能在多项式内可解,属于组合优化中的P问题。算法H普遍适用于任意有向图,解决了串并有向图的判定问题。

基于加权无向图的永磁球形步进电机运动控制

提出了一种三自由度永磁球形步进电机的控制方法。首先简单介绍了该永磁球形步进电机定子与转子的结构,然后针对其结构特点及运动原理,提出根据距离相等的永磁体对和铁心线圈对的排列组合,建立一个包含位于球形步进电机转子某一点上物体的所有可能的运动轨迹点的加权无向图,根据所给定的物体的运动轨迹,采用图中路径搜索算法,最终确定永磁球形步进电机的通电线圈对,达到控制球形步进电机,使物体沿着期望的运动轨迹运动的目的。

基于快速递推模糊2-划分熵图割的红外图像分割

考虑现有图割算法没有充分考虑红外图像的模糊特性,分割精度和运行效率低的缺点,提出了基于快速递推模糊2-划分熵图割的红外图像分割算法以实现复杂背景下红外图像的自动高效分割。该方法利用图像感兴趣区域的最大模糊熵信息设计图割能量函数的似然能,基于局部最大模糊2-划分熵值迭代检测出包含图像最大信息的感兴趣区域来确保提取目标信息的完整性。为了提高最大模糊熵寻优的效率,引入时间复杂度为O(n2)的递推算法,将模糊熵计算转化为递推过程,并保存所有递推的熵函数值用于后续的穷举寻优。针对确定的感兴趣区域,利用该区域最大模糊2-划分时隶属度函数分布设置图割能量函数的似然能,从而充分考虑图像的模糊特性。对分割结果与几种常用的算法进行了视觉比较及运行时间,错分率,F指标的量化分析。结果表明:该算法分割精度F值高达95%,运行时间较其他常用算法至少缩短了72%,基本满足自动红外图像分割对精度、效率和鲁棒性的要求。

基于Cayley图的六度环绕网络研究

六度网络是一类平面图网络结构,将平面以等边三角形的形式进行分割,包括六度网孔网络和六度环绕网络.六度网孔网络不是规则网络,其边缘节点与内部节点的度不相等.通过对六度网孔网络的边缘节点建立环绕边就形成了规则的六度环绕网络,每个节点的度为6.但是由于环绕边的存在,使得六度环绕网络的通信算法实现复杂,网络直径也非常难于计算.六度环绕网络被证实是一种Cayley图模型,具有良好的对称性.但是基于Cayley图的六度环绕网络的最优路由算法、广播算法还没有得到,该网络模型的具体直径值也是未解问题.针对基于Cayley图的六度环绕网络模型,文中给出了一种简单的最优路由算法和一种基于陪集图理论的广播算法,并给出该网络模型的网络直径确切值.

基于XML和XSD的通用GUI生成器研究

为了满足应用软件对图形用户界面(graph user interface,GUI)快速变更的需求,提出了基于深度递归和广度递归思想的持久化和解析算法,设计了基于XML和XSD(XML schema description language)的GUI生成器.该生成器包括设计器和解析器,支持层次化的界面样式语义以及组、联合、枚举等数据模型语义.最后,给出了应用示例,使用Java和C#语言分别解析了采用该生成器定制的某网络入侵检测系统的路由器对象,同时可以验证用户输入数据是否符合约束语义.

生成有向装配连接图有向割集的递归收缩算法

为解决有向装配图有向割集的求解,给出一个生成有向装配连接图有向割集的高效算法,该算法优先考虑检查有向割集两个子图间边的方向。算法首先利用边收缩图的概念,递归生成有向装配连接图的具有一个连通子图的一部分有向断集,接着通过判断另一个子图是否连通,从这些有向断集的集合中筛选出全部的有向割集。理论分析和实验分析均表明,该改进算法可行且高效,时间复杂度明显低于已有算法。

逐点循环递归法求哈密顿回路

给出了求解任意图的所有哈密顿回路逐点循环递归算法,用于处理复杂的旅行商问题,证明了一个图是否是哈密顿图。在算法中,用结点标号数组存储一个回路,无向图的正向表存储初始图。

采用遗传算法的手绘草图关系模板生成方法

草图理解包含两个方面:草图图形识别和草图布局分析,但目前的研究大部分集中于一些特殊图形的草图识别上。实际上,草图布局分析对草图信息内容的发现,尤其是在获取其构思方面更为重要。本文为事实草图图形的布局分析提出了一种基于遗传算法的模板生成方法,在定义和描绘了布局模式的基础上,本方法能找出有潜在语义的图形对象间的模式。实验表明:遗传算法能够有效找出明显或是潜在的模式,并能很减轻手工标注模式的负担。

一种改进蚁群算法在排课中的应用研究

为了合理安排课表、有效地利用教学资源、提高教学质量。根据排课问题的约束条件,将排课问题转化为二分图匹配问题,从而提出一种优化的蚁群算法解决排课问题。实践结果表明,这种优化的蚁群算法提高了排课质量和效率。

分层自治的Multicast地址管理和连接控制

Multicast动态地址管理和连接控制是多点会话中的重要问题．基于分层自治结构，文章提出了Multicast地址分配管理机制、主从结构连接管理体系和一种简单的多点连接建立算法，简述了它们的工作过程，并通过模拟实验比较了3种地址分配方式，即集中管理方式、分布方式（由Eleftheri-adis提出）与分层自治方式．分层自治结构与Internet自组织拓扑结构一致，分层自治地址分配机制结合了集中方式和分布方式的优点，具有较高的整体效率，主从结构连接管理体系也具有较高的控制效率，它们都具有较高的鲁棒性、柔韧性和伸缩性．

优化蚁群算法在排课中的应用策略

针对高校排课面临的问题和挑战,通过分析排课问题的约束条件,将解决排课问题转化为二分图匹配的问题,并给出优化蚁群算法方案,探索高校排课问题的优化策略。

计算广义离散哈特莱变换(GDHT)的快速递推算法

讨论了一般带时间参数和频率参数的广义离散 Hartley变换 ,基于代数中的块矩阵乘积分解式 ,建立了一种高效快速递推算法 ,其算术复杂性是目前最小的。

二部图在排课系统设计中的应用

介绍在进行排课系统设计时 ,利用二部图结构构造数学模型。

混合图在无向图割集生成中的应用

为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集。在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度。理论分析结果和实验比较结果均表明改进算法明显比现有算法高效。

使破轮图构形成为二次构形之边序的构造与生成

研究了使破轮图决定的构形成为二次构形的边序,证明了边序使破轮图构形成为二次构形的一个充要条件,找出了生成所有这种边序的递推算法。

f模式下广播网络的最佳源点集

所谓广播 ,就是将网络中一个成员所拥有的消息 ,沿着网络成员之间的通信线路传递给其它所有成员的过程 .称最初拥有消息的成员为源点 .从不同的源点广播一条消息所需的时间一般是不同的 .关于Whisper模式和 Shouting模式下树上的最佳源点与最佳源点对问题 ,已有相关文章进行过讨 .本文提出了比c(c≥ 1)广播模式更一般的 f 广播模式的概念 ,并从该模式出发 ,在树形网络中设计了寻找最佳源点和最佳 k(k≥ 2 )源点集的算法 .

几个最小2容错广播网络

广播是研究通信网络的某个成员的消息如何尽快地传递给所有其它成员的消息传递问题。有两种常见的通信模式,一类是shouting模式,即在一个单位时间内,一个顶点能够和它的所有邻点通信;另一类是whispering模式,即在一个单位时间以内,一个顶点最多只能和它的一个邻点通信。通信网络通常用图来描述。最初贮存消息的网络成员称为源点。一个极小k容错广播网络是指n个顶点的通信网络,它的每个成员都能在k条边失效的情形下在最小的时间T_k(n)内实现广播。T_s(n)定义为一个这样的最小整数,使得存在一个n阶网络,以该网络的任何顶点为源点都能在不超过T_K(n)个单位时间内执行k容错广播。B_k(n)是n阶极小k容错广播网络必需的通信线路的最小数目。本文提出了呼叫图的新概念,构造它可以直观地判断k容错广播方案的正确性,并且可以作为求解B_k(n)的一种有效的辅助手段,本文给出了一些B_2(n)值(n≤10)。