期刊文献+
共找到44篇文章
< 1 2 3 >
每页显示 20 50 100
A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs 被引量:1
1
作者 Tianlong Gu Liang Chang Zhoubo Xu 《International Journal of Communications, Network and System Sciences》 2011年第2期111-121,共11页
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis... The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms. 展开更多
关键词 bipartite graphs weightED matching SYMBOLIC ALGORITHM Algebraic DECISION DIAGRAM (ADD) Ordered Binary DECISION DIAGRAM (OBDD)
下载PDF
IMPROVEMENT AND REALIZATION FOR THE MAXIMUM WEIGHT MATCHING ALGORITHM
2
作者 徐志才 《Journal of Electronics(China)》 1989年第3期220-231,共12页
Some new concepts of effective incidence matrix,ascending order adjacency matrix andend-result vertex are introduced,and some improvements of the maximum weight matchingalgorithm are made.With this method a computer p... Some new concepts of effective incidence matrix,ascending order adjacency matrix andend-result vertex are introduced,and some improvements of the maximum weight matchingalgorithm are made.With this method a computer program in FORTRAN language is realized onthe computers FELIX C-512 and IBM-PC.Good results are obtained in practical operations. 展开更多
关键词 Optimization algorithm for graph maximum weight matching Ascending order ADJACENCY MATRIX End-result MATRIX
下载PDF
面向高速行驶车辆的在线任务卸载决策算法
3
作者 丁爽 曹沐雨 何欣 《计算机科学》 CSCD 北大核心 2024年第2期286-292,共7页
车载边缘计算中的任务卸载决策主要解决任务何时卸载,以及卸载至哪里执行的问题。车辆的高速行驶会造成卸载接入设备频繁变化,卸载通信链路随时可能中断,这要求车辆一旦获得卸载机会,就必须立即做出卸载决策。现有的卸载决策研究专注于... 车载边缘计算中的任务卸载决策主要解决任务何时卸载,以及卸载至哪里执行的问题。车辆的高速行驶会造成卸载接入设备频繁变化,卸载通信链路随时可能中断,这要求车辆一旦获得卸载机会,就必须立即做出卸载决策。现有的卸载决策研究专注于如何最大化任务卸载执行增益,未充分考虑卸载决策时效对卸载策略的影响,导致提出的卸载决策方法的时间复杂度和空间复杂度高,无法用于高速行驶车辆的在线任务卸载决策。为解决上述问题,首先综合考虑卸载决策时效和卸载增益因素的影响,建立高速行驶车辆的任务卸载决策模型,并将其转化为类秘书问题。然后,提出了一种基于加权二部图匹配的在线车载任务卸载决策算法OODA,以协助车辆在依次经过多个异构的边缘服务器时,做出实时的任务卸载决策,并最大化整体卸载执行增益。最后,理论分析OODA算法的竞争比,并采用仿真实验验证该算法的可行性和有效性。 展开更多
关键词 车载边缘计算 任务卸载 秘书问题 加权二部图匹配
下载PDF
一种多层级二分图最大匹配问题的快速算法
4
作者 主令恒 顾丹鹏 +1 位作者 唐松强 陈肖勇 《计算机与现代化》 2024年第6期59-63,102,共6页
本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配。该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配。本文针对该匹配问题... 本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配。该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配。本文针对该匹配问题,提出一个多项式时间的算法,该算法的整体思路是将问题分解为2个经典问题的组合:二分图最大匹配和最大权匹配。这2个经典问题都有成熟的算法可以解决,分别是匈牙利算法和KM算法。算法在组合的过程中采取了贪心策略,在子对象这一层应用最大匹配问题,之后将匹配数作为权值,在父对象这层应用最大权匹配问题,从而得到最终结果。本文给出了其正确性的证明,并对算法的性能进行了实验分析。 展开更多
关键词 二分图 最大匹配 最大权匹配 模式匹配 贪心策略
下载PDF
Graphs Isomorphic to Their Maximum Matching Graphs 被引量:4
5
作者 Yan LIU Gui Ying YAN 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2009年第9期1507-1516,共10页
The maximum matching graph M(G) of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M(G) if they differ by exactly one edge. In this paper, ... The maximum matching graph M(G) of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M(G) if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle. 展开更多
关键词 ISOMORPHIC maximum matching graph bipartite graph factor-critical graph
原文传递
量子协同的二分图最大权完美匹配求解方法 被引量:9
6
作者 印桂生 崔晓晖 +2 位作者 董红斌 董宇欣 崔香 《计算机研究与发展》 EI CSCD 北大核心 2014年第11期2573-2584,共12页
信息科学中许多组合优化问题可抽象为二分图最大权完美匹配问题.由于数据量的增长,经典算法难以平衡匹配问题求解效率和求解精度的矛盾.基于此,提出一种适用于求解通用最大权完美匹配的智能优化方法.该方法将原始的矩阵形式的匹配候选... 信息科学中许多组合优化问题可抽象为二分图最大权完美匹配问题.由于数据量的增长,经典算法难以平衡匹配问题求解效率和求解精度的矛盾.基于此,提出一种适用于求解通用最大权完美匹配的智能优化方法.该方法将原始的矩阵形式的匹配候选解转换成可被智能优化算法处理的演化基结构,通过子代选择和量子策略协同过程,自适应地从改进的离散粒子群策略以及模拟退火策略中选择适用于当前演化过程的有效策略,并在保持种群稳定进化的同时促使种群快速收敛.通过不同类型检验函数以及不同维度匹配矩阵的实验,结果表明:与其他方法相比,该方法在有限迭代次数内具有较高的收敛精度以及较快的收敛速度,体现出对经典问题以及高维匹配问题的适应能力. 展开更多
关键词 二分图 最大权 完美匹配 量子协同 匹配候选解转换
下载PDF
图谱和Kuhn-Munkres算法在图匹配中的应用研究 被引量:8
7
作者 李昌华 李智杰 高阳 《计算机工程与科学》 CSCD 北大核心 2017年第10期1896-1900,共5页
为了对图数据库中的结构化数据进行有效的匹配分析,提出了基于全局结构相似度以及节点位置相似度的Kuhn-Munkres算法。首先对图数据构建全局以及节点位置矩阵,全局相似度矩阵用邻接矩阵的拉普拉斯谱特征构造,位置相似度矩阵首先使用高... 为了对图数据库中的结构化数据进行有效的匹配分析,提出了基于全局结构相似度以及节点位置相似度的Kuhn-Munkres算法。首先对图数据构建全局以及节点位置矩阵,全局相似度矩阵用邻接矩阵的拉普拉斯谱特征构造,位置相似度矩阵首先使用高斯核函数进行节点相对位置的归一化计算,再利用其谱特征构造。节点位置相似度主要描述图所有节点之间的相对位置,弥补了全局结构相似度只刻画图整体结构的不足。最后使用Kuhn-Munkres算法进行图匹配,得到二分图的最大权匹配。实验表明,改进的Kuhn-Munkres算法有效提高了节点之间的匹配正确率。 展开更多
关键词 Kuhn-Munkres算法 相似度矩阵 二分图 最大权匹配
下载PDF
基于二分图极大权值匹配的SoC故障定位算法研究 被引量:3
8
作者 张鹏 朱利 杜小智 《计算机应用研究》 CSCD 北大核心 2017年第1期79-82,共4页
针对故障传播给故障定位带来的影响,考虑SoC功能测试系统中的故障源与故障事件之间的不确定性,提出一种基于二分图的故障定位算法。从SoC中抽象出特定的硬件模块,由这些模块构成故障源,结合相应的故障事件组合成二分图,在二分图的基础... 针对故障传播给故障定位带来的影响,考虑SoC功能测试系统中的故障源与故障事件之间的不确定性,提出一种基于二分图的故障定位算法。从SoC中抽象出特定的硬件模块,由这些模块构成故障源,结合相应的故障事件组合成二分图,在二分图的基础上生成一种适用于SoC故障定位的故障传播模型(fault propagation model,FPM)。将SoC故障定位的问题转换成二分图极大权值匹配的求解问题,从概率上保证结果的正确性。实验结果表明,故障定位准确率提高了0~21%,误报率下降了0~15%,更加适用于小型系统的故障定位。 展开更多
关键词 故障传播 二分图模型 极大权值匹配 SoC故障定位
下载PDF
文本相似度计算在主观题评分中的应用 被引量:6
9
作者 程传鹏 齐晖 《计算机工程》 CAS CSCD 2012年第5期288-290,共3页
针对传统主观题自动评分准确度低的问题,提出一种基于文本相似度计算的主观题评分方法。利用扩展的《同义词词林》计算词语之间的相似度,根据标准答案中的词语和学生答卷中的词语以及词语之间的相似度构造二部图,通过二部图的最大匹配... 针对传统主观题自动评分准确度低的问题,提出一种基于文本相似度计算的主观题评分方法。利用扩展的《同义词词林》计算词语之间的相似度,根据标准答案中的词语和学生答卷中的词语以及词语之间的相似度构造二部图,通过二部图的最大匹配算法获得标准答案和学生答案的相似度。实验结果表明,该方法可以给主观题评分提供一个较好的参考。 展开更多
关键词 自动评分 文本相似度 二部图 匈牙利算法 最大匹配
下载PDF
基于复合结构的知识库分类体系匹配方法 被引量:1
10
作者 林海伦 贾岩涛 +3 位作者 王元卓 靳小龙 程学旗 王伟平 《计算机研究与发展》 EI CSCD 北大核心 2017年第1期50-62,共13页
近年来,分类体系匹配由于其在知识库构建和融合等方面的广泛应用,已成为国内外工业界和学术界的研究热点.然而,随着网络大数据的不断发展,分类体系变得越来越庞大和复杂,构造一种通用有效的分类体系匹配器以适应大规模、异构分类体系匹... 近年来,分类体系匹配由于其在知识库构建和融合等方面的广泛应用,已成为国内外工业界和学术界的研究热点.然而,随着网络大数据的不断发展,分类体系变得越来越庞大和复杂,构造一种通用有效的分类体系匹配器以适应大规模、异构分类体系匹配的扩展性仍然面临很大的挑战.为此,提出了一种基于复合结构的分类体系匹配方法 BiMWM,该方法利用分类体系中分类的复合结构信息:微观结构和宏观结构,将分类体系匹配问题转化为二部图上的优化问题进行求解.首先,创建赋权的二部图建模分类体系之间候选的匹配类对关系;然后,通过计算二部图上的最大权匹配剪枝选择最优的分类体系的匹配类对.BiMWM方法可以在多项式时间内为2个分类体系产生最优匹配.实验结果表明:与当前先进的基准方法相比,该方法能够有效提升大规模、异构分类体系匹配的性能. 展开更多
关键词 知识库 分类体系匹配 复合结构 二部图 最大权匹配
下载PDF
用二分图实现数据发布的隐私保护 被引量:1
11
作者 兰丽辉 鞠时光 +1 位作者 金华 李昊 《计算机应用研究》 CSCD 北大核心 2010年第11期4303-4305,4308,共4页
基于表存储而发布的数据虽然可以实现隐私保护,但是由于表中记录相互独立,使得个体间的关联信息在发布中缺失,影响发布数据的效用。提出采用二分图的形式对数据进行发布,将顶点划分为两类,把带有标签的顶点按聚类方法进行分组,根据聚类... 基于表存储而发布的数据虽然可以实现隐私保护,但是由于表中记录相互独立,使得个体间的关联信息在发布中缺失,影响发布数据的效用。提出采用二分图的形式对数据进行发布,将顶点划分为两类,把带有标签的顶点按聚类方法进行分组,根据聚类分组结果对另外一个顶点集进行最大匹配分组,通过隐藏个体和顶点的映射关系,保证两类个体间关系的安全发布。基于聚类的最大匹配分组方法既实现了隐私的保护又增加了发布数据的效用。 展开更多
关键词 隐私保护 数据发布 二分图 最大匹配
下载PDF
LTE-A网络中D2D通信的资源分配算法研究 被引量:11
12
作者 钱志鸿 阎双叶 +1 位作者 田春生 王鑫 《电子与信息学报》 EI CSCD 北大核心 2018年第10期2287-2293,共7页
该文研究了D2D通信使用LTE-A网络上行链路的资源分配问题。首先将问题建模为混合整数非线性规划问题(MINLP),其次根据待接入用户对各信道的青睐程度计算特征值列表并形成相应联盟。在保证各用户服务质量(QoS)的情况下,利用最大加权二部... 该文研究了D2D通信使用LTE-A网络上行链路的资源分配问题。首先将问题建模为混合整数非线性规划问题(MINLP),其次根据待接入用户对各信道的青睐程度计算特征值列表并形成相应联盟。在保证各用户服务质量(QoS)的情况下,利用最大加权二部图匹配(MWBM)方法为待接入网络用户寻找合适的资源及复用的组合。仿真结果表明,该算法打破了D2D用户在数据传输过程中一直处于专用或者复用模式的束缚,扩大了D2D用户对可选用的资源范围,与现有算法相比,可有效提高系统的总速率。 展开更多
关键词 无线通信 D2D通信 资源分配 最大加权二部图匹配
下载PDF
应用网络流模型解决航班衔接问题 被引量:11
13
作者 孙宏 《西南交通大学学报》 EI CSCD 北大核心 2002年第2期223-226,共4页
针对单枢纽机场航线结构的特点 ,以所需飞机数最少为目标 ,提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题 ,并建立一个描述航班节衔接问题的二部图 ,将航班衔接问题转化为二部图的最大匹... 针对单枢纽机场航线结构的特点 ,以所需飞机数最少为目标 ,提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题 ,并建立一个描述航班节衔接问题的二部图 ,将航班衔接问题转化为二部图的最大匹配问题 ,然后由二部图生成一个具有单源汇网络特征的辅助图 ,利用Ford Fulkerson算法求该网络的最大流 ,进而得到二部图的最大匹配 ,从而得到了一个需用飞机数最少的航班节衔接方案 ,为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限 ,可以得出不同的航班衔接方案 ,为制订生产计划提供了必要的灵活性。 展开更多
关键词 航班衔接 单枢纽航线结构 二部图 最大匹配 Ford-Fulkerson算法 网络流模型 图论模型
下载PDF
基于施工效能最大化的多设备多任务匹配研究 被引量:1
14
作者 晋良海 周律豪 +2 位作者 韩兰珍 谢慧云 陈雁高 《水电能源科学》 北大核心 2015年第1期150-153,共4页
在工程施工组织中,多设备多任务调度方案对作业效率和施工效能影响很大。考虑多设备多任务施工系统特性,假设施工调度是发生在某一特定时段的无后效过程,确定不同调度方案下设备—任务匹配的权重,生成赋权二部图匹配模型,利用Kuhn-Munk... 在工程施工组织中,多设备多任务调度方案对作业效率和施工效能影响很大。考虑多设备多任务施工系统特性,假设施工调度是发生在某一特定时段的无后效过程,确定不同调度方案下设备—任务匹配的权重,生成赋权二部图匹配模型,利用Kuhn-Munkras算法求解某个时段内的最大权匹配,实现施工效能最大化。实例应用结果表明,该模型能有效提高作业效率及作业面利用率、减少窝工损失、提升效能,可供同类工程辅助决策参考。 展开更多
关键词 施工效能 施工调度 权重 二部图匹配 Kuhn-Munkras算法
下载PDF
二部图最大匹配的快速动态优化算法 被引量:3
15
作者 李洪波 翟金刚 《鲁东大学学报(自然科学版)》 2006年第3期168-170,177,共4页
建立了二部图G=(V,U,E)的二级优先匹配规则,在此规则下,用改进的深度优先搜索对匹配算法进行改进,使得算法能够根据连通分量的个数动态优化算法的性能,使动态最大匹配算法的时间复杂度提高到O(max(|V|,|E|,m|U|)).
关键词 二部图 最大匹配 二级优先 动态深度优先搜索
下载PDF
网络评价倾向性研究 被引量:2
16
作者 程传鹏 《计算机工程与应用》 CSCD 北大核心 2011年第25期156-159,共4页
提出了基于语义相似度判别用户评价倾向的方法。利用同义词词林计算词语的相似度,由词语的相似度构造二部图,通过求二部图的最大匹配获得文本之间的相似度。依据KNN分类来判断文本的倾向性。实验结果表明该方法优于传统的倾向性判断的... 提出了基于语义相似度判别用户评价倾向的方法。利用同义词词林计算词语的相似度,由词语的相似度构造二部图,通过求二部图的最大匹配获得文本之间的相似度。依据KNN分类来判断文本的倾向性。实验结果表明该方法优于传统的倾向性判断的方法。 展开更多
关键词 同义词词林 K-最近邻(KNN)分类 文本相似度 二部图 最大匹配
下载PDF
求偶图最大匹配的矩阵算法 被引量:2
17
作者 代西武 李群高 《北京建筑工程学院学报》 2003年第2期75-78,共4页
深入研究了偶图与其简化邻接矩阵之间的关系 ,提出了 (0 ,1 ) -矩阵的无关元对角形概念 ,利用此概念给出了定理“任一 (0 ,1 ) -矩阵的项秩与线秩相等”的一种直接简单证明 ,得到了判断 (0 ,1 ) -矩阵的无关元集为最大无关元集的充要条... 深入研究了偶图与其简化邻接矩阵之间的关系 ,提出了 (0 ,1 ) -矩阵的无关元对角形概念 ,利用此概念给出了定理“任一 (0 ,1 ) -矩阵的项秩与线秩相等”的一种直接简单证明 ,得到了判断 (0 ,1 ) -矩阵的无关元集为最大无关元集的充要条件。最后给出了寻找偶图最大匹配的算法———矩阵算法 。 展开更多
关键词 偶图 匹配 矩阵算法 无关元集 计算机
下载PDF
图像多阶特征对集的最优匹配模型
18
作者 李玉鑑 阳勇 尹创业 《北京工业大学学报》 CAS CSCD 北大核心 2013年第11期1680-1687,共8页
针对图像匹配问题,提出了一种图像多阶特征对集的最优匹配模型.图像的多阶特征主要是指一阶、二阶和三阶特征,分别由单个特征点、特征点之间的边或者连接特征点的三角形来定义.最优匹配模型是一个以图像多阶特征为顶点集的加权二分图,... 针对图像匹配问题,提出了一种图像多阶特征对集的最优匹配模型.图像的多阶特征主要是指一阶、二阶和三阶特征,分别由单个特征点、特征点之间的边或者连接特征点的三角形来定义.最优匹配模型是一个以图像多阶特征为顶点集的加权二分图,其优点是权重参数可以直接计算,并能采用Kuhn-Munkras算法求解最大权对集.实验结果表明,该模型具有很好的鲁棒性,对于视频序列图像和涂鸦图像,即使在存在较大缩放、旋转和仿射变换的情况下,也能获得比较精确的匹配结果,其准确度通常优于OpenCV中著名的Flann和BruteForce匹配算法. 展开更多
关键词 图像匹配 多阶特征 加权二分图 最大权对集 Kuhn—Munkras算法
下载PDF
面向子流的低延迟数据调度算法
19
作者 吴国福 窦强 +1 位作者 吴吉庆 窦文华 《计算机工程与科学》 CSCD 北大核心 2012年第5期7-12,共6页
P2P流媒体是分发流媒体数据的高效方式,而数据传输延迟是决定P2P流媒体系统性能的重要参数。在分析"拉"模式数据调度模式传输延迟的基础上,本文在"推"、"拉"混合的调度模式下提出一种新的面向子流的低延... P2P流媒体是分发流媒体数据的高效方式,而数据传输延迟是决定P2P流媒体系统性能的重要参数。在分析"拉"模式数据调度模式传输延迟的基础上,本文在"推"、"拉"混合的调度模式下提出一种新的面向子流的低延迟数据调度算法。首先子流的调度问题被转换成等价的带权二部图匹配问题,其次针对转换后的二部图改进匈牙利算法,提出最小延迟、最大匹配的启发式匹配算法。该算法在保证最大匹配的同时使得每条子流的延迟尽可能地低。模拟实验表明本文的算法能够极大降低数据传输延迟。 展开更多
关键词 P2P流媒体 数据调度 子流 带权二部图 匹配
下载PDF
基于赋权二部图的记录簇匹配模型及其算法
20
作者 陈波 王延章 《计算机工程》 CAS CSCD 北大核心 2009年第24期60-62,共3页
通过一组成员记录表示实体时,相似记录匹配问题被扩展为记录簇匹配问题。提出2种记录簇匹配模式,应用赋权二部图理论建立记录簇匹配数学模型,设计记录簇上下界匹配算法。快速推导出记录簇匹配阈值的上下界,以减少记录簇子记录最大权的... 通过一组成员记录表示实体时,相似记录匹配问题被扩展为记录簇匹配问题。提出2种记录簇匹配模式,应用赋权二部图理论建立记录簇匹配数学模型,设计记录簇上下界匹配算法。快速推导出记录簇匹配阈值的上下界,以减少记录簇子记录最大权的匹配次数。实验结果证明该算法能提高记录簇匹配精度和计算效率。 展开更多
关键词 信息集成 记录簇匹配 二部图最大权匹配
下载PDF
上一页 1 2 3 下一页 到第
使用帮助 返回顶部