检索结果-南通市图书馆

维普期刊数据库博看期刊

在线全文

学校读者我要写书评

暂无评论

占线顶点覆盖问题的结构性下界

系统工程理论与实践 2012年第1期32卷 134-138页

作者：代文强电子科技大学经济与管理学院成都610054

在实际顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静... 详细信息

在实际顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.

关键词：占线问题选址顶点覆盖算法竞争比

在线全文

学校读者我要写书评

暂无评论

顶点覆盖变体问题的确定参数可解算法研究

计算机工程与科学 2008年第12期30卷 79-81,84页

作者：洪翔宇蔡晟复旦大学信息工程学院计算机系上海200433

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题:一个是连接的顶点覆盖问题,二是含权的树型顶... 详细信息

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题:一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。

关键词：参数复杂性确定参数可解算法顶点覆盖连接顶点覆盖

在线全文

学校读者我要写书评

暂无评论

具有完美匹配的图的顶点覆盖问题

浙江大学学报（理学版） 2013年第5期40卷 506-508页

作者：金珍万龙南昌工程学院理学系江西南昌330099 江西财经大学信息管理学院江西南昌330013

对具有完美匹配的无向图的顶点覆盖问题进行了研究,提出了2个相关的问题,并对它们的难解性做出了判断.

关键词：完美匹配顶点覆盖 P问题 NP完全问题

在线全文

学校读者我要写书评

暂无评论

图的最小顶点覆盖问题的DNA表面计算模型

计算机工程与应用 2009年第6期45卷 69-72页

作者：羊四清李小龙袁辉勇湖南人文科技学院湖南娄底417000 湖南大学计算机与通信学院长沙410082

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

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。

关键词： DNA计算表面方式解空间顶点覆盖

在线全文

学校读者我要写书评

暂无评论

模糊环境下的最小权顶点覆盖问题

计算机应用研究 2012年第1期29卷 38-42页

作者：王辰尹倪耀东柯华对外经济贸易大学信息学院北京100029 同济大学经济与管理学院上海200092

最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描... 详细信息

最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描述模糊不确定性,并根据不同的决策准则建立了求解模糊环境下最小权顶点覆盖问题的三个决策模型,结合模糊模拟和遗传算法设计了一种求解所建立模型的混合智能算法,并给出了数值实验。数值实验的结果验证了所提出的决策模型与算法的有效性。

关键词：顶点覆盖模糊变量可信性理论模糊模拟遗传算法

在线全文

学校读者我要写书评

暂无评论

改进的最优顶点覆盖贪心边近似算法

计算机应用 2006年第1期26卷 149-151页

作者：杨杰康定民族师范高等专科学校计算机科学系四川康定626001

最优顶点覆盖问题是6个基本的NP完全问题之一,无法在多项式时间内得到最优解,除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时,证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。

关键词：顶点覆盖近似算法近似因子单点贪心边双点贪心边贪心边

在线全文

学校读者我要写书评

暂无评论

最优顶点覆盖的贪心边近似算法

四川师范大学学报（自然科学版） 2006年第2期29卷 244-248页

作者：杨杰王玲康定民族师范高等专科学校计算机科学系四川康定626001 四川师范大学计算机科学学院四川成都610066

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证(能得到最优覆盖点数)时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点... 详细信息

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证(能得到最优覆盖点数)时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.

关键词：贪心边单点贪心边双点贪心边顶点覆盖近似算法

点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算法研究

在线全文

学校读者我要写书评

暂无评论

点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算...

作者：段侠昆明理工大学

学位级别：硕士

给定一个无向图,一个边的子集称为匹配,如果里面的任意两条边都没有共同的交点;一个顶点的子集称为顶点覆盖,如果图中每一条边的两个端点中的至少一个在该顶点子集内。经典的最大匹配问题要求图中包含边数最多的匹配,而经典的顶点覆盖... 详细信息

