元素判别值分配法用于求解Hamilton圈问题的算法设计

Hamilton问题有最小Hamilton圈(H-圈)及Hamilton通路问题。H-圈问题可用于求解货郎担问题。但尚没有一种有效的求解方法。作者研究的‘元素判别值分配法’可以用于求解H-圈问题。该文介绍该方法用于求解最小H-圈的表上求解及程序求解的算法设计。     

用分层关联方法求有向图中所有Hamilton回路的算法

首先建立了有向图中初级通路的关联关系,并对初级通路的关联关系进行了分析,得到了关于初级通路关联关系的一些重要结果．然后,对初级通路的关联关系进行了分级分层．在此基础上,设计了求有向图中所有Hamilton回路的算法．该算法利用长度为k的初级通路及其分层关联关系逐步求长度为k＋1的初级通路及其分层关联关系的方法,求得有向图的所有Hamilton回路．通过理论分析可以看到,所设计的算法与已有的求有向图的所有Hamilton回路的算法相比,避免了大量的重复计算,从而降低了算法复杂度,为求解Hamilton回路问题提供了新思路．     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈.文中提出了变换的方法来寻找图中的Hamilton圈,即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈.由此,设计了一个在Edmonds意义下的有效算法--自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换,证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n2).最后通过应用实例说明该算法的有效性和实用性.     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈，即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此，设计了一个在Edmonds意义下的有效算法——自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换，证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n^2)。最后通过应用实例说明该算法的有效性和实用性。     

一个由接口路径求Hamilton回路的算法研究

为了求简单图中的所有Hamilton回路,首先,提出了一种对集合幂集进行编码的算法,引入了接口路径的概念,将Hamilton回路的运算转换为等级接口路径矩阵的运算;其次,结合肖尔茨猜想的证明,对算法复杂性的上限进行了估算;最后,以中国旅行商问题为例,给出了求解CTSP的精确算法.     

求Halin图中给定两点之间最优Hamilton路的有效算法

在赋权图中，求任意给定两点之间的最优（边权值之和最小）Hamilton路问题，简称OHP问题，是计算机领域的一个经典算法问题，它在网络路由选择和计算机的许多领域都有广泛应用。该问题是NP完全的。Halln图是对树和环网络的非平凡概括，因此求赋权Halin图的OHP问题是非常有意义的。但当前仍没找到该问题的有效算法。本文通过递归压缩Halin图中的扇，设计了一个求解赋权Halin图OHP的有效算法，并给出算法的正确性证明和复杂度分析。     

基于多方向对称和匀质约束的SUSAN棋盘格角点检测算法

棋盘格角点检测是摄像机标定过程中的一个重要步骤。针对原有SUSAN角点检测算法在棋盘格角点检测应用中边缘点与角点难以区分的问题,通过对棋盘格角点特性的分析和实验,提出了一种基于多方向对称和匀质约束的SUSAN棋盘格角点检测算法。通过在原有SUSAN算法的基础上添加对称约束算子和匀质约束算子滤除SU- SAN检测结果中的边缘点,最终确定角点的坐标。实验结果表明,该算法在角点检测的有效性和精度方面优于已有算法。     

多部图的匹配算法研究

本文给出了一个多部图的商匹配问题的定义,提出了求解多部图商匹配问题的一个算法。该算法使用圈与割集中偶图的交相结合的方法,利用求二部图的最大匹配算法,求解多部图的最大商匹配问题。     

蚁群神经网络在旅行商问题中的应用

在求解旅行商问题(TSP)时,首先引入交叉策略进行预处理,将具体的地图抽象为常见的无向完全图,即把TSP抽象为求无向完全图的一条Hamilton回路;然后用蚁群算法与人工神经网络相结合的方法来求解.实验结果表明了该方法的可行性和高效性.     

马步遍历探索

马步遍历探索是一个有难度也有趣味的组合数学问题。分别应用回溯与贪心算法探索马步遍历n＊m棋盘。结果显示,回溯算法能够求出问题的所有解,但效率较低,而贪心算法的求解效率非常高,但只能求得问题的一个解,且对于有解棋盘往往得不到解。     

一个关于Hamilton环（路）的多项式时间算法

该研究为Hamilton环路（道路）问题设计出了一个多项式时间算法,论证了它的正确性。根据该算法编制了程序,进行了大量的实例计算。文章公布了主要研究方法、过程、实验数据,以及粗略的算法步骤。详细的算法步骤和证明将在随后的论文中发表。由于Hamilton环路（道路）为著名的NP完全问题,而作者认为自己已彻底解决了NP复杂问题。     

