基于MWST-CS-K2算法的贝叶斯网络结构学习

针对K2算法依赖最大父节点数和节点顺序的不足,提出了一种改进的贝叶斯网络结构学习算法（MWST-CS-K2）。该算法先通过构造最大支撑树（MWST）得到最大父节点数;再利用变量间的关联度和更新系数对加边、减边和反转边进行规则设定,通过改进的布谷鸟算法对鸟巢位置进行寻优,应用广度优先搜索策略搜索遍历得到节点顺序;最后将最大父节点数和节点顺序作为K2算法的输入搜索得到最终网络。实验表明,所提出的MWST-CS-K2算法在标准的ASIA、SACHS和CHILD网络数据测试中的平均正确边比率分别达到了97.3%、87.7%和95.6%,学习效果优于其他对比算法,获得的网络结构和标准的网络结构最为相似。     

基于邻节点空间顺序序列优化的DV-Hop定位算法

针对典型的DV-Hop定位算法中未知节点在计算与信标节点间距离时估算的不足,在DV-Hop算法的基础上提出了一种优化定位精度的算法。考虑并分析了未知节点与信标节点的路径中相邻三个节点的通信边组成的夹角对计算距离的影响,提出了一种基于“邻节点空间顺序”序列标号法计算夹角的方案,实验仿真验证了该优化定位算法的有效性和可行性。     

求解必经点k条最优路径问题的粒子群优化算法

提出了一种解决指定必经点[k]条最优路径问题的粒子群优化算法。算法以[k]条最优路径集合作为优化目标,将粒子种群划分为[k]个子种群,通过各子种群的局部搜索和子种群间的相互协作,使种群在搜索过程中易于找到[k]条最优路径。为了提高含有多必经节点的初始生成路径的多样性,设计了基于弹性拉伸原理的种群初始化方法。在随机生成的26个节点65条边,50个节点262条边和80个节点410条边的拓扑图中,分别选取不同的源节点和目的节点,以及必经节点对算法进行了测试。数值实验结果表明,提出的算法在求解网络规模比较大、必经点数比较多的无环[k]条最优路径问题中具有比较好的性能。     

基于邻域k-核的社区模型与查询算法

现实生活中的网络通常存在社区结构,社区查询是图数据挖掘的基本任务.现有研究工作提出了多种模型来识别网络中的社区,如基于k-核的模型和基于k-truss的模型.然而,这些模型通常只限制社区内节点或边的邻居数量,忽略了邻居之间的关系,即节点的邻域结构,从而导致社区内节点的局部稠密性较低.针对这一问题,本文将节点的邻域结构信息融入k-核稠密子图中,提出一种新的基于邻域连通k-核的社区模型,并定义了社区的稠密度.基于这一新模型,研究了最稠密单社区搜索问题,即返回包含查询节点集且具有最高稠密度的社区.在现实生活图数据中,一组查询节点可能会分布在多个不相交的社区中.为此,本文进一步研究了基于稠密度阈值的多社区搜索问题,即返回包含查询节点集的多个社区,且每个社区的稠密度不低于用户指定的阈值.针对最稠密单社区搜索和基于稠密度阈值的多社区搜索问题,首先定义了边稠密度的概念,并提出了基于边稠密度的基线算法.为了提高搜索效率,设计了索引树和改进索引树结构,能够支持在多项式时间内返回查询结果.通过与基线算法在多组数据集上的对比,验证了基于邻域连通k-核的社区模型的有效性和所提出查询算法的效率.     

无线传感器网络中一种基于标号的贪婪转发算法

针对传统地理路由存在的路由空洞问题,提出一种新的路由算法:基于标号的贪婪转发LBGF算法。算法将网络中的节点组织为一个带环树,在构建树的同时,父节点依据子节点的位置信息为其分配隐含节点间亲缘关系的标号,从而形成一个树型标号系统,并设计相应的贪婪转发算法。分析与仿真结果表明:相对于GPSR,LBGF算法具有空洞避免、容错性强、通信与存储开销低、计算简便等优点,适于节点稀疏或障碍物较多的无线传感器网络。     

基于深度优先贪婪搜索的可重构硬件任务划分算法

