区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法.利用这两种方法,对最小团覆盖、最大团、最大独立集、最小支配集、Hamiltonian 回路、最佳道路覆盖、最小带宽和Steiner 树的计算问题, 在EREW PRAM 模型上给出O(logn) 时间,使用O(n) 处理器的高效并行算法.     

一种大规模稀疏中国邮递员问题快速求解方法

针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进：首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割;其次根据邻近节点覆盖率对分割后的节点群进行合并;最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明：在奇偶点图上作业法所能支持的节点规模下,该方法可求得与确定性算法相同的最优解,并在运算时间上达到约10倍的效率优化;且该方法在大规模稀疏路网图下可有效提高计算效率,并在可控时间范围内得到优化的可行解,针对5 000个节点规模的路网图最快可在60 s内完成求解.     

基于分治策略和蚁群算法的最大团问题的研究

最大团问题是经典的NP-hard问题,对该问题求解方法的研究在理论上、实践上都具有一定的意义.蚁群算法已成功地求解出许多组合优化难题.通过使用分治法,将图分解成子图,对各子图应用蚁群算法求解,提出一种求解最大团问题的蚁群算法.它减小了问题的求解规模,使求解变得容易,且实验取得了较好的结果.     

求解有向图中三个分图问题的研究

强分图、单向分图和弱分图都是研究有向图的子图的连通性问题,求解强分图的算法有很多。总结了强分圈的求解算法,主要是算法实现的基本技术和特点;通过论述求解单向分图和相应无向图的团问题的等价性,提出了求解单向分图问题是NP问题的观点;最后又阐述了求解弱分图的方法,并给出了一个具体的算法。     

运输调度问题图上作业法的改进及其计算机实现

“利用标准圈的图上作业法”是线性规划中求解运输调度问题的一种方法，针对其中“找圈”运算等困难，本文运用了人工智能学科的思想和方法，在运输网络上建立“圈号”、“边号”启发式表示法，用产生式系统实现流向图的优化迭代过程，从而简化、改进了原有的方法。作为应用实例．本文构造了一个汽车调度实验系统，使所提出的求解方法得到了正确的计算机实现。     

分布式内存机器中优化调度问题的数学模型

对分布式内存机器中相互依赖多任务的优化调度问题,将约束条件归纳为任务约束、链路约束和资源约束,建立了允许任务复制情况下多任务静态调度问题的数学模型.描述了有向无回路图的构造性定义,指出问题一定有不超过所有任务执行时间总和的解.推出以最短时间完成任务集所需的最小资源数与任务数一样大.阐明了问题具有可计算性.研究结果改进了原有的问题描述和数学模型,使对问题的认识更深入,并有利于寻求更好的求解策略.     

求解大规模稀疏有向图回路的多线程并行算法

传统的基于深度优先遍历的回路求解算法限于计算机内存无法对大规模图进行求解,而已有的分布式图计算系统需要借助计算机集群,成本较高。针对此问题,给出一种可在普通计算机上求解大规模有向图所有回路的多线程并行算法。该算法根据顶点的出度,首先删除出度为0的顶点,然后采用多线程并行求解包含出度较大的顶点的回路,最后使用串行算法求出图剩余部分的回路。实验表明,此算法能够在普通计算机上求得大规模有向稀疏图的所有回路。     

决策影响图在设备可靠性系统分析中的应用

决策影响图是决策分析的一种新的图形表征求解方法，它用无回路的有向图表征决策变量、随机变量和目标函数之间的相关关系，并进行推理分析、信息分析和灵敏度分析等．本文运用影响图分析法研究设备可靠性分析问题．     

有向哈密顿回路问题的一个充分条件及其多项式验证算法

利用自动机理论研究有向哈密顿回路问题，提出一个多项式复杂度的算法验证有向哈密顿回路问题的一个充分条件.更具体地说，将有向图建模为一个自动机，并在自动机的基础上形式化了哈密顿图的相关概念，然后提出了一个多项式复杂度的算法，检验一个自动机标记的语言的子集是否满足真子集的一个充分条件.在该算法的基础上，提出了一个多项式复杂度的算法检验哈密顿图的一个充分条件并找出相应的哈密顿回路.特别地，给出了一个判断有向图是否是哈密顿图的充分条件和一个判断有向图中的一条回路是否是哈密顿回路的充分条件.     

