次模函数近似算法求最小颜色生成树(英文) 被引量：1

1

作者 李学良 涂建华 《新疆大学学报（自然科学版）》 CAS 2008年第4期391-394,共4页

给定图G并对其进行边着色,G的最小颜色生成树(MCST)问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论(贪婪... 给定图G并对其进行边着色,G的最小颜色生成树(MCST)问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论(贪婪算法的思想)给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果. 展开更多

关键词 边着色图 最小颜色生成树(MCST) 最大颜色匹配(MCM) 次模函数 近似算法

在线阅读 下载PDF 职称材料

由次模函数f_0所确定的拟阵

2

作者 吕国亮 余保民 《科学技术与工程》 2011年第15期3359-3361,3365,共4页

研究由次模函数f0所确定的拟阵。首先给出由次模函数f所确定的拟阵,讨论了连通拟阵的特征。据此证明了子集XE(G)是C(f0)中成员的充分必要条件。证明了双圈拟阵与由其确定的横贯拟阵的关系。

关键词 次模函数 秩函数 连通拟阵 双圈 横贯 相异代表元系

在线阅读 下载PDF 职称材料

次模函数近似算法求最小弱顶点覆盖 被引量：1

3

作者 涂建华 高昊宇 赖文华 《北京化工大学学报（自然科学版）》 CAS CSCD 北大核心 2011年第1期136-139,共4页

求给定无向图的最小弱顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解。本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解,且近似度为1+ln(d-1),其中d为图的顶点最大度。

关键词 最小弱顶点覆盖 次模函数 近似算法 近似度

在线阅读 下载PDF 职称材料

基于次模函数最大化的测试用例集约简 被引量：1

4

作者 文进 张星宇 +1 位作者 沙朝锋 刘艳君 《计算机科学》 CSCD 北大核心 2021年第12期75-84,共10页

随着软件回归测试规模的不断增大和成本的不断增加,测试用例集约简对于提高软件的回归测试效率显得愈发重要。在选取测试用例子集时,需考虑该子集的代表性和多样性,并采用一个有效的算法来求解。针对该测试用例集约简问题,文中提出了一... 随着软件回归测试规模的不断增大和成本的不断增加,测试用例集约简对于提高软件的回归测试效率显得愈发重要。在选取测试用例子集时,需考虑该子集的代表性和多样性,并采用一个有效的算法来求解。针对该测试用例集约简问题,文中提出了一种基于次模函数最大化的算法SubTSR。尽管引入的离散优化问题是NP-hard问题,但文中利用其目标函数的次模性,采用启发式贪心搜索,求得有近似度保证的次优解。在15个数据集上对SubTSR算法与其他测试用例集约简算法展开实验,针对平均错误检出率、错误检测损失率、首次错误检出位等指标,尝试改变LDA处理中的主题个数以及衡量测试用例相似度的距离,以验证SubTSR算法的有效性。实验结果表明,SubTSR算法在错误检出性能上较其他算法有着较大提升,且在多个数据集上的表现保持相对稳定。在主题个数变化引起文本表示变化时,采用曼哈顿距离的SubTSR算法的性能相较其他算法仍能保持相对稳定。 展开更多

关键词 软件测试 测试用例集约简 错误检测 主题模型 次模函数

在线阅读 下载PDF 职称材料

关于次模函数优化及其应用的综述

5

作者 孙兵 《电子测试》 2020年第21期36-39,51,共5页

为了阐述次模函数在自动摘要、多文档摘要、特征提取、主动学习、传感器放置、图像采集摘等多个领域的广泛应用,通过文献调研及信息研究等方法,对近些年来国内外学者在该研究领域取得的成果进行了系统总结,阐释了次模函数的分类和定义,... 为了阐述次模函数在自动摘要、多文档摘要、特征提取、主动学习、传感器放置、图像采集摘等多个领域的广泛应用,通过文献调研及信息研究等方法,对近些年来国内外学者在该研究领域取得的成果进行了系统总结,阐释了次模函数的分类和定义,在此基础上总结了次模最小化问题、次模最大化问题等相关性问题,重点综述了次模函数的优化和应用。旨在给从事这方面工作的研究人员一个基本的指导,能够为一个完整的次模函数研究贡献自己的一份力量. 展开更多

关键词 次模函数优化

在线阅读 下载PDF 职称材料

大语言模型驱动的知识图谱实体摘要的次模优化方法

6

作者 张琪 钟昊 《计算机科学与探索》 CSCD 北大核心 2024年第7期1806-1813,共8页

知识图谱的规模不断增加,使得实体摘要成为了研究的热点问题。实体摘要的目标是从描述实体的大规模三元结构事实中得到实体的简洁描述。研究的目的是基于大语言模型提出一种次模优化方法用于实体摘要的提取。首先,基于三元组中实体、关... 知识图谱的规模不断增加,使得实体摘要成为了研究的热点问题。实体摘要的目标是从描述实体的大规模三元结构事实中得到实体的简洁描述。研究的目的是基于大语言模型提出一种次模优化方法用于实体摘要的提取。首先,基于三元组中实体、关系和属性的描述信息,采用大语言模型对它们进行嵌入,能够有效地捕捉三元组的语义信息,生成包含丰富语义信息的嵌入向量。其次,基于大语言模型生成的嵌入向量,定义任意两个描述同一实体的三元组事实之间关联度的刻画方法,任意两个三元组之间的关联度越高,表示这两个三元组之间包含的信息越相似。最后,基于上述定义的三元组关联度的刻画方法,定义正规化且单调非减的次模函数,将实体摘要建模为次模函数最大化问题,那么具有性能保证的贪心算法可以直接用于提取实体的摘要。在三个公共基准数据集上进行测试,采用F1值和归一化折损累计增益(NDCG)两个指标对提取的实体摘要的质量进行评估,实验结果表明该方法显著优于当前最先进的方法。 展开更多

关键词 实体摘要 大语言模型 次模函数 贪心算法

在线阅读 下载PDF 职称材料

最大化非减次模集函数问题的近似算法及其性能保证 被引量：1

7

作者 郝自军 何尚录 《西南民族大学学报（自然科学版）》 CAS 2009年第1期35-40,共6页

次模集函数的最值问题在组合优化问题中有广泛应用,次模集函数的增减性对该问题的分析具有一定的简化作用.给出了求解非减次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证.

关键词 组合优化问题 次模集函数 近似算法 性能保证

在线阅读 下载PDF 职称材料

基于次模函数极小化的最优化问题 被引量：4

8

作者 邓素娟 《内江师范学院学报》 2016年第12期29-32,共4页

提出将最优化问题的对偶间隙改写成函数的积分形式,即转化为次模函数极小化问题,再通过Lovász延拓来实现正则化.并实际讨论了基于最接近方法和多面体的最优化问题的次模函数的构造方法,从理论上证明了最优化问题与次模极小化问题... 提出将最优化问题的对偶间隙改写成函数的积分形式,即转化为次模函数极小化问题,再通过Lovász延拓来实现正则化.并实际讨论了基于最接近方法和多面体的最优化问题的次模函数的构造方法,从理论上证明了最优化问题与次模极小化问题之间的等价性关系. 展开更多

关键词 次模函数 最接近方法 多面体 最优化 等价性

在线阅读 下载PDF 职称材料

投资组合对非系统性风险的发散作用——基于单调非增次模集函数的证明 被引量：3

9

作者 陈奕延 李晔 《首都师范大学学报（自然科学版）》 2018年第6期1-4,共4页

风险是客观存在且无法灭失的,有效降低投资中的风险程度是当前研究投资问题的热点之一.通过扩展单调非增次模集函数的性质,利用该性质可证明含多个资产的投资组合对投资中的非系统性风险有发散作用,并用标准差成功对其进行检验.得到结论... 风险是客观存在且无法灭失的,有效降低投资中的风险程度是当前研究投资问题的热点之一.通过扩展单调非增次模集函数的性质,利用该性质可证明含多个资产的投资组合对投资中的非系统性风险有发散作用,并用标准差成功对其进行检验.得到结论:含有多个资产的投资组合的非系统性风险比投资多个资产的非系统性风险的组合更低. 展开更多

关键词 投资组合 风险偏好 非系统性风险 单调非增次模集函数 标准差

在线阅读 下载PDF 职称材料

模糊化拟阵的最新进展 被引量：1

10

作者 史福贵 修振宇 《聊城大学学报（自然科学版）》 2015年第2期1-11,共11页

本文拟对模糊化拟阵理论做一个简短的介绍和评述,试图使读者了解模糊化拟阵理论的最新研究成果.

关键词 模糊化拟阵 模糊化次模函数 基映射 圈映射 模糊化幼阵 模糊化对偶 模糊化自由积

在线阅读 下载PDF 职称材料

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

11

作者 吕国亮 余保民 《科学技术与工程》 2011年第20期4671-4673,共3页

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

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

在线阅读 下载PDF 职称材料

SFExt-PGAbs:两阶段长文档摘要模型

12

作者 周伟枭 蓝雯飞 +1 位作者 许智明 朱容波 《计算机科学与探索》 CSCD 北大核心 2021年第5期907-921,共15页

针对抽取式方法、生成式方法在长文档摘要上的流畅性、准确性缺陷以及在文档编码前截断原始文档造成的重要信息缺失问题,提出一种两阶段长文档摘要模型SFExt-PGAbs,由次模函数抽取式摘要SFExt与指针生成器生成式摘要PGAbs组成。SFExt-PG... 针对抽取式方法、生成式方法在长文档摘要上的流畅性、准确性缺陷以及在文档编码前截断原始文档造成的重要信息缺失问题,提出一种两阶段长文档摘要模型SFExt-PGAbs,由次模函数抽取式摘要SFExt与指针生成器生成式摘要PGAbs组成。SFExt-PGAbs模拟人类对长文档进行摘要的过程,首先使用SFExt在长文档中抽取出重要句子,过滤不重要且冗余的句子形成过渡文档,然后PGAbs接收过渡文档作为输入以生成流畅且准确的摘要。为获取与原始文档中心思想更为接近的过渡文档,在传统SFExt中拓展出位置重要性、准确性两个子方面,同时设计新的贪心算法。为研究不同特征提取器对生成摘要质量的影响,在PGAbs中应用两种循环神经网络。实验结果显示,在CNNDM测试集上,SFExt-PGAbs相较于基线模型生成了更为流畅、准确的摘要,ROUGE指标有较大提升。同时,子方面拓展后的SFExt也能抽取得到更准确的摘要。 展开更多

关键词 两阶段摘要模型 长文档摘要 抽取式摘要 生成式摘要 次模函数 指针生成器 子方面融合

在线阅读 下载PDF 职称材料

关于一类集函数系统的全对偶整性的一个充要条件

13

作者 吴伟良 《华东师范大学学报（自然科学版）》 CAS CSCD 1991年第4期9-14,共6页

设S是有限集,f是定义在S的子集上的实值函数.文章提出了离散凸函数的概念,并指出线性系统x(T)≤f(T),T??S是全对偶整性([4])的充要条件是f的“Dilworth”开拓f是离散凸函数.

关键词 离散凸函数 全对偶整性 次模函数

在线阅读 下载PDF 职称材料

高校应用数学学报──第13卷(1998年)B辑(英文版)第3期目次和提要

14

《高校应用数学学报（A辑）》 CSCD 北大核心 1998年第3期363-364,共2页

高校应用数学学报第１３卷（１９９８年）Ｂ辑（英文版）第３期目次和提要一相Ｓｔｅｆａｎ问题爆破解的一个注记朱宁（苏州大学数学系）该文讨论一相Ｓｔｅｆａｎ问题：ｕｔ＝ｕｘｘ＋ｆ（ｕ，ｔ）ｉｎＱｌ（Ｔ）ｕ（ｘ，０）＝ｕ０（... 高校应用数学学报第１３卷（１９９８年）Ｂ辑（英文版）第３期目次和提要一相Ｓｔｅｆａｎ问题爆破解的一个注记朱宁（苏州大学数学系）该文讨论一相Ｓｔｅｆａｎ问题：ｕｔ＝ｕｘｘ＋ｆ（ｕ，ｔ）ｉｎＱｌ（Ｔ）ｕ（ｘ，０）＝ｕ０（ｘ），０≤ｘ≤Ｑｌ（Ｔ）ｕ（０，... 展开更多

关键词 高校应用数学学报 非线性算子方程组 数学系 英文版 算子子空间 目次 次模函数 微分方程 混合单调 提要 二次文献 爆破解

在线阅读 下载PDF 职称材料

基于贪心组合优化的分布极端不平衡分类算法

15

作者 陈兴国 许静 +1 位作者 李扬 罗玉盘 《小型微型计算机系统》 CSCD 北大核心 2024年第10期2411-2419,共9页

现有针对不平衡数据分类的研究主要从重采样、特征、代价和算法等4个角度展开,方法多样,但针对极端不平衡的数据分布仍缺乏有效算法.本文的目标是通过结合各种算法的特性获取一个最优性能的组合算法.本文假设算法间的组合满足次模函数性... 现有针对不平衡数据分类的研究主要从重采样、特征、代价和算法等4个角度展开,方法多样,但针对极端不平衡的数据分布仍缺乏有效算法.本文的目标是通过结合各种算法的特性获取一个最优性能的组合算法.本文假设算法间的组合满足次模函数性质,并采用贪心的组合优化方法.具体而言,选择深度森林算法为基础,依次组合最优重采样方法、以异常检测思想的特征提取方法对数据进行的特征处理方法或基于贝叶斯优化的最优代价敏感矩阵方法.在3种组合算法中选择分类性能最优的算法组合,再次组合其余角度的方法,判断分类性能是否再次提升.实验选择两组极端不平衡数据——真实饮用水数据和UCI数据库中的page-blocks数据进行验证.结果表明,基于贪心优化对算法间进行组合,在3轮迭代后得到的算法组合,较单一算法其分类性能能有进一步的提升. 展开更多

关键词 次模函数 贪心优化 数据分布极端不平衡 深度森林 组合算法

在线阅读 下载PDF 职称材料

求解非增次模集函数最大值问题的近似算法及其性能保证 被引量：4

16

作者 郝自军 高岳林 何尚录 《数学的实践与认识》 CSCD 北大核心 2008年第12期145-151,共7页

次模集函数的最值问题在组合优化问题中有广泛的应用,给出了求解非增次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证.

关键词 组合优化问题 次模集函数 近似算法 性能保证

原文传递

社会网络中影响力传播的鲁棒抑制方法 被引量：7

17

作者 李劲 岳昆 +1 位作者 张德海 刘惟一 《计算机研究与发展》 EI CSCD 北大核心 2016年第3期601-610,共10页

社会网络中影响力传播的有效抑制是当前社会网络影响力传播机制研究关注的问题之一.针对不确定性、策略性负影响源的影响力传播抑制,讨论社会网络中影响力传播的鲁棒抑制问题.首先,作为提高算法运行效率的有效途径,讨论在竞争性线性阈... 社会网络中影响力传播的有效抑制是当前社会网络影响力传播机制研究关注的问题之一.针对不确定性、策略性负影响源的影响力传播抑制,讨论社会网络中影响力传播的鲁棒抑制问题.首先,作为提高算法运行效率的有效途径,讨论在竞争性线性阈值传播模型下,负种子集传播能力的近似估计方法,以此为基础,提出不确定性负影响源情况下,期望抑制效果最大化的抑制种子集挖掘算法.然后,对于策略性传播源,以最小化最坏情况下的影响力传播范围为目标,基于极小极大优化作为抑制决策准则,提出了一个随机抑制策略的多项式时间近似求解算法.最后,在真实的社会网络数据集上,通过实验验证了所提出方法的有效性. 展开更多

关键词 社会网络 影响力抑制最大化 极小极大原理 近似算法 次模函数

在线阅读 下载PDF 职称材料

双圈拟阵

18

作者 吕国亮 陈斌 《大学数学》 北大核心 2007年第4期80-83,共4页

Sim■es Pereira于1992年提出双圈拟阵.本文讨论了(i)双圈拟阵及其秩函数;(ii)次模函数在双圈拟阵中的应用;(iii)双圈拟阵B(G)的横贯拟阵.主要结果:1°由圈矩阵Bf=[I,Bf12]和圈秩的概念,推出M(f0)为双圈拟阵;2°证明了双圈拟阵B... Sim■es Pereira于1992年提出双圈拟阵.本文讨论了(i)双圈拟阵及其秩函数;(ii)次模函数在双圈拟阵中的应用;(iii)双圈拟阵B(G)的横贯拟阵.主要结果:1°由圈矩阵Bf=[I,Bf12]和圈秩的概念,推出M(f0)为双圈拟阵;2°证明了双圈拟阵B(G)等于由子集族{Av∶v∈V(G)},e与v在G中相关联}所确定的横贯拟阵;3°用不同于Matthews(1977)的方法证明了(iii). 展开更多