针对可重构计算硬件任务划分通信成本较小化的问题,提出了一种基于深度优先贪婪搜索划分(DFGSP)算法。首先,从待调度的就绪队列中取出队首任务,在某一硬件面积约束下,按深度优先搜索(DFS)方式扫描一个计算密集型任务转换来的有向无环图(DAG),逐个划入满足要求的节点;然后,一遇到不满足面积要求的任务节点时,就计算当前划分模块间输出边数(可量化为通信成本);最后,跳过当前不满足要求的任务节点,继续搜索该点之后处于就绪状态的节点,当搜索到满足要求的点时,按加入该点后不增加当前划分块间输出边数和尽可能填满可重构运算阵列的原则进行。实验结果表明,与现有的簇划分(CBP)、簇层次敏感两种划分算法相比,提出的算法获得了最小划分模块数和平均跨模块间I/O边数最小的均值,通过实际验证,算法显著地改善了硬件任务的划分效果,而且运行开销没有明显增加。     

基于蝙蝠算法的贝叶斯网络结构学习研究

针对混合算法学习贝叶斯网络结构存在易陷入局部最优、搜索精度低等问题,提出了采用蝙蝠算法和约束结合的贝叶斯网络结构混合算法。首先应用最大最小父子(Max-min parents and children,MMPC)节点集合构建初始无向网络的框架,然后利用蝙蝠算法进行评分搜索并确定网络结构中边的方向。最后应用上述算法学习ALARM网,并和最大最小爬山(the max-min hill climbing,MMHC)算法,贪婪搜索算法相比较,结果表明在增加边、反转边、删除边以及结构海明距离方面都有不同程度的减少,表明改进算法具有较强的学习能力和良好的收敛速度。     

基于节点可达度的公交多路径搜索算法

针对公交网络路径搜索问题,以复杂网络的角度进行了相关研究。根据出行者实际需求,提出一种基于节点可达度的公交多路径搜索算法。采用复杂二分网络模型来描述公交网络,将公交线路和公交站点分别看做一类节点,每条公交线路与它所经过的公交站点之间存在连边;在分析网络社团结构的基础上定义了节点可达度,算法根据节点可达度逐步搜索直至目的节点,搜索过程保留可能存在的多条最佳路径。实验结果表明,该方法能够得到最小换乘的多条有效路径。     

结合增量与启发式搜索的多目标问题处理方法

提出了一种结合增量与启发式搜索的多目标问题处理方法,设计并实现了一个基于路径扩展方法的多目标增量启发式搜索系统.当问题搜索图中边的权重发生改变或添加删除节点时,该系统通过对搜索现场进行实时的更新,部分利用先前搜索保留的信息,从更新后的状态开始求解新的问题,从而提高了重搜索的效率.对gridworld标准测试样例进行了大量的系统测试,实验结果表明：结合增量与启发式搜索的处理方法能够有效地解决状态格局不断变化的一系列相似的多目标最短路径问题.     

基于节点排序的贝叶斯网络结构学习算法

针对K2算法学习贝叶斯网络结构时需要确定节点顺序的问题,提出一种混合贝叶斯网络结构学习算法。在给定数据集的情况下,利用MMPC算法获得网络的初始结构图,应用广度优先搜索的方式对此初始结构图进行搜索,从该图中入度为0的节点出发,按层次依次访问图中的邻接点,获得优化的节点顺序。将该节点顺序作为K2算法的初始节点顺序,再利用K2算法对空间进行搜索,找到全局最优解。实验结果表明,与K2算法和限制性粒子群算法相比,该算法在相同的样本数据集下产生多边、少边和反边情况的概率更低,并且可学习到更准确的贝叶斯网络结构,收敛速度快、求解精度高。     

A chronological and mathematical overview of digital circle generation algorithms – introducing efficient 4- and 8-connected circles

Circles are one of the basic drawing primitives for computers and while the naive way of setting up an equation for drawing circles is simple, implementing it in an efficient way using integer arithmetic has resulted in quite a few different algorithms. We present a short chronological overview of the most important publications of such digital circle generation algorithms. Bresenham is often assumed to have invented the first all integer circle algorithm. However, there were other algorithms published before his first official publication, which did not use floating point operations. Furthermore, we present both a 4- and an 8-connected all integer algorithm. Both of them proceed without any multiplication, using just one addition per iteration to compute the decision variable, which makes them more efficient than previously published algorithms.     

从中央美院设计基础课程探索看我国设计基础教育发展

我国自新中国建立起工艺美术教育,至1998年高等学校本科专业目录调整后确立的艺术设计教育专业;直至今日,经过多年研究和改革在艺术设计的设计基础课教学上,已有明显的进步。但不能否认还存在诸多不足,但皆因已有大量文献针对不足进行探讨和研究,故现以中央美院设计基础课的创新为例,针对设计基础教育的合理因素,进行归纳、总结、分析并比较德国国立魏玛包豪斯的艺术设计教育模式,从中总结和发现我国设计基础教育的创新探索与发展之路。     

