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

摘要：通过在piFogBedII中引入移动众包资源,解决了雾计算实验平台用户层设备多样性和移动性问题,但也带来移动众包任务分配的问题,而现有移动众包任务分配机制不适合该平台。基于双向拍卖机制,设计了基于最大匹配的任务(MTM)分配算法,考虑移动用户的偏好,以最大化任务匹配数为目标,并满足诚实性、个体理性和预算平衡性。实验表明,该算法在任务匹配数上有很大提高,同时,具有计算高效性。

摘要：本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为2-2/m,其中m是机器数目。

摘要：介绍几种常见的分词算法,在改进传统的反序词典、优化逆向最大匹配算法的基础上,设计并实现基于逆向最大匹配的中文分词系统,试验证明速度和精度都有显著提高。

摘要：随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。

摘要：通过研究和分析现有最大匹配分词算法,词库结构的设计和分词算法直接关系着分词的速度和效率,提出了一种改进的最大匹配分词算法——基于双字词的动态最大匹配分词算法,设计并实现了汉语分词词库和算法。实验结果表明,此算法相对于现有最大匹配分词算法有显著提高。

摘要：研究随机给定拓扑结构的二阶有向多智能体网络的可控包含控制问题.针对当前包含控制研究成果大多没有考虑多智能体网络领导者和跟随者的可控配置问题,结合复杂网络可控性理论和二分图最大匹配算法给出满足网络可控的领导者和跟随者集合,并为跟随者智能体设计相应的控制协议,驱使跟随者能够渐近收敛到由多个领导者构成的静态凸包中,从而实现网络的可控包含控制.仿真结果验证了理论分析的正确性.

摘要：在参数化CAD设计中,设计者常常遇到判断一个参数化模型是欠、过和完整约束的问题.针对这个问题,提出了一个判断参数化模型的欠、过和完整约束性的图论算法.该算法不仅能够给出判断,同时还能够对欠和过约束的情形进行定位,即能够给出欠和过约束发生的具体位置.这给设计者在设计过程中提供了很大的方便.

摘要：藏文信息化发展至今已经取得了一定的成果,但存在的问题还有许多。藏文文本校对是实现藏文信息处理的基础,是藏文信息处理必不可少的工作。藏文文本校对的内容较广,方面较多,文中主要以藏文文本的词语校对作为研究的目标,通过使用最大匹配算法的思想在不进行分词的情况下对文本的词语作校对。文中对校对算法进行了叙述,并通过实验验证了该方法是可行性和校对效果。

摘要：信息传播算法求解可满足性问题时具有良好的有效性,能使难解区域变窄。在信息传播算法的设计中,是将变量的联合概率分布分解为变量子集上的局部函数的乘积形式。称局部函数为因子(factor),每一个因子依赖于一个变量子集,将变量联合分布的这一因子形式表示为图模型——因子图(factor graph)。信息传播算法是通过因子图上的边传递概率消息,这种消息传递有两种方式:变量结点传递给因子结点的消息和因子结点传递给变量结点的消息。从每个结点传出的消息由传入该结点的消息决定,通过某种迭代策略对消息进行更新。当这种消息迭代过程收敛到某一固定点时,利用某种规则(如,最小熵、最大积、最大匹配)对问题进行求解。本文提出一种利用最大匹配规则求解因子图上的信息传播算法的收敛性及算法迭代步数的上界估计方法,根据对算法的收敛性分析,在对问题解的精确性影响不大的前提下,仅需要给出算法合理的迭代步数或者强迫算法终止,使得算法提前结束,有助于求解可满足性问题算法性能的更进一步优化。