一种基于继承次序与相关度的布图算法

在层次图边交叉最小化问题上,常规启发算法或者时间复杂度大或者布图效果不佳。基于Sugiyama布图算法模式,提出了一种交叉数减少算法,并从布局与布线两个主要方面介绍了其实现过程。两层图上的实验表明,该算法具有较好的性能,一定程度上克服了时间复杂度与效果的矛盾。     

低复杂度重构在分布式实时数据密集型Web服务架构中的应用

针对下一代分布式实时系统在重构时实时性要求较高的问题,本文提出了一种降低系统图复杂度并在有限时间内重构的方法。首先,利用服务组合确保重构在有限时间内实现;然后,通过路径选择算法和路径发送算法对图进行实时剪裁;最后,引入图构建算法消除具有更多非可调度路径的服务实现来降低图的复杂度。在iLAND服务重构和组合组件内部验证了本文方法,实验结果表明,本文方法能够显著减少解空间,大大减少了重构过程的计算时间。     

人工神经网络在并行计算机集群上的设计研究

人工神经网络在集群上的并行化设计和实现能够充分发挥ANN并行处理的特点,缩短训练时间,降低算法复杂度。随着并行技术的日益成熟,在并行集群上以软硬件相结合的方式设计神经网络的重要性也不断提高。从软硬件平台的多方面讨论了并行集群技术对人工神经网络设计的支持,提出了一种SOM神经网络在并行集群上的设计方法和基础框架,并就并行集群上神经网络训练效率的问题进行了深入讨论。该方案可广泛应用于多种神经网络模型的并行计算机实现。     

求图着色问题的新算法

图着色问题是NP-难度的问题。基于两种传统的启发式算法，提出了两种新的求解策略，由此给出了求图着色问题的两个新算法。与传统算法相比，其中一个新算法在时间复杂度不变的条件下，解的质量有明显提高；另一个则在时间复杂度稍有增加的前提下，进一步较显著地提高了所得解的质量。     

无线传感器网络中目标覆盖图的分解

在无线传感器网络中,为降低目标覆盖问题的复杂度,给出3种减小网络规模的方法,即删除冗余节点、删除冗余目标、将目标覆盖图分解成多个独立子图。分别证明这3种方法的正确性,并提出构造独立子图算法。仿真结果表明,该算法可以减少30%的网络规模,并降低目标覆盖问题的算法复杂度。     

多层次图排序算法及其在图剖分中的应用

图排序问题在众多领域中有着重要应用.本文利用多层次思想,提出一种具有V-循环结构的新算法.该算法是一种线性时间复杂度的方法.在文中的4个算例中,这种多层次方法所得到的排序质量至少比谱方法高5%.本文把它应用到图剖分领域,利用KL/FM方法对其进行了局部修改,得到了两种新的图剖分算法.在文中的4个算例中,这两种方法都能提供与当前质量最佳算法相当的图剖分结果.     

一种基于移动IPv6路由寻址的最短路径优化算法

移动IPv6的路由寻址是一个最短路径优化问题,最著名的两种最短路径算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,这两种算法的时间复杂度都是O(n3).本文通过对这两种经典算法的研究与分析,提出一种求最短路径的优化算法.该算法的时间复杂度是O(e*n),在连通图中,该算法能够比Floyd算法少近50%的迭代次数,在非连通图中e<相似文献   

求解区间图K-连接最短路径问题的在线算法

针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。     

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

下含D2D蜂窝网基于有向加权二部图的资源分配

针对蜂窝下含D2D系统最多允许一条蜂窝链路和一条D2D对链路同时共占信道的场景,旨在设计一种低复杂度的资源分配算法。首先将以最大化系统吞吐量为目标的资源分配问题归结为整数规划问题。考虑到干扰是决定两条链路能否共占信道的关键因素,将最优化问题转化为以最小化干扰链路信道增益为目标的问题;该问题可看作一对一双偏好最优匹配问题,为此,首次提出有向加权二部图的相关概念,并用它对最优化问题建模。为了降低寻找最优匹配的难度,提出一种贪婪算法,该算法复杂度仅为O(n)。仿真表明,与加权二部图算法相比,所提算法不仅在复杂度方面下降两个数量级,而且在一定范围内得到的系统吞吐量与容量等性能比加权二部图算法略优。     

一种新的复杂网络聚类算法

揭示网络簇结构的复杂网络聚类方法研究具有重要的理论意义和应用价值。应用两种谱方法将复杂网络簇结构发现问题转换为空间数据聚类问题,并将粒子群聚类算法应用到对复杂网络簇结构的探测,提出了两种新的结合粒子群聚类的复杂网络簇结构探测算法。最后在两类复杂网络上进行实验并对实验结果进行了比较分析,提出的新算法在聚类准确性方面效果更好。     

Xen虚拟机资源调度优化算法

针对Xen虚拟化平台中虚拟机资源分配不合理的问题,提出了两种资源调度优化算法,即细粒度优化算法和粗粒度优化算法.细粒度优化算法主要解决单个物理节点上虚拟机资源分配不合理问题,能够根据物理节点上运行的各虚拟机的资源利用情况来调整资源分配量,适当增加利用率较高的虚拟机的资源,减少资源利用率低的虚拟机的资源,从而优化资源分配,提高资源利用效率,避免不必要的虚拟机迁移.粗粒度优化算法是针对集群中多个物理节点之间虚拟机负载不均衡问题而提出的.该算法结合粒子群优化技术,选择将集群系统中热点物理机上的部分虚拟机迁移到最适合的冷点物理机上,从而避免高载物理机宕机.实验结果表明,这两种资源调度优化算法能够有效解决虚拟机资源分配不合理的问题,具有较好的适用性和应用前景.     