Friends Classification of Ego Network Based on Combined Features

Ego networks consist of a user and his/her friends and depending on the number of friends a user has, makes them cumbersome to deal with. Social Networks allow users to manually categorize their “circle of friends”, but in today’s social networks due to the unlimited number of friends a user has, it is imperative to find a suitable method to automatically administrate these friends. Manually categorizing friends means that the user has to regularly check and update his circle of friends whenever the friends list grows. This may be time consuming for users and the results may not be accurate enough. In this paper, to solve this problem, we present a method, which combining user attributes, network structure and contact frequent three aspects. Efficiently using the profile of users, we first identify the relationship between them and then we attempt to solve the problem of community identification when a user’s profile is missing or inaccessible by use of ego network structural features. Lastly, to obtain more accurate results and realize updates automatically, we attempt to find those friends who have frequent contacts with the user. We compare the performance of the proposed algorithm with other methods, and the results show that our method has significant advantages to them.     

Tractable queries on big data via preprocessing with logarithmic-size output

Given a set S of points in the two-dimensional space, which are stored in a spatial database, this paper presents an efficient algorithm to find, in the area delimited by those points, the empty circle with the largest area that contains only a query point q. Our algorithm adapts previous work in the field of computational geometry to be used in spatial databases, which requires to manage large amounts of data. To achieve this objective, the basic idea is to discard a large part of the points of S, in such a way that the problem can be solved providing only the remaining points to a classical computational geometry algorithm that, by processing a smaller collection of points, saves main memory resources and computation time. The correctness of our algorithm is formally proven. In addition, we empirically show its efficiency and scalability by running a set of experiments using both synthetic and real data.     

Packing equal circles into a circle with circular prohibited areas

The paper considers the problem of packing a maximal number of identical circles of a given radius into a multiconnected domain. The domain is a circle with prohibited areas to be finite unions of circles of given radii. We construct a mathematical model of the problem and investigate its characteristics. The starting points are constructed in a random way or on the ground of the hexagonal lattice. To find the local maxima, a modification of the Zoutendijk method of feasible directions and a strategy of active inequalities are applied. We compare our results with the benchmark instances of packing circles into circular and annular containers. A number of numerical examples are given.     

一种含有圆弧的曲线快速求交方法

二维曲线的求交是CAD&CG中的一个基本问题,论文提出了一种由圆弧和直线段组成的二维曲线快速求交方法。首先选择一个最优方向,根据最优方向把封闭曲线分割为一系列单调链,然后通过拓展Bentley-Ottman的扫描线算法对单调链进行求交。算法时间复杂度为O((n+k)logm),其中n为顶点个数,k为交点的个数,m为划分的单调链的个数。     

Solving spatial basic geometric constraint configurations with locus intersection

A basic idea of geometric constraint solving (GCS) is to decompose the constraint problem into smaller ones according to some basic configurations. In this paper, we find all spatial basic configurations involving points, lines, and planes containing up to six geometric primitives in an automated way. Many of these basic configurations still resist effective analytical solutions. We propose the locus intersection method (LIM) for GCS, a hybrid method based on geometric computation and numerical search that can be used to find all the solutions for a geometric constraint problem. We show that the LIM can be used to solve all the above basic configurations.     

网络拓扑发现算法综述

本文分别总结了网络物理拓扑发现算法和网络逻辑拓扑发现算法两大类拓扑发现算法的基本思想和设计方法,分析了影响各算法性能的主要因素,并对今后网络拓扑发现算法的设计路线作了展望和提出了建议。我们认为本文对网络拓扑发现算法的设计者有较高的参考价值。     

Numerische Erfahrungen bei der Lösung des dreidimensionalen Transportproblems

To find an initial basic feasible solution is a special problem on solving the three dimensional transportation problem. It is not possible to do this work in a similar simple way as it can be done in the usual transportation problem. In [3] Haley proposes to solve a new problem that is essentionally the old one with the addition of a set of artificial variables. However, numerical investigations have shown that this procedure enlarges the amount of computing very much. This paper now gives another procedure for finding an initial basic solution for the three dimensional transportation problem. A great number of examples is discussed which demonstrate the efficiency of this procedure.     

Representing circles with five control points

We show that five is the minimal dimension of a space required to draw a complete circle with a unique control polygon. We identify all five-dimensional spaces invariant under translations and reflections where we can find shape preserving representations of a circle parameterized by its arc length.