一种改进的量子进化算法及其在乡村邮路问题的应用

针对基本量子进化算法易陷于局部最优解的缺陷,提出一种改进的量子进化算法(QEA)。结合乡村邮路问题,对算法进行了测试,结果表明,改进算法在全局寻优能力和种群多样性方面比基本量子进化算法有所改进,是求解乡村邮路问题的一种有效算法。     

基于Hamilton回路的车辆巡逻问题优化算法

一类车辆巡逻问题可以归结为赋权Hamilton回路最小化问题。该文采用一种局部优化的单点切割方法，优化了业已求得的Hamilton回路经典启发式算法，给出了算法基础定理的数学证明，通过算例说明了算法的实现过程。该算法改进了经典启发式算法的性能，在实践中取得了良好的效果。     

面向变电站机器人巡检路径规划中的算法研究

针对目前在变电站中应用广泛的巡检机器人,探讨了其巡检路径的问题,依据离散数学理论中的哈密顿回路方法和路径的常规规划算法,研究了一种变电站的巡检路径为矩形分布时的机器人巡检路径问题。针对不同巡检方式,分别提出：全局巡检方式,采用新提出的哈密顿算法,当巡视起点被设定后,其他被巡视的任何点均可被归类,从而找出其巡检路径的哈密顿回路;重点设备巡检方式,采用Dijkstra算法和遗传算法相结合的方法;固定点巡检方式,采用Dijkstra算法。其中,三种巡检方式分别针对电量充足、低电量返回及充电完毕继续巡视等方面给出仿真结果,并将其在某变电站进行了试用。研究结果表明,三种巡检方式下的算法均有效可行,新提出的哈密顿回路算法巡视的路径比常规方法相对要短,算法的运算速度相对更快。     

哈密顿回路问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得哈密顿回路问题的所有解。在新模型中,解空间的生成过程与边的排列顺序无关。     

基于TSP的图的路包装问题的算法研究

图的路包装问题是一类有着重要应用背景的最优化问题,然而它在计算复杂度上是NP-困难的。受Hassin和Rubinstein的思想启发,在max-TSP问题的基础上给出了完全图的路包装问题的近似算法,分析了算法的复杂度和近似比;基于LINGO软件的算例表明了算法的可行性和有效性。     

基于互连网络系统故障的新型自适应诊断算法

互连网络的故障诊断是网络系统可靠性分析的重要内容。PMC模型是一种重要的网络故障模型。针对具有哈密顿环的互连网络(也称哈密顿网络),利用分治回环思想,提出了一种新的基于PMC故障模型自适应的诊断算法。其核心思想是,首先对哈密顿网络进行序列划分,然后对得到的每个01序列的结节进行回环诊断,最后利用回环诊断的结果对非01序列的节点进行诊断。对于一个具有多个01序列的互连网络,该算法通过有限次轮回的测试,能准确的定位系统中的故障节点,对于正确节点的诊断可靠度能无限接近100%。当系统中存在的回测边越多,该算法的诊断效果越好。     

一种求解邮路问题的量子进化算法

乡村邮递员问题属于NP完全问题,对它的近似求解方法主要是智能算法及线性规划,但其中的基本量子进化算法易陷于局部最优解。为此,提出一种新的量子进化算法,结合城市垃圾运输问题,对算法进行测试。结果表明,该算法在全局寻优能力及种群多样性方面均比传统算法有所改进,是求解乡村邮递员问题的一种有效算法。     

Parallel algorithms for the hamiltonian cycle and hamiltonian path problems in semicomplete bipartite digraphs

We give anO(log⁴ n)-timeO(n ²)-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph,B, provided that a factor ofB (i.e., a collection of vertex disjoint cycles covering the vertex set ofB) is computed in a preprocessing step. The factor is found (if it exists) using a bipartite matching algorithm, hence placing the whole algorithm in the class Random-NC. We show that any parallel algorithm which can check the existence of a hamiltonian cycle in a strong semicomplete bipartite digraph in timeO(r(n)) usingp(n) processors can be used to check the existence of a perfect matching in a bipartite graph in timeO(r(n)+n ² /p(n)) usingp(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC. We also consider the problem of finding a hamiltonian path in a semicomplete bipartite digraph.