传感器网络中一种存储有效的小波渐进数据压缩算法

现有的数据压缩算法大多以节能为设计目标,很少顾及到节点有限的存储容量.设计适合传感器网络小波变换的环模型和基于覆盖重叠的分簇模型,消除边界效应.基于此两种网络模型,分别提出存储有效的二维和三维渐进小波数据压缩算法,该算法依据小波函数的支撑长度和簇头的可用存储容量来确定渐进传送的数据单元,具有存储有效性;依据空间相关性来选择渐进传送数据的传感器节点,从而在存储有效的同时又节省网络传输耗能.从存储开销、能量消耗和网络延时等3个方面分析了算法的性能.理论分析和实验结果表明,和一般的数据压缩算法相比,小波渐进压缩算法在耗能相当的情况下,节省了节点的存储容量.     

K-Harmonic means type clustering algorithm for mixed datasets

K-means type clustering algorithms for mixed data that consists of numeric and categorical attributes suffer from cluster center initialization problem. The final clustering results depend upon the initial cluster centers. Random cluster center initialization is a popular initialization technique. However, clustering results are not consistent with different cluster center initializations. K-Harmonic means clustering algorithm tries to overcome this problem for pure numeric data. In this paper, we extend the K-Harmonic means clustering algorithm for mixed datasets. We propose a definition for a cluster center and a distance measure. These cluster centers and the distance measure are used with the cost function of K-Harmonic means clustering algorithm in the proposed algorithm. Experiments were carried out with pure categorical datasets and mixed datasets. Results suggest that the proposed clustering algorithm is quite insensitive to the cluster center initialization problem. Comparative studies with other clustering algorithms show that the proposed algorithm produce better clustering results.     

网络集群计算系统中的并行任务调度

基于多处理机并行任务调度模型，探讨网络集群计算系统中的并行任务调度问题，首先证明了一般网络集群计算系统中调度算法的可近似性难度，然后提出了三种不同的启发式算法：最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法；然后根据大量的模拟实验对这些算法以及文献中已提出的调度算法进行了比较分析，结果表明该文的启发式算法比文献中的算法在性能上效果更好。     

Density Based Cluster Growing via Dominant Sets

Although there are a lot of clustering algorithms available in the literature, existing algorithms are usually afflicted by practical problems of one form or another, including parameter dependence and the inability to generate clusters of arbitrary shapes. In this paper we aim to solve these two problems by merging the merits of dominant sets and density based clustering algorithms. We firstly apply histogram equalization to eliminate the parameter dependence problem of the dominant sets algorithm. Noticing that the obtained clusters are usually smaller than the real ones, a density threshold based cluster growing step is then used to improve the clustering results, where the involved parameters are determined based on the initial clusters. This is followed by the second cluster growing step which makes use of the density relationship between neighboring data. Data clustering experiments and comparison with other algorithms validate the effectiveness of the proposed algorithm.     

Reusable components for partitioning clustering algorithms

Clustering algorithms are well-established and widely used for solving data-mining tasks. Every clustering algorithm is composed of several solutions for specific sub-problems in the clustering process. These solutions are linked together in a clustering algorithm, and they define the process and the structure of the algorithm. Frequently, many of these solutions occur in more than one clustering algorithm. Mostly, new clustering algorithms include frequently occurring solutions to typical sub-problems from clustering, as well as from other machine-learning algorithms. The problem is that these solutions are usually integrated in their algorithms, and that original algorithms are not designed to share solutions to sub-problems outside the original algorithm easily. We propose a way of designing cluster algorithms and to improve existing ones, based on reusable components. Reusable components are well-documented, frequently occurring solutions to specific sub-problems in a specific area. Thus we identify reusable components, first, as solutions to characteristic sub-problems in partitioning cluster algorithms, and, further, identify a generic structure for the design of partitioning cluster algorithms. We analyze some partitioning algorithms (K-means, X-means, MPCK-means, and Kohonen SOM), and identify reusable components in them. We give examples of how new cluster algorithms can be designed based on them.     

Analysis of integer programming formulations of clustering problems

Five different integer programming formulations of the clustering problem are discussed. Three new heuristic algorithms for solving these problems are presented. Some of the existing algorithms are generalized. The relevance of integer programming and combinatorial theory to cluster analysis is discussed. Many other applicable algorithms are listed.     

Cluster Editing: Kernelization Based on Edge Cuts

Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Most kernelization algorithms for the problem are based on the concept of critical cliques. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the cluster editing problem. Our techniques are based on the study of the relationship between cluster editing and graph edge-cuts. As an application, we present a simple algorithm that constructs a 2k-vertex kernel for the integral-weighted version of the cluster editing problem. Our result matches the best kernel bound for the unweighted version of the cluster editing problem, and significantly improves the previous best kernel bound for the weighted version of the problem. For the more general real-weighted version of the problem, our techniques lead to a simple kernelization algorithm that constructs a kernel of at most 4k vertices.     

一种基于图论的加权聚类融合算法

现有聚类融合算法对混合属性数据进行处理的效果不佳,主要是融合后的结果仍存在一定的分散性。为解决这个问题,提出了一种基于图论的加权聚类融合算法,通过对数据集聚类得到聚类成员后,利用所设计的融合函数对各个数据对象赋予权重,同时通过设置各个数据对间边的权重来确定数据之间的关系,得到带权最近邻图,再用图论的方法进行聚类。实验表明,该算法的聚类精度和稳定性优于其他聚类融合算法。