Drawing non‐layered tidy trees in linear time

The well‐known Reingold–Tilford algorithm produces tidy‐layered drawings of trees: drawings where all nodes at the same depth are vertically aligned. However, when nodes have varying heights, layered drawing may use more vertical space than necessary. A non‐layered drawing of a tree places children at a fixed distance from the parent, thereby giving a more vertically compact drawing. Moreover, non‐layered drawings can also be used to draw trees where the vertical position of each node is given, by adding dummy nodes. In this paper, we present the first linear‐time algorithm for producing non‐layered drawings. Our algorithm is a modification of the Reingold–Tilford algorithm, but the original complexity proof of the Reingold–Tilford algorithm uses an invariant that does not hold for the non‐layered case. We give an alternative proof of the algorithm and its extension to non‐layered drawings. To improve drawings of trees of unbounded degree, extensions to the Reingold–Tilford algorithm have been proposed. These extensions also work in the non‐layered case, but we show that they then cause a O(n²) run‐time. We then propose a modification to these extensions that restores the O(n) run‐time. Copyright © 2013 John Wiley & Sons, Ltd.     

Variational Tree Synthesis

Modelling trees according to desired shapes is important for many applications. Despite numerous methods having been proposed in tree modelling, it is still a non‐trivial task and challenging. In this paper, we present a new variational computing approach for generating realistic trees in specific shapes. Instead of directly modelling trees from symbolic rules, we formulate the tree modelling as an optimization process, in which a variational cost function is iteratively minimized. This cost function measures the difference between the guidance shape and the target tree crown. In addition, to faithfully capture the branch structure of trees, several botanical factors, including the minimum total branches volume and spatial branches patterns, are considered in the optimization to guide the tree modelling process. We demonstrate that our approach is applicable to generate trees with different shapes, from interactive design and complex polygonal meshes.     

最短路径算法在校园导游系统中的应用

用无向网表示学校的平面图,设计了该平面图的存储结构,并应用最短路径算法实现了查询图中各景点的相关信息,以及查询图中任意两个景点间的最短路径的功能;应用克鲁斯卡尔算法构造该平面图的最小生成树,求出可以连通所有景点的最短路径。该系统为新生熟悉校园环境提供了方便。     

基于糊模ID3算法的高校学生流失数据挖掘研究

目前高校不断扩招,生源却逐渐减少,于是预防和减少学生流失正成为各高校必须面对的问题。通过对高校学生流失情况进行数据挖掘,可发现一些有价值的信息,为解决高校学生流失问题提供帮助。基于糊模理论提出了糊模ID3算法,并将该算法运用于分析高校学生流失原因之中。通过实验证明,该算法生成的决策树更加合理,分类速度更快,为解决高校学生流失问题提供了理论依据。     

基于贪婪路由协议的动态单/多链路故障恢复策略

针对现有的贪婪方法不能有效处理拓扑结构中链路故障的问题,提出单链路故障和多链路故障本地化恢复策略。首先,通过利用克莱因伯格的贪婪嵌入给出单链路故障恢复策略;然后,将其扩展到多链路故障的情况;最后,在基于Python/C++的仿真环境下对提出的技术进行评估。实验结果表明,该技术仅需要非常有限的资源,且造成的路由质量损耗也有限,可以实现快速切换,可依网络生成树中链路数目扩展。该技术的可扩展性、简单性和低开销使其适合于大型网络。     

数据挖掘预测模型在脑损伤患者认知功能康复中的应用

为了更好地预测后天性脑损伤ABI(Acquired Brain Injury)患者认知功能康复的影响因素,提出基于决策树(DT)、多层感知器(MLP)和广义回归神经网络(GRNN)的三种预测模型。借助于10折交叉验证测试算法,通过专一性、灵敏度和精度分析以及混淆矩阵分析对模型的性能进行测试,从而获得新的知识以评估和改善认知功能康复过程中的有效性。实验结果表明,基于DT的模型的模拟结果明显比其他模型更为优越,预测平均精度可高达90.38%。     

RIAIL:大规模图上的可达性查询索引方法

图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.     

基于攻击树的安全芯片穿透性測试评估

随着安全芯片应用范围的不断扩大和应用环境的日趋复杂,需要通过穿透性测试验证芯片的安全性,同时有必要对测试进行评估。为此,提出一种基于攻击树模型的安全芯片穿透性测试评估方法。分析安全芯片的穿透性测试过程,采用攻击树模型作为穿透性测试的描述模型,在此基础上提出攻击事件的多属性赋值方法、攻击代价的推算方法和攻击路径的分析方法。应用结果表明,该方法可准确评估安全芯片穿透性测试结果。     

一种并行中英文混合多模式匹配算法

针对中英文混合文本的匹配准确性及大规模数据文本的匹配效率等问题,基于经典的线索化完全哈希特里树算法,提出一种并行化的中英文混合多模式文本匹配算法。采用拆分文本降低多模式匹配算法的串行度,进而在拆分出的小文本上并行地执行文本匹配。通过并行化预处理过程,设计新的存储结构。实验结果表明,该算法在保证结果正确的前提下,执行效率高于经典的串行匹配算法,当数据规模达到226个字符时,可以获得8倍以上的加速比。