一种基于元胞自动机的无向图剖分优化算法

运用元胞自动机理论,针对无向图剖分优化问题进行了分析和建模,提出了一种元胞自动机模型以及基于该模型的无向图剖分优化算法。在该元胞自动机模型中,元胞对应于无向图中的结点,元胞的邻居对应于邻接结点,元胞空间对应于无向图中的结点集,元胞的状态对应于所在的结点子集。实验及分析表明该算法不仅能找到无向图的近似最优剖分,而且有效地降低了空间复杂度和时间复杂度。     

基于赋权有向超图的云计算依赖任务调度研究

如何对依赖任务进行高效合理的调度是云计算急需解决的关键问题之一。对云计算环境下的依赖任务调度系统进行了形式化描述。采用赋权有向无环超图来构造依赖任务调度问题的数学模型,结点对应于依赖任务,有向超边对应于任务之间的执行先后依赖关系。将云计算依赖任务调度问题转换为赋权有向超图的优化划分问题,提出了基于多水平方法和赋权有向超图的依赖任务划分优化算法。设计并实现了基于多水平方法的云计算依赖任务调度原型系统。在CloudSim云计算仿真实验平台下,与Min-Min算法、Max-Min算法进行了对比实验,实验数据对比表明该算法在减少依赖任务执行时间的同时,优化了资源负载均衡性能。     

求解非线性方程组的元胞自动机方法及其全局收敛性证明

为了求得非线性方程组所有精确解,根据元胞自动机的特点构造了求解非线性方程组的全局收敛算法。在该算法中,将非线性方程组解的理论搜索空间划分为离散搜索空间,将离散搜索空间定义为元胞空间;离散搜索空间的每个点就是一个元胞,而一个元胞对应着非线性方程组的一个试探解;元胞的状态由其空间位置及位置修正量构成。将元胞空间划分为若干个非空子集,所有元胞的状态从一个非空子集转移到另一个非空子集的状态演化过程实现了元胞空间对理论搜索空间的搜索。在元胞状态演化过程中,元胞从一个状态转移到另一个状态的状态转移概率可以计算出来;元胞演化过程中的每个状态对应于有限Markov链上的一个状态。利用可归约随机矩阵的稳定性条件证明了该算法具有全局收敛性。仿真实例表明该算法是高效的。     

赋权超图划分算法的电路划分实验比较研究

给出了赋权超图优化划分问题的形式化描述,并结合电路划分的具体应用,采用赋权超图来构造ISPD98电路测试基准的数学模型。阐述了基于迁移方法和多水平方法的赋权超图优化划分算法,并重点讨论了粗化阶段的不同结点匹配策略、迁移优化阶段的不同结点迁移优化策略。基于ISPD98测试基准给出的18 组电路,进行了迁移方法和多水平方法的对比实验,以及五种结点匹配和三种结点迁移优化不同组合策略的对比实验,实验数据对比充分验证了多水平方法的可行性和效率。     

基于空间数据挖掘的分区异步元胞自动机模型研究

传统的元胞自动机模型采用统一的转换规则和相同的演化速率进行演化,忽略了地理现象演变的时空差异性：演化规律的空间异质性和演化速率的空间差异性。针对这一问题,提出了基于空间数据挖掘的分区异步元胞自动机模型,采用双约束空间聚类的方法对元胞空间进行分区,用分区转换规则替代统一转换规则可以体现地理现象演化规律的空间差异性;采用标准格网划分的方法求取异步元胞演化速率,用异步演化速率替代同步演化速率可以体现地理现象演化速率的空间差异性。以杭州市土地利用变化为例对基于空间数据挖掘的分区异步元胞自动机模型进行了实证研究,结果表明：与传统的元胞自动机模型相比,基于空间数据挖掘的分区异步元胞自动机模型具有较高的模拟精度,并且适用于较大区域较长时间段地理现象的动态变化模拟。基于空间数据挖掘的分区异步元胞自动机模型是地理元胞自动机研究的新视角,它将地理现象演变的空间异质性和时间差异性引入到地理元胞自动机模型中,使模型对地理过程的模拟更接近实际地理过程。然而,由于有关分区异步的元胞自动机模型还处于尝试性研究阶段,在元胞空间分区方法、双约束空间聚类算法中权重的确定方法、元胞演化速率的获取方法、元胞转换规则的获取方法、模拟精度评估以及分区异步元胞自动机模型在较大区域较长时间的地理现象模拟中的应用等方面有待进一步的研究与探讨。     

元胞自动机压缩算法仿真卫星云图

为减小计算复杂度和提高压缩比,提出基于方块编码和可逆元胞自动机结合的二值图像压缩算法来仿真卫星云图简单实用的元胞自动机编码表示方法。并针对卫星云图特性和业务实际,提出搜索和统计云图元胞邻域的状态集合,改进加权有限元胞自动机算法,对卫星云图数据进行压缩。实验表明,两种编码方法都能有效地减小计算复杂度,提高压缩比。峰值信噪比(PSNR)在30 dB左右,RCA-BTC算法压缩率可以达到15,图像重建仿真效果良好。     

基于元胞鱼群算法的人员疏散模型

