一种多层级二分图最大匹配问题的快速算法

本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配。该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配。本文针对该匹配问题,提出一个多项式时间的算法,该算法的整体思路是将问题分解为2个经典问题的组合:二分图最大匹配和最大权匹配。这2个经典问题都有成熟的算法可以解决,分别是匈牙利算法和KM算法。算法在组合的过程中采取了贪心策略,在子对象这一层应用最大匹配问题,之后将匹配数作为权值,在父对象这层应用最大权匹配问题,从而得到最终结果。本文给出了其正确性的证明,并对算法的性能进行了实验分析。

量子协同的二分图最大权完美匹配求解方法

信息科学中许多组合优化问题可抽象为二分图最大权完美匹配问题.由于数据量的增长,经典算法难以平衡匹配问题求解效率和求解精度的矛盾.基于此,提出一种适用于求解通用最大权完美匹配的智能优化方法.该方法将原始的矩阵形式的匹配候选解转换成可被智能优化算法处理的演化基结构,通过子代选择和量子策略协同过程,自适应地从改进的离散粒子群策略以及模拟退火策略中选择适用于当前演化过程的有效策略,并在保持种群稳定进化的同时促使种群快速收敛.通过不同类型检验函数以及不同维度匹配矩阵的实验,结果表明:与其他方法相比,该方法在有限迭代次数内具有较高的收敛精度以及较快的收敛速度,体现出对经典问题以及高维匹配问题的适应能力.

图谱和Kuhn-Munkres算法在图匹配中的应用研究

为了对图数据库中的结构化数据进行有效的匹配分析,提出了基于全局结构相似度以及节点位置相似度的Kuhn-Munkres算法。首先对图数据构建全局以及节点位置矩阵,全局相似度矩阵用邻接矩阵的拉普拉斯谱特征构造,位置相似度矩阵首先使用高斯核函数进行节点相对位置的归一化计算,再利用其谱特征构造。节点位置相似度主要描述图所有节点之间的相对位置,弥补了全局结构相似度只刻画图整体结构的不足。最后使用Kuhn-Munkres算法进行图匹配,得到二分图的最大权匹配。实验表明,改进的Kuhn-Munkres算法有效提高了节点之间的匹配正确率。

基于二分图极大权值匹配的SoC故障定位算法研究

针对故障传播给故障定位带来的影响,考虑SoC功能测试系统中的故障源与故障事件之间的不确定性,提出一种基于二分图的故障定位算法。从SoC中抽象出特定的硬件模块,由这些模块构成故障源,结合相应的故障事件组合成二分图,在二分图的基础上生成一种适用于SoC故障定位的故障传播模型(fault propagation model,FPM)。将SoC故障定位的问题转换成二分图极大权值匹配的求解问题,从概率上保证结果的正确性。实验结果表明,故障定位准确率提高了0~21%,误报率下降了0~15%,更加适用于小型系统的故障定位。

基于复合结构的知识库分类体系匹配方法

近年来,分类体系匹配由于其在知识库构建和融合等方面的广泛应用,已成为国内外工业界和学术界的研究热点.然而,随着网络大数据的不断发展,分类体系变得越来越庞大和复杂,构造一种通用有效的分类体系匹配器以适应大规模、异构分类体系匹配的扩展性仍然面临很大的挑战.为此,提出了一种基于复合结构的分类体系匹配方法 BiMWM,该方法利用分类体系中分类的复合结构信息:微观结构和宏观结构,将分类体系匹配问题转化为二部图上的优化问题进行求解.首先,创建赋权的二部图建模分类体系之间候选的匹配类对关系;然后,通过计算二部图上的最大权匹配剪枝选择最优的分类体系的匹配类对.BiMWM方法可以在多项式时间内为2个分类体系产生最优匹配.实验结果表明:与当前先进的基准方法相比,该方法能够有效提升大规模、异构分类体系匹配的性能.

LTE-A网络中D2D通信的资源分配算法研究

该文研究了D2D通信使用LTE-A网络上行链路的资源分配问题。首先将问题建模为混合整数非线性规划问题(MINLP),其次根据待接入用户对各信道的青睐程度计算特征值列表并形成相应联盟。在保证各用户服务质量(QoS)的情况下,利用最大加权二部图匹配(MWBM)方法为待接入网络用户寻找合适的资源及复用的组合。仿真结果表明,该算法打破了D2D用户在数据传输过程中一直处于专用或者复用模式的束缚,扩大了D2D用户对可选用的资源范围,与现有算法相比,可有效提高系统的总速率。

图像多阶特征对集的最优匹配模型

