检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

图的路径运算矩阵与哈密顿回路等路径问题

华中科技大学学报（自然科学版） 2021年第2期49卷 32-36页

作者：高遵海陈倬武汉轻工大学数学与计算机学院湖北式汉430048 武汉轻工大学经济与管理学院湖北式汉430048

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路... 详细信息

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上。证明了一般路径运算矩阵的幂长公式并得到了简单图存在哈密顿回路的充要条件,分析了矩阵乘法运算的总时间复杂度,结果表明本算法比其他同类方法计算量大大减少,为图论相关路径问题研究提供了一个新的研究方法。

关键词：路径运算矩阵简单图最长路最短路哈密顿回路

在线全文

学校读者我要写书评

暂无评论

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

计算机工程与应用 2006年第30期42卷 62-64,71页

作者：方俊潘勇湖南长沙民政职业技术学院软件学院长沙410004

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在... 详细信息

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

关键词： DNA计算表面方式解空间哈密顿回路

有限循环群上的Cayley有向图的哈密顿回路

在线全文

学校读者我要写书评

暂无评论

系统科学与数学 1990年第2期10卷 169-174页

作者：张先迪李正良电子科技大学

给定有限循环群G及其特征集M(记为 G=〈M〉),在G上以M为特征集的Cayley有向图Γ(M,G) 定义如下:Γ(M,G)的顶点为 G 的元,当且仅当 g∈G,s∈M 时,在Γ(M,G)中存在一条从 g 到 gs 的弧.本文所指的群均为至少有三个元的有限群,其特征集 M ... 详细信息

给定有限循环群G及其特征集M(记为 G=〈M〉),在G上以M为特征集的Cayley有向图Γ(M,G) 定义如下:Γ(M,G)的顶点为 G 的元,当且仅当 g∈G,s∈M 时,在Γ(M,G)中存在一条从 g 到 gs 的弧.本文所指的群均为至少有三个元的有限群,其特征集 M 均不含单位元.有限集 E 的元的个数记为|E|.令 T=[t_1,t_2,…,t_r](表示序列),n 为正整数,n 个 T 排成的序列记为 n*T.例如,T=[t_1,t_2],2*T=[t_1,t_2,t_1,t_2].

关键词： Cayley有向图哈密顿回路有限群

在线全文

学校读者我要写书评

暂无评论

用“遗传”算法求任意图的所有哈密顿回路

哈尔滨工业大学学报 2004年第12期36卷 1690-1692页

作者：王彦祺石家庄经济学院信息工程学院河北石家庄050031

给出求解任意图所有哈密顿回路的"遗传"算法.首先,使用"继承"法,求完全图的所有哈密顿回路,既从Kk的哈密顿回路求Kk+1的哈密顿回路,直到Kn的哈密顿回路;然后,使用"选择"算法,将Kn中所有哈密顿回路在实际图中有不存在边的哈密顿回路去掉... 详细信息

给出求解任意图所有哈密顿回路的"遗传"算法.首先,使用"继承"法,求完全图的所有哈密顿回路,既从Kk的哈密顿回路求Kk+1的哈密顿回路,直到Kn的哈密顿回路;然后,使用"选择"算法,将Kn中所有哈密顿回路在实际图中有不存在边的哈密顿回路去掉,最后得到任意图Gn的所有哈密顿回路,如果全部去掉,则该图不是哈密顿图.

关键词：哈密顿回路遗传算法无向图正向表结点标号数组

在线全文

学校读者我要写书评

暂无评论

逐点循环递归法求哈密顿回路

哈尔滨工业大学学报 2004年第1期36卷 115-117,121页

作者：王彦祺石家庄经济学院信息工程系河北石家庄050031

给出了求解任意图的所有哈密顿回路逐点循环递归算法,用于处理复杂的旅行商问题,证明了一个图是否是哈密顿图。在算法中,用结点标号数组存储一个回路,无向图的正向表存储初始图。

关键词：逐点循环递归法哈密顿回路哈密顿图无向图旅行商问题

在线全文

学校读者我要写书评

暂无评论

改进的哈密顿回路蜂群无人机航迹规划

兵器装备工程学报 2022年第S1期43卷 139-142页

作者：于晓琳郎炎澍张崇武警警官学院信息通信系成都610213 武警第二机动总队第一支队江苏无锡214026

为了使无人机蜂群作战的航迹规划更贴近侦察任务实际需求,对蚁群算法求解哈密顿路径的方法做了适当改进,引入影子蚂蚁,使蚂蚁本体和影子蚂蚁共同完成对所有目标点的访问,侦察任务中派遣的无人机总数即为影子蚂蚁和本体蚂蚁的数量。通过... 详细信息

为了使无人机蜂群作战的航迹规划更贴近侦察任务实际需求,对蚁群算法求解哈密顿路径的方法做了适当改进,引入影子蚂蚁,使蚂蚁本体和影子蚂蚁共同完成对所有目标点的访问,侦察任务中派遣的无人机总数即为影子蚂蚁和本体蚂蚁的数量。通过实验和结果分析,保证了蚁群算法在蜂群无人机航迹规划中路径总和最短、各条路径长度相近的结果,确保了改进后的算法在蜂群无人机航迹规划问题中的可行性和有效性。

关键词：影子蚂蚁蚁群算法哈密顿回路蜂群无人机航迹规划

一种基于关联矩阵判断图的哈密顿性及求解哈密顿回路的算法

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

宁波大学学报（理工版） 2018年第2期31卷 83-88页

作者：王亚丽徐晨东宁波大学理学院浙江宁波315211

基于对图的关联矩阵分析,刻画了哈密顿回路的关联矩阵的有关性质,给出了简单无向图和有向图为哈密顿图的充分条件和具体算法,该算法不仅可以判断简单图的哈密顿性,而且可以找出该图的所有哈密顿回路.最后用实例说明该算法的正确性和有效性.

关键词：哈密顿图哈密顿回路关联矩阵

在线全文

学校读者我要写书评

暂无评论

再生哈密顿回路的边数条件

哈尔滨理工大学学报 2012年第6期17卷 41-46页

作者：刘书家北京工商大学计算机与信息工程学院北京100048

为了缩小最短哈密顿回路的搜索空间,从而提高TSP算法的搜索效力;并依据图论中邻点交叉边的性质,对哈密顿回路内边进行全面分析和统计,给出和证明了再生哈密顿回路的边数条件P(n),这在图论中是未曾有过的.进而证明了最短哈密顿回路必至... 详细信息

为了缩小最短哈密顿回路的搜索空间,从而提高TSP算法的搜索效力;并依据图论中邻点交叉边的性质,对哈密顿回路内边进行全面分析和统计,给出和证明了再生哈密顿回路的边数条件P(n),这在图论中是未曾有过的.进而证明了最短哈密顿回路必至少含有前P(n)条小边之一的结论.该结论可广泛应用于TSP搜索算法中,减少搜索时间.

关键词：哈密顿回路最短哈密顿回路再生哈密尔顿回路

在线全文

学校读者我要写书评

暂无评论

λ阶短哈密顿回路的最小权法

广西科学院学报 2005年第2期21卷 67-70,75页

作者：周炳生周勤南京大学信息管理系江苏南京210008 南京金陵科技学院图书馆江苏南京210008

提出短哈密顿回路的概念,分析由延长而形成最短哈密顿回路的特点,得出求权图G(n,m)λ阶短哈密顿回路的最小权法.该最小权法不但可精确求得最短和其它阶的短哈密顿回路,而且可用于权图G(n,m)的判别,得出求λ阶短路径的最小权法.

关键词：哈密顿回路最小权短路径权图