给定一个无向图,一个边的子集称为匹配,如果里面的任意两条边都没有共同的交点;一个顶点的子集称为顶点覆盖,如果图中每一条边的两个端点中的至少一个在该顶点子集内。经典的最大匹配问题要求图中包含边数最多的匹配,而经典的顶点覆盖问题要求图中包含顶点数最少的顶点覆盖。匹配与顶点覆盖问题是组合最优化研究的中心问题。在计算复杂性方面,匹配可认为是类问题的典型代表,顶点覆盖问题可认为是难问题的典型代表。对匹配与顶点覆盖问题的持续和深入研究推动了学科的发展,丰富了算法理论和技巧,揭示了深刻的数学关系。Kǒnig(1931)找到了让这两个问题相互联系的图论结构：二部图。经典的Kǒnig定理断言：在二部图中,最大的匹配包含的边数等于最小的顶点覆盖包含的顶点数。20世纪以来离散数学的发展见证了Kǒnig定理的深刻性。很多推动学科发展的著名定理都和Kǒnig定理等价,它们包括：代数学中的P. Hall定理,偏序集上的Dilworth定理,图论中的Menger定理,网络流的最大流最小割定理等等。本文研究点赋权二部图上的边装填与顶点覆盖问题,关注它们的关系及其算法研究。给定一个无向图,每个顶点上有一个正整数权重,一个边的子集(边允许重复)称为一个边装填,如果图中每个顶点与中的边相关联的数目不超过该点的权重;一个顶点的子集称为顶点覆盖,如果图中每一条边都与相交。最大边装填问题要求图中包含边数最多的边装填,而最小顶点覆盖问题要求图中顶点权重之和最小的顶点覆盖。这两个问题推广了经典的最大匹配与最小顶点覆盖问题,有重要的理论意义和广阔的应用前景。本文分析了这两个问题的计算复杂性,用整数规划理论证明了这两个问题的最优值在二部图结构下相等,并提供了多项式时间算法求解任意二部图上的这两个问题的最优解。我们的结果推广了Kǒnig定理,并为相关的装填与覆盖问题提供了有益的参考。

关键词：匹配顶点覆盖难边装填计算复杂性整数规划

最大顶点覆盖问题及限定条件下的随机近似算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

最大顶点覆盖问题及限定条件下的随机近似算法

作者：周培衍山东大学

学位级别：硕士

众所周知,集合覆盖问题和顶点覆盖问题,同为Karp的21个NP-完全问题,它们都是非常著名的NP-完全问题。因这些问题在选举、网络设计、生物信息学等方面有广泛应用而受到了理论计算机研究学者的重点关注。本文主要研究他们的变体问题,最大... 详细信息

众所周知,集合覆盖问题和顶点覆盖问题,同为Karp的21个NP-完全问题,它们都是非常著名的NP-完全问题。因这些问题在选举、网络设计、生物信息学等方面有广泛应用而受到了理论计算机研究学者的重点关注。本文主要研究他们的变体问题,最大覆盖问题、最大顶点覆盖问题和局部集合覆盖问题。最大覆盖问题为给定基础集合S,S中元素构成的子集的集合Sc,目标为从Sc中找不超过K个子集,使得覆盖S中尽量多的元素。特殊情况下若每个元素在Sc中出现正好两次,则为最大顶点覆盖问题。相应地,子集加权和顶点加权版本的问题为加权最大覆盖问题和加权最大顶点覆盖问题。截止目前,最大覆盖和加权最大覆盖问题最好的近似算法的近似比为（e-1）/e,最大顶点覆盖和加权最大顶点覆盖问题最好的近似比为3/4[1]。局部集合覆盖问题和最大覆盖问题输入参数相同,不过目标为从Sc中选最少数量的子集,使得覆盖S中至少K个元素。定义f为最大频次,即元素出现在Sc所有子集中最大次数。局部集合覆盖问题的最好近似算法是在16年前被设计的,近似比为f。针对以上几个问题,本文的主要工作如下:1、基于线性规划舍入技术,对于最大覆盖问题设计了近似比为（e-1）/e-ε的近似算法,对于最大顶点覆盖问题设计了近似比为3/4-ε的近似算法。论文提出的算法使用简单的随机舍入策略并结合Chernoff界分析,极大的简化了证明过程且可以推广到其他类似问题。结合Hoeffding界分析,可将算法推广到加权最大覆盖和加权最大顶点覆盖问题并保证相同的近似比,该算法除去解线性规划是多项式时间的。随后指出论文[1]中关于加权最大顶点覆盖问题的疏漏之处。2、提出了关于局部集合覆盖问题的双标准的近似比为（ln1/ε,1-ε）的近似算法,其中ε和1/f有关。严格来说,算法保证使用最多ln1/ε·OPT个子集,覆盖S中至少（1-ε）·K个元素（该算法明显对于局部线覆盖问题有效）。该算法基于简单的随机取整策略,同样结合了 Hoeffding界分析。3、针对最大顶点覆盖问题,论文还研究了 3-度图（每个顶点度数不超过3）和3-正则图（每个顶点度数都为3）上的最大顶点覆盖问题。在3-正则图上,设计了近似比为21/25的算法,结合线性规划技术分析可行解的存在性可精确到79/90。算法也可以推广到3-度图上,得到的近似比为19/24。而且证明了论文中对算法近似性能比的分析是紧的。

关键词：顶点覆盖集合覆盖随机算法近似算法线性规划