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

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

图数据库在工程数据中心的应用

为了提升工程建设及运维过程的工作效率和质量,建设覆盖工程全过程的全生命周期工程数据中心具有重大意义。工程数据中心数据建设的特点在于数据之间关联的多样化和复杂化,为适应这样的数据存储需求,采用区别于关系型数据库的图数据库构建工程主数据的存储方案,以维护其复杂多变的关联关系,并为基于图结构数据进行数据分析应用提供了可能。