检索结果-内蒙古大学图书馆

作者：黄玉飞河北师范大学

学位级别：硕士

求解边度量生成集及边度量维数是图论和组合优化领域的一个重要问题.边度量维数是近些年提出来的研究对象.给定一个连通图G＝(V,E),顶点w∈V到边e=uv∈E的距离定义为d(w,e)=min{d(u,w),d(v,w)}.一个顶点子集S称作图G的边度量生成集,如... 详细信息

求解边度量生成集及边度量维数是图论和组合优化领域的一个重要问题.边度量维数是近些年提出来的研究对象.给定一个连通图G＝(V,E),顶点w∈V到边e=uv∈E的距离定义为d(w,e)=min{d(u,w),d(v,w)}.一个顶点子集S称作图G的边度量生成集,如果对于边集E中任意两条不同的边e1,e2 ∈E,在顶点子集S中都存在一个顶点w∈S,使得d(w,e1)≠d(w,e2).本文通过构作一个合适的势函数,进而给出了关于边度量维数问题的贪婪算法.所得结论:1.构作了一个解决一般图上边度量维数问题的贪婪算法.2.对构作的贪婪算法,给出了近似比(1+lnn)+ln(log2n),其中n是图G中顶点的个数.3.对圈和树给出了解决赋权的边度量维数问题的算法.

关键词：边度量维数边度量生成集近似算法次模函数

来源：评论

学校读者我要写书评

暂无评论

强化学习中特征选择研究

强化学习中特征选择研究

引用

作者：林洁南京邮电大学

学位级别：硕士

大规模状态和动作空间下的维度灾难问题目前是强化学习研究中的一个难题,广泛被使用的解决方法是值函数估计。但估计的值函数和真实的值函数是有差距的。误差的来源除学习方法本身的拟合能力外,值函数选择特征的好坏对误差也有着很大的... 详细信息

大规模状态和动作空间下的维度灾难问题目前是强化学习研究中的一个难题,广泛被使用的解决方法是值函数估计。但估计的值函数和真实的值函数是有差距的。误差的来源除学习方法本身的拟合能力外,值函数选择特征的好坏对误差也有着很大的影响。因而本文围绕着强化学习的特征选择问题,设计了一些值函数估计中进行特征选择的算法,主要工作如下:(1)针对值函数估计与真实值函数的误差的问题,本文提出一种基于贪心的封装式特征选择方法为值函数构造一个好的特征。并通过分段值函数的方法处理特征选择的不稳定特性。实验结果表明,该方法提高了特征选择的稳定性,也增强了值函数估计的准确性。(2)针对强化学习中特征选择速度较慢,以及贪心策略只顾当前最优,目光短浅的问题,本文根据弱次模函数的性质,提出了一种分布式的top-k贪心方法选择特征。实验结果表明该方法提高了特征选择的速度,并且探索到更好的特征。(3)封装式的特征选择依据后续算法的效果作为特征选择的标准,而强化学习的训练较长导致了即使使用分布式的方法也难以较好解决时间消耗大的问题。本文提出基于经验回放的过滤式特征选择方法,通过经验回放生成强化学习数据集,接着直接在数据集上完成特征选择的工作,最后只需使用一次强化学习的训练来检验特征选择的效果。实验结果表明,基于经验回放的过滤式方法特征选择的速度明显快于封装式的方法。

关键词：强化学习值函数估计特征选择次模函数分布式优化

来源：评论

学校读者我要写书评

暂无评论

两阶段次模最大化问题的近似算法研究

两阶段次模最大化问题的近似算法研究

引用

作者：徐楚楚南京师范大学

学位级别：硕士

次模最大化问题在许多领域广泛应用,包括机器学习,数据科学和人工智能等.随着超模函数的出现,次模+超模（BP）函数最大化问题的研究也变得非常热门.基于次模曲率和超模曲率,本文研究了两个与次模和超模相关的问题:两阶段次模最大化问题... 详细信息

