检索结果-南通市图书馆

超立方体幂图中常重点集导出子图的团分布和最大独立集

在线全文

学校读者我要写书评

暂无评论

超立方体幂图中常重点集导出子图的团分布和最大独立集

作者：师娟娟太原理工大学

学位级别：硕士

在现代通信系统中,码距约束是一个基本出发点,而在码距的基础上设计具有明确规律的校验矩阵是进一步提升编译码效率的关键,也是码的性能提升的关键点.常重码作为一类典型的结构码,从而编码理论中的最基本的问题就是求A(n,d,w)的值,A(n,d... 详细信息

在现代通信系统中,码距约束是一个基本出发点,而在码距的基础上设计具有明确规律的校验矩阵是进一步提升编译码效率的关键,也是码的性能提升的关键点.常重码作为一类典型的结构码,从而编码理论中的最基本的问题就是求A(n,d,w)的值,A(n,d,w)是所有码字的码重为w,最小Hamming距离为d的最大n长二元码集的大小.Hamming,Vardy等许多著名学者都进行了深入的研究,但是并没有完全解决这个问题.在此基础上,本文从图论的角度出发,针对这个问题做了一些相关的探索.首先,本文将A(n,d,w)看作n维超立方体d-1次幂图点导出子图Qn(d-1,w)的最大独立集的大小,从而将求A(n,d,w)的值的问题转化为找Qn(d-1,w)的最大独立集的问题.为研究Qn(d,w)的最大独立集,我们从结构的角度分析了其最大团的分布和结构特点.根据Qn(d,w)的结构特点,我们先对其作了关于(1,1,…,1,0,0,…,0)的距离划分得到不同的距离集,然后构造了距离集中满足一定距离条件的最大子集,在此基础上完整得到了 4≤d≤5时Qn(d,w)中最大团的数量、结构特点及分布状况.其次,通过研究Qn(d-1,w)的最大独立集,我们刻画了 A(n,d,w)=2、3的情形.对A(n,d,w)=4的情形做了初步探索.

关键词：超立方体最大独立集最大团最大码集二元码

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

最大独立集算法

西南交通大学学报 1995年第5期30卷 473-479页

作者：朱松年朱嫱西南交通大学运输工程系马里兰大学土木工程系

本文提出了网络中的一种特殊结构──负包络图。原来是它包含了网络的最小截，因而制约了网络的最大流量。研究表明，负包络图也是关于网络最大独立集的充要条件。本文以既有的最大流算法为手段，利用这个充要条件，给出了在偶网络上求... 详细信息

本文提出了网络中的一种特殊结构──负包络图。原来是它包含了网络的最小截，因而制约了网络的最大流量。研究表明，负包络图也是关于网络最大独立集的充要条件。本文以既有的最大流算法为手段，利用这个充要条件，给出了在偶网络上求最大独立集的有效算法，而且也给出了在奇网络上求最大独立集的递归算法。

关键词：负包络图最大流最小截网络最大独立集

在线全文

学校读者我要写书评

暂无评论

基于串行最大独立集的连通支配集构造及分析

华中科技大学学报（自然科学版） 2011年第3期39卷 61-65页

作者：王玉明赵大胜华中科技大学电子与信息工程系湖北武汉430074

针对传感器网络最大独立集的构造方法中并行构造算法生成的连通支配集尺寸没有明确的上界且难以确定边界节点的问题,在串行最大独立集构造算法的基础上,提出了基于权重和时序的触发式连通支配集构造算法.仿真结果表明:该算法无需构造生... 详细信息

针对传感器网络最大独立集的构造方法中并行构造算法生成的连通支配集尺寸没有明确的上界且难以确定边界节点的问题,在串行最大独立集构造算法的基础上,提出了基于权重和时序的触发式连通支配集构造算法.仿真结果表明:该算法无需构造生成树,降低了计算时延和通信开销;此外,由于最大独立集节点存在时间上的先后关系,因而使得边界节点的数量显著减少,最终求得的连通支配集存在明确的上界.

关键词：无线传感器网络最大独立集连通支配集通信复杂度计算复杂度

在线全文

学校读者我要写书评

暂无评论

最大独立集问题及其成长算法的研究

最大独立集问题及其成长算法的研究

作者：戎文晋太原理工大学

学位级别：硕士

最大独立集问题(Maximum Independent Set problem，MIS)是图论中经典的组合优化问题。本文综述了国内外学者对此问题的研究成果，包括该问题的应用背景，界的估计，求解的难点及现代优化算法的设计。通过对遗传算法的研究，并模拟了... 详细信息

最大独立集问题(Maximum Independent Set problem，MIS)是图论中经典的组合优化问题。本文综述了国内外学者对此问题的研究成果，包括该问题的应用背景，界的估计，求解的难点及现代优化算法的设计。通过对遗传算法的研究，并模拟了生物个体的成长机制，本文提出了一种新的启发式算法-------成长算法(Grown-Up Algorithm，简称GUA)。该算法将组合最优化问题解的演进分为诞生和成长两个阶段，诞生阶段产生一个近似解，成长阶段让这个近似解象生物个体一样成长为一个满意解，并且诞生和成长均在确定性和随机性的双机制作用下演进变化。与遗传算法相比，其主要特点是利用诞生算子强化了遗传算法的初始化过程，利用成长算子使解的进化有了定向的机制。本文主要研究了GUA在MIS问题中的应用，详细探讨了诞生算子和成长算子的构造，算法的效能分析等，并在DIMACS图上进行了测试，取得了良好的效果，表明了GUA有效的运行机制，值得进一步研究。

关键词：最大独立集成长算法启发式算法诞生算子成长算子

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

一种启发式的分布式最大独立集算法

南京邮电大学学报（自然科学版） 2013年第6期33卷 18-23,28页

作者：杜鹏南京邮电大学自动化学院江苏南京210023

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树(Tree)算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树(m-Tree)算法。理... 详细信息

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树(Tree)算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树(m-Tree)算法。理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播(BP)的分布式算法,是对BP算法的一种推广。仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解。

关键词：分布式算法最大独立集 0-1整数规划信念传播

最大独立集和最小弱顶点覆盖问题求解及其应用研究

在线全文

学校读者我要写书评

暂无评论

最大独立集和最小弱顶点覆盖问题求解及其应用研究

作者：彭震宇江南大学

学位级别：硕士

全局优化问题,特别是组合优化问题,是科学研究与工程计算中最基本的问题之一,这类问题的求解一直是算法研究领域的热点问题。全局优化方法一般分为确定型和随机型方法,确定型方法在数学理论上较为完善,但难以应用,而传统的随机型方法对... 详细信息

全局优化问题,特别是组合优化问题,是科学研究与工程计算中最基本的问题之一,这类问题的求解一直是算法研究领域的热点问题。全局优化方法一般分为确定型和随机型方法,确定型方法在数学理论上较为完善,但难以应用,而传统的随机型方法对于复杂的全局优化问题又难以解决,这时启发式算法的引入使得随机型方法和整个全局优化方法得到了新的发展,尤其是元启发式算法。蚁群优化算法(Ant Colony Optimization,简称ACO)作为一种新的元启发式算法,具有分布式计算、自组织、正反馈以及贪心启发等特点,使其能够成功解决许多NP-hard组合优化问题。ACO算法作为一种全局搜索算法,其全局优化性能的优劣在很大程度上与参数的正确选择有关。但由于ACO算法参数之间的关联性,使得最优参数组合成为一个极其复杂的优化问题,目前还没有形成完善的理论依据,一般都是根据经验来确定参数值。而禁忌搜索算法(Tabu Search,简称TS)以其灵活的禁忌表和相应的禁忌准则来避免重复迂回搜索,具有强大的全局优化性能。所以为弥补ACO算法易出现停滞现象和陷入局部最优这一缺陷,本文将ACO算法与TS算法组合起来,提出了基于禁忌搜索的蚁群优化算法(Tabu Search Based Ant Colony Optimization,简称TSBACO),并将该算法用于求解最大独立集问题。实验表明:禁忌搜索策略的引入,不仅提高了TSBACO算法的全局优化性能而且还提高了搜索效率。为了增强超大规模集成电路(VLSI)系统运行时的可靠性与稳定性,需要在电路设计中引入容错技术增强系统的容错能力。在VLSI阵列的容错技术中,一般有冗余法和降阶法两种重构方法,这两种方法都属于NP-hard问题。本文是通过冗余法来解决这一问题的,根据阵列中缺陷单元的分布情况,构造相应的矛盾图模型,将阵列的重构问题转化为求解矛盾图的独立集问题。通过TSBACO算法对矛盾图的独立集进行求解且使得所求独立集大小恰为缺陷单元个数,找出合理的补偿通道来完成阵列的重构问题。实验分析表明该重构方法是简单有效的。为进一步验证TSBACO算法在求解组合优化问题方面的实用性和有效性,本文将其应用于网络流量测量中的有效测量点选择问题。通过对图论中最小顶点覆盖模型的研究,网络流量测量点选择问题可以抽象为最小弱顶点覆盖问题,而求解该问题是一个NP-hard问题,于是本文又提出了一种求解最小弱顶点覆盖问题的TSBACO算法。比较现有的求解算法,实验结果表明:本文提出的TSBACO算法能够发现更小的弱顶点覆盖集,且具有更好的可扩展性,是网络流量测量中的一种有效测量点选择算法。

关键词：蚁群优化算法禁忌搜索算法最大独立集最小弱顶点覆盖

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于最大独立集的钢种集约问题求解方法

系统工程学报 2014年第3期29卷 414-422页

作者：易剑贾树晋谭树彬杜斌东北大学信息科学与工程学院辽宁沈阳110819 宝钢研究院自动化研究所上海201900

针对炼钢生产中的钢种集约问题,建立了数学模型,并以图论的思路设计了一种基于最大独立集的求解方法.首先基于图论知识,构造了钢种集约问题的图,并证明了最大独立集的独立数是它的主目标的下界;然后对图进行赋权,以实现对次要目标的控制... 详细信息

针对炼钢生产中的钢种集约问题,建立了数学模型,并以图论的思路设计了一种基于最大独立集的求解方法.首先基于图论知识,构造了钢种集约问题的图,并证明了最大独立集的独立数是它的主目标的下界;然后对图进行赋权,以实现对次要目标的控制;最后在最大独立集的基础上,采用图分解的方法,对赋权图递归分解来获得优化后的钢种集约方案.选择实际生产数据构造了一些测试案例,对它们进行仿真计算,结果表明所提出的算法明显好于遗传算法;同时分析了图的顶点、密度变化对算法性能的影响,揭示了它们之间的关系.

关键词：钢种集约图论最大独立集遗传算法

基于PNA的最大独立集问题的DNA计算模型

在线全文

学校读者我要写书评

暂无评论

生物数学学报 2008年第3期23卷 501-508页

作者：崔建中殷志祥杨静安徽理工大学数理系安徽淮南232001 华中科技大学控制科学与工程系湖北武汉430071

肤核酸(Peptide Nucleic Acid)是人工合成的拔酸(DNA)的类似物.PNA能够特异地、稳定地与DNA杂交以及其独特的性质,使得PNA广泛应用在分子生物学中.本文提出了一种基于PNA的最大独立集问题的DNA计算模型,利用单链PNA被逐步褪火到单链DNA... 详细信息

肤核酸(Peptide Nucleic Acid)是人工合成的拔酸(DNA)的类似物.PNA能够特异地、稳定地与DNA杂交以及其独特的性质,使得PNA广泛应用在分子生物学中.本文提出了一种基于PNA的最大独立集问题的DNA计算模型,利用单链PNA被逐步褪火到单链DNA分子上,解决了一个最大独立集问题的实例.该模型的解空间只有一种类型的DNA分子,计算经m步生物操作产生问题的解(其中m=|E(G)|),最后利用鞭子PCR(whiplash PCR)原理以及凝胶电泳读解.

关键词： DNA计算最大独立集肽核酸

在线全文

学校读者我要写书评

暂无评论

偶错位图的张量幂的最大独立集和自同构群

中国科学：数学 2011年第12期41卷 1075-1088页

作者：邓芸萍谢富纪张晓东上海交通大学数学系上海200240 上海交通大学安泰经济与管理学院上海200052

若An是X:={1,2,...,n}上的偶置换构成的交错群,εn是X上的偶错位集,则Cayley图AΓn:=Γ(An,εn)称为偶错位图.令AΓqn为q个AΓn的张量幂.在本文中,我们研究了AΓqn的连通性、直径、独立数、团数、色数和最大独立集等性质.利用AΓqn最大... 详细信息

若An是X:={1,2,...,n}上的偶置换构成的交错群,εn是X上的偶错位集,则Cayley图AΓn:=Γ(An,εn)称为偶错位图.令AΓqn为q个AΓn的张量幂.在本文中,我们研究了AΓqn的连通性、直径、独立数、团数、色数和最大独立集等性质.利用AΓqn最大独立集的结果,我们完全确定了AΓqn的自同构群的结构.

关键词：自同构群 Cayley图张量幂最大独立集交错群