切比雪夫映射族关联函数的指数型丢番图方程

切比雪夫映射族是一类典型的混沌映射，关联函数是研究其统计性质的关键.本文所研究的指数型丢番图方程源于该映射族的关联函数的计算问题.为求得该方程的解，本文首先对该方程进行简化，使简化后的方程具有严格单调递增的指数及非零系数.然后本文引入了“块”的概念，根据简化方程所含块的个数对其进行了分类，进而将原丢番图方程求解问题转化为由块所构成的丢番图方程的求解问题.本文最后研究了一个和两个块的情形，并举例说明了本文结果的应用.     

一个新的与或图求解算法

给出了一个包含有向回路的与或图的求解算法,以及如何确定被扩展节点的祖行节点的优先数,并通过优先数有效地选取祖先节点的方法也在本文中给出。     

蛇形图的消圈公式

本文讨论了任意形状蛇形图的消圈数,给出每节都是4-圈情形的蛇形图别名函数C(H),并证明每节为4-圈的蛇形图的消圈数等于它的别名函数的势.另外,在保持消圈数不变的情况下,通过简单的收缩、剖分运算把求解任意情形的蛇形图的消圈数问题归为求解每节都是4-圈特殊情形下的蛇形图消圈数问题.     

基于带回溯传播信息和编码技术的求解传递闭包方法

求解传递闭包问题是计算机科学中的一经典问题.文章提出了一种新的传递闭包算法,并导出了若干理论结果,能够将任一关系图化为左偏序图,它是基于带回溯传播信息和编码技术的深度优先搜索算法,该算法效率高,且易于实现.     

计算机视觉中的图匹配方法研究综述

图匹配是计算机视觉与模式识别领域的基础而又重要的问题.它在诸多方面都有着广泛的应用.从优化角度看,图的匹配问题是一种离散组合优化问题,使得该问题本身具有NP(non-deterministic polynomial)-hard性质.因此,寻找该问题的一种有效的近似解是当前研究的重要问题.论文首先对图匹配问题的的问题表示进行了阐述,并分析了该问题求解的难点和关键点.然后,对近年来计算机视觉研究领域中提出的一些具有代表性的传统图匹配算法进行了归纳和综述.最后,探讨了图匹配的未来研究方向和研究思路.     

在细胞图自动机上寻找图的基本回路

将细胞自动结构推广到任意图结构，并用它解决图论中的问题，是细胞自动机理论在图论领域中的一个应用．本文给出了用细胞图自动机求任意连通图的所有基本回路的并行算法     

基于生成树的回路核

针对图的相似性问题,提出了基于生成树的回路核,其中包括基于最小生成树的回路核、基于最大生成树的回路核、基于最小生成树或最大生成树的回路核、基于最小生成树与最大生成树的回路核、基于混合生成树的回路核、基于赋权混合生成树的回路核.结果表明,所定义的基于生成树的回路核是可计算的、正定的;在实验中,回路核的识别率高于通路核的识别率,最高可达100%.     

图的Steiner最小树的竞争决策算法

图的Steiner最小树问题是一个著名的NP难题,在通讯网络、VLSI等工程实践中有着重要的应用.在分析图的Steiner最小树问题数学性质的基础上,提出了图的Steiner最小树的竞争决策算法.为了验证算法的有效性,求解了OR-Library中的基准问题,测试结果表明了算法具有较好的求解效果.     

区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法,利用这两种方法,对最小团覆盖,最大团,最大独立集,最小支配集,Hamiltonian回路,最佳道路覆盖,最小带宽和Steiner树的计算问题,在EREW PRAM模型上给出O(logn)时间,使用O（n)处理器的高效并行算法。     

网络图任意两点间最短路径问题的计算机实现

最短路径问题是网络分析中的一个最基本的问题,著名的旅行推销员问题,中国邮路问题,运输网络的最小费用最大流问题及最小根树问题等都建立在此问题的基础上。本文用集合并的思想解决了Floyd算法中路径寻求在计算机上实现的问题,并给出了负回路的判别方法,从而也解决了中国邮路、旅行推销员等相关问题的计算机实现问题。     

用遍历方式求解图中是否存在回路问题

本文介绍用图的深度优先搜索遍历求图中是否存在回路问题的算法。