次模最大化问题在许多领域广泛应用,包括机器学习,数据科学和人工智能等.随着超模函数的出现,次模+超模（BP）函数最大化问题的研究也变得非常热门.基于次模曲率和超模曲率,本文研究了两个与次模和超模相关的问题:两阶段次模最大化问题和两阶段BP函数最大化问题.使用替代贪婪算法,对于满足基数约束和p-拟阵约束的两阶段次模最大化问题,我们设计了一个近似比只与次模函数fi（i=1,2,···,m）的最大次模曲率kf有关的近似算法,近似比为(1/p(1-e-p)-k_f((1-e-p)/(p（p+1）)+(e-（p+1）-e-p)/（p+1）)).对于满足基数约束和拟阵约束的两阶段BP函数最大化问题,我们设计了一个近似比只与超模函数gi（i=1,2,···,m）的最大超模曲率kg有关的近似算法,近似比为(（1-kg）2)/(（1-kg）2+2).

关键词：两阶段次模最大化两阶段BP函数最大化次模函数超模函数贪婪算法

来源：评论

学校读者我要写书评

暂无评论

聚集式路旅行商问题和带次模惩罚的分组奖励收集旅行商问题的近似算法

聚集式路旅行商问题和带次模惩罚的分组奖励收集旅行商问题的近似...

引用

作者：张家旋河北师范大学

学位级别：硕士

旅行商问题是组合优化中一个经典的NP-难问题.本文研究旅行商问题的两个变形:带次模惩罚的分组奖励收集旅行商问题和聚集式路旅行商问题.对于带次模惩罚的分组奖励收集旅行商问题,本文首先利用给出的带次模惩罚的分组奖励收集旅行商问... 详细信息

旅行商问题是组合优化中一个经典的NP-难问题.本文研究旅行商问题的两个变形:带次模惩罚的分组奖励收集旅行商问题和聚集式路旅行商问题.对于带次模惩罚的分组奖励收集旅行商问题,本文首先利用给出的带次模惩罚的分组奖励收集旅行商问题的实例,通过定义合适的权值函数和次模惩罚函数来构作带次模惩罚的奖励收集旅行商问题的实例.然后,将带次模惩罚的奖励收集旅行商问题的已有近似算法的输出解转化为带次模惩罚的分组奖励收集旅行商问题的解,进而设计带次模惩罚的分组奖励收集旅行商问题的近似算法.最后,我们对该近似算法进行理论分析,给出近似比为2k I,其中k是分组的个数,I是最大分组的基数.对于聚集式路旅行商问题,本文分四种情形来考虑.首先,我们设计了路堆叠式起重机问题的近似算法和路乡村邮递员问题的近似算法,而这两个问题是我们求解聚集式路旅行商问题的子问题.然后,基于这些能够解决的子问题并调用路旅行商问题的近似算法,我们设计了聚集式路旅行商问题四种情形下的近似算法,近似比分别为8/3,2,8/3,13/4.

关键词：近似算法聚集式路旅行商问题分组奖励收集旅行商问题次模函数

来源：评论

学校读者我要写书评

暂无评论

LTE/WLAN网络下基于比例公平的资源分配算法研究

引用

电子设计工程 2016年第22期24卷 12-15,19页

作者：俞涵张武雄裴冬赵铖张婷婷上海微系统与信息技术研究所上海200050 上海科技大学上海201210 上海无线通信研究中心上海201210

近年来,为满足移动数据爆发性的增长需求,LTE与WLAN共同组成的异构网络逐渐成为研究的焦点。在这样的场景下,当每个用户同时配备LTE和WLAN收发器时,用户体验更能获得巨大的改善。然而,由于两个系统之间的协同存在障碍,联合管理无线资源... 详细信息

近年来,为满足移动数据爆发性的增长需求,LTE与WLAN共同组成的异构网络逐渐成为研究的焦点。在这样的场景下,当每个用户同时配备LTE和WLAN收发器时,用户体验更能获得巨大的改善。然而,由于两个系统之间的协同存在障碍,联合管理无线资源比较困难。因此,文中考虑同时优化LTE系统中的信道分配和WLAN系统中的用户关联的问题,证明了这两个问题都可以转化成相交拟阵下的次模函数,并利用了一个基于次梯度的算法对这两个问题分别求解,最终通过LTE和WLAN系统中交替使用该优化算法提高全网吞吐量。

关键词：异构网络资源分配比例公平 LTE/WLAN 次模函数

来源：评论

学校读者我要写书评

暂无评论

由多项拟阵函数f所确定的拟阵Mf的秩rf

引用

科学技术与工程 2011年第20期11卷 4671-4673页