针对元胞自动机模型以及原始人工鱼群算法在刻画综合交通枢纽人员常规疏散行为上的局限性,本文提出了一种基于元胞鱼群算法的人员疏散模型,考虑个体之间的行走速度、视野范围差异,将排队机制和出（入）口选择行为、导向行为、记忆功能加入原始人工鱼群算法中,顶层采用改进的人工鱼群算法进行移动位置更新,底层采用元胞自动机模型解决移动位置冲突.实验证明,该模型可真实反映人员在综合交通枢纽内换乘时的疏散过程;在同等环境下,与原始人工鱼群模型相比,该模型实现了个体按照疏散引导进行有序移动,避免了陷入局部最优;与元胞自动机模型相比,其更好地体现了个体的从众、避障和出（入）口选择行为,有效地降低了时间复杂度.     

基于结点间距离统计的无向无权图同构判别

按照同构图的定义判断两个图是否同构,最坏情况下其时间复杂度是O(N!),当结点数N比较大时,计算速度非常慢,针对该问题,提出一种通过统计结点间距离和按照距离分层,计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法,该算法可以给出两个图的结点间可能的对应关系.如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应,其时间复杂度仅为O(N4),否则,根据结点间可能的对应关系,避免遍历所有结点序号的交换,计算量可以成倍地下降.     

进化树拓扑路网构建及多停靠点路径规划方法研究

针对多停靠点线路优化问题,提出一种基于邻接矩阵网络拓扑树构建的路径寻优方法,借鉴系统生物学中进化树分类的思想,引入路网结点间邻接关系评价标准邻接值的概念,将路网按照其结点邻接关系归类划分为以路网结点间邻接值为表征的路网拓扑进化树,同时对线路路径寻优问题中目标结点进行动态回溯分类,在限定路网搜索区域同时采用分支定界搜索策略进行搜索优化,降低了搜索算法时间复杂度.最后依据国家基础地理信息系统网站提供的国界、省会城市及主要公路基础地理数据进行系统实现,证明该算法的有效性.     

基于元胞自动机模型的新型二值图像压缩算法

不同于传统的去相关,去冗余的压缩方法,提出一种基于元胞自动机模型的二值图像压缩算法。该算法用遗传规划算法搜索出较优的元胞自动机规则后,对分块后的二值图像矢量进行元胞自动机变换,利用元胞自动机的变换状态多样性等特点,生成相邻矢量,将变换次数作为码本。实验表明：该算法经过4次以内的元胞自动机变换即可生成较优的相邻矢量,具有编码时间短、重建图像的质量好、压缩率高、适应性强等特点,并且与其它压缩算法结合性好。     

Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices

K$K$-way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct K$K$-way refinement, instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct K$K$-way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning.     

基于属性分布相似度的超图高维聚类算法研究

在许多聚类应用中,数据对象是具有高维、稀疏、二元的特征。传统聚类算法无法有效地处理此类数据。该文提出一种基于超图模型的高维聚类算法,通过定义对象属性分布特征向量和对象间属性分布相似度,建立超图模型,并应用超图分割法进行聚类。聚类结果通过簇内奇异特征值进行评价。实验结果和算法分析表明,该算法可以有效地进行聚类知识挖掘。     

Hypergraph recovery algorithms from a given vector of vertex degrees

Methods of obtaining certain classes of hypergraphs from a given integer vector of vertex degrees are considered. These classes are as follows: hyperedges with unit weight incident upon k vertices; hyperedges with unit weight incident upon k vertices in the case when the vertices may be non-unique; multiple hyperedges incident upon k vertices; and arbitrary hypergraph in which the edges can contain any set of k vertices. For each of these classes, an algorithm is proposed for constructing the hypergraph from an arbitrary vector. If the construction is impossible, the algorithm determines how much the vector should be reduced so that the hypergraph could be constructed.     

寻求简单多边形凸壳的线性时间算法

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选，使剩余顶点的角的大小排成递增序，然后用Graham扫描方法删去非凸壳顶点，最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点，最后得到凸壳顶点序列。这两种算法简单，易于实现，时间复杂性都是O（n)。     

A new fragment re-allocation strategy for NoSQL database systems

NoSQL databases are famed for the characteristics of high scalability, high availability, and high fault-tolerance. So NoSQL databases are used in a lot of applications. The data partitioning strategy and fragment allocation strategy directly affect NoSQL database systems’ performance. The data partition strategy of large, global databases is performed by horizontally, vertically partitioning or combination of both. In the general way the system scatters the related fragments as possible to improve operations’ parallel degree. But the operations are usually not very complicated in some applications, and an operation may access to more than one fragment. At the same time, those fragments which have to be accessed by an operation may interact with each other. The general allocation strategies will increase system’s communication cost during operations execution over sites. In order to improve those applications’ performance and enable NoSQL database systems to work efficiently, these applications’ fragments have to be allocated in a reasonable way that can reduce the communication cost i.e., to minimize the total volume of data transmitted during operations execution over sites. A strategy of clustering fragments based on hypergraph is proposed, which can cluster fragments which were accessed together in most operations to the same cluster. Themethod uses a weighted hypergraph to represent the fragments’ access pattern of operations. A hypergraph partitioning algorithmis used to cluster fragments in our strategy. This method can reduce the amount of sites that an operation has to span. So it can reduce the communication cost over sites. Experimental results confirm that the proposed technique will effectively contribute in solving fragments re-allocation problem in a specific application environment of NoSQL database system.     

计算两类网络的可靠性的多项式时间算法

定义了两类有向网络——ORC-网络和IRC-网络,并且提出一个计算它们的根通信可靠性(网络的一个特定结点(根点)能与其余每个结点通信的概率)的多项式时间算法.对于ORC-网络和IRC-网络,该算法的时间复杂度分别是O(｜E｜)和O(｜V｜·｜E｜),这里,｜V｜,｜E｜分别表示网络所含结点和边的数量.