针对图像匹配问题,提出了一种图像多阶特征对集的最优匹配模型.图像的多阶特征主要是指一阶、二阶和三阶特征,分别由单个特征点、特征点之间的边或者连接特征点的三角形来定义.最优匹配模型是一个以图像多阶特征为顶点集的加权二分图,其优点是权重参数可以直接计算,并能采用Kuhn-Munkras算法求解最大权对集.实验结果表明,该模型具有很好的鲁棒性,对于视频序列图像和涂鸦图像,即使在存在较大缩放、旋转和仿射变换的情况下,也能获得比较精确的匹配结果,其准确度通常优于OpenCV中著名的Flann和BruteForce匹配算法.

基于赋权二部图的记录簇匹配模型及其算法

通过一组成员记录表示实体时,相似记录匹配问题被扩展为记录簇匹配问题。提出2种记录簇匹配模式,应用赋权二部图理论建立记录簇匹配数学模型,设计记录簇上下界匹配算法。快速推导出记录簇匹配阈值的上下界,以减少记录簇子记录最大权的匹配次数。实验结果证明该算法能提高记录簇匹配精度和计算效率。

赋权二部图最大匹配的灵敏分析

本文主要从理论上讨论赋权二部图的权的变化对最优解的影响 。

D2D通信中联合链路共享与功率分配算法研究

针对D2D(Device-to-Device,D2D)通信过程中的资源分配问题,提出一种联合链路共享和功率分配算法.在保证系统内蜂窝用户服务质量(Quality of Service,QoS)需求的前提下,利用系统的信道状态信息,为D2D用户生成一个由蜂窝用户组成的通信链路的候选集合;在通信链路候选集合内使用凸优化方法得到D2D用户最优功率分配策略;最后利用(Kuhn-Munkres,KM)算法求解最大加权二部图匹配(Maximum Weight Bipartite Matching,MWBM)问题,为D2D用户选择最优的蜂窝用户进行资源共享.仿真结果表明该算法能有效的提升通信网络的吞吐量,可以为D2D用户选择最优的资源分配策略.

基于多特征融合和图匹配的维汉句子对齐

维吾尔语新闻网页与对应的中文翻译网页在内容上往往并非完全可比,主要表现为双语句子序列的错位甚至部分句子缺失,这给维汉句子对齐造成了困难。此外,作为新闻要素的人名地名很多是未登录词,这进一步增加了维汉句子对齐的难度。为了提高维汉词汇的匹配概率,作者自动提取中文人名、地名并翻译为维吾尔译名,构造双语名称映射表并加入维汉双语词典。然后用维文句中词典词对应的中文译词在中文句中进行串匹配,以避免中文分词错误,累计所有匹配词对得到双语句对的词汇互译率。最后融合数字、标点、长度特征计算双语句对的相似度。在所有双语句子相似度构成的矩阵上,使用图匹配算法寻找维汉平行句对,在900个句对上最高达到95.67%的维汉对齐准确率。

适用于可伸缩视频的D2D网络资源分配方案

对在D2D辅助蜂窝网络中可伸缩视频实时传输中的网络资源分配问题进行研究,提出一个功率分配与频谱共享的优化方案实现用户整体视频质量的最优化。基于可伸缩视频每层的传输速率需求进行单个蜂窝网用户及D2D用户的功率分配,得到最优视频层组合和功率分配方案;基于最大加权二部图匹配方法为D2D用户匹配适当频谱,得到整体资源最优化分配方案。实验结果表明,提案方法在保证D2D用户高接入率的前提下显著提高单个D2D复用所提供的视频质量增益。

传感器网络中一种最大生命周期的路径覆盖算法

路径覆盖是传感器网络覆盖领域的重要问题.已有研究仅针对直线路径情形,分析了节点部署密度与覆盖概率之间的关系.由于目前还不存在多项式时间算法来解决路径覆盖问题,提出了一种新颖的启发式算法.将路径离散成一些点,并将传感器分成可以独立覆盖路径的组,然后利用最大加权二分匹配对组内节点进行调度,从而在覆盖路径的同时最大化网络生命周期.仿真实验考察了网络规模、节点初始能量以及传感器感知半径对网络生命周期的影响.

多用户对双向中继网络的中继和用户选择策略

通过对多用户对多个可选中继组成的双向中继网络进行权重二部图建模,并利用信道状态信息合理设计权重,从而将以最大化系统总速率为目标的中继和用户对选择策略问题等效为权重二部图的最大权匹配问题。利用图论最大权匹配算法(匈牙利算法),提出了最大权匹配选择策略。并进一步同时基于最大权匹配算法和用户对公平性,提出了最大权匹配轮询策略和基于数据序列因子的最大权匹配策略。仿真结果证明,3种策略均提升了系统性能。

二部图最大权匹配的符号ADD算法

利用代数决策图ADD数据结构,在KM算法基础上,提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念,将传统的匹配选择转化成布尔运算,"并行"地搜索匹配集合。实验结果表明:与传统算法相比,该算法可以改善问题的状态空间复杂度。