作者：吕国亮余保民渭南师范学院数学与信息科学院渭南714000

研究由多项拟阵函数f所确定的拟阵的秩函数rf。先给出由次模函数所确定的拟阵Mf,然后导出多项拟阵函数的秩函数rf的表示式。由此证明了多项拟阵函数f的两个性质,讨论了由二部图导出拟阵M(△)的独立集I(△)和秩函数rf(△)的表示。

关键词：多项拟阵函数秩次模函数 f-平衡集独立集集族A(J)的关联二部图

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithms for Some Stochastic Problems of Combinatorial Optimization

Approximation Algorithms for Some Stochastic Problems of Com...

引用

作者：盛海云南京师范大学

学位级别：硕士

覆盖问题和斯坦纳树问题都是典型的NP困难问题。这些问题有着广泛的应用背景并且是研究的热点问题。在本文中,我们研究的是两阶段有限情形的一些组合优化问题的随机模型。其中包括带次模惩罚的随机集合覆盖问题(带次模惩罚的随机顶点覆... 详细信息

覆盖问题和斯坦纳树问题都是典型的NP困难问题。这些问题有着广泛的应用背景并且是研究的热点问题。在本文中,我们研究的是两阶段有限情形的一些组合优化问题的随机模型。其中包括带次模惩罚的随机集合覆盖问题(带次模惩罚的随机顶点覆盖问题是它的一个特例)和随机prize-collecting斯坦纳树问题。在实际需求出现之前,我们可以在第一阶段选择(购买)一些集合或者边。当实际需求从预先的概率分布中出现时,则会选择(购买)更多的集合或者边来满足实际需求,但是在每一种情形下没有被购买的集合或者边服务的顾客集会产生相应的(次模)惩罚。目标是使第一阶段的购买费用,第二阶段的期望购买费用和期望惩罚费用的和最小化。通过对次模函数构造性质的研究,对带次模惩罚的随机集合覆盖问题,我们给出了2η-近似的原始-对偶算法(当η= 2时,对带次模惩罚的随机顶点覆盖问题给出了4-近似算法),这里η是元素在子集中出现的最大次数。对随机prize-collecting斯坦纳树问题,我们也给出了基于原始-对偶的3-近似算法。

关键词：随机集合覆盖随机prize-collecting斯坦纳树近似算法次模函数

来源：评论

学校读者我要写书评

暂无评论

Submodular Maximization Problems in Combinatorial Optimization

Submodular Maximization Problems in Combinatorial Optimizati...

引用

作者：刘治成南京师范大学

学位级别：硕士

次模函数最大化问题已在机器学习和经济学中得到广泛研究。在论文中,本人考虑了四个与之相关的问题。首先是在线的社会福利问题,其在组合拍卖中具有重要应用,并且也在计算经济学中得到了广泛的研究。在社会福利问题中,我们将具有n个物... 详细信息

次模函数最大化问题已在机器学习和经济学中得到广泛研究。在论文中,本人考虑了四个与之相关的问题。首先是在线的社会福利问题,其在组合拍卖中具有重要应用,并且也在计算经济学中得到了广泛的研究。在社会福利问题中,我们将具有n个物品的集合V划分成m块(S1,S2,…,Sm),然后分配给m个人,使得社会总福利∑i=1m Vi(Si)最大化,其中每个Vi是非负单调次模函数。这个问题也可以转化成次模函数在划分拟阵约束下最大化问题。本人考虑了这个问题的推广形式。每一个划分拟阵的到来都是随机的,然后使用随机算法来最大化目标函数(次模函数)。第二个问题是次模函数分类问题。目标是在基约束的条件下,最大化单调次模函数与满足松弛三角不等式条件的分类函数的和。接下来的两个问题都与两阶段次模函数最大化问题相关。其中一个问题是目标函数由非负的单调次模函数组成,第一阶段具有背包约束,第二阶段满足k拟阵约束。我们给出一个近似比为1/2(1-e-1/k+1)的近似算法。另一个问题目标函数是由非负单调次模函数与非负单调模函数的差构成,第一阶段满足基数约束,第二阶段满足k拟阵约束。本人提出了这个问题的两个双因子算法,一种是确定性算法,另一个是随机算法,可以有效改善了时间复杂度。

关键词：在线拍卖社会福利次模函数分类背包约束拟阵近似算法

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：