关键词 双圈拟阵 次模函数 细分 F-可线性表示拟阵 横贯拟阵 关联矩阵

在线阅读 下载PDF 职称材料

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

19

作者 俞涵 张武雄 +2 位作者 裴冬 赵铖 张婷婷 《电子设计工程》 2016年第22期12-15,19,共5页

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

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

在线阅读 下载PDF 职称材料

基于超图的社交网络中的预算影响力最大化 被引量：2

20

作者 陈彬 帅天平 宋新月 《哈尔滨商业大学学报（自然科学版）》 CAS 2022年第3期343-351,共9页

影响力最大化问题是在线社交网络中的热点问题,然而社交网络的结构错综复杂,传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足,利用有向超图刻画社交用户之间的群体影响,提出一种基于有向超图的预算影响力最大化问题... 影响力最大化问题是在线社交网络中的热点问题,然而社交网络的结构错综复杂,传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足,利用有向超图刻画社交用户之间的群体影响,提出一种基于有向超图的预算影响力最大化问题.该问题是在有向超图的社交网络中,在给定预算下,寻找高影响力用户作为种子节点集,使得其最终的传播范围最大化.分析了该问题是NP-hard的且目标函数是非次模函数,提出了改进的贪婪算法和交换启发式算法进行求解,并分析了改进贪婪算法的近似比.通过将所提的算法应用到三个在线社交网络数据集中进行实验,验证了算法的正确性和良好性能.结果表明,改进贪婪算法基础上的交换启发式算法具有明显的性能优势. 展开更多

关键词 社交网络 预算影响力最大化 有向超图 非次模函数 贪婪算法 启发式算法

在线阅读 下载PDF 职称材料