共查询到20条相似文献,搜索用时 62 毫秒
1.
在逻辑验证和综合中,布尔匹配利用有序二叉判定图OBDD来检验两个给定的逻辑函数是否相等。为了提高匹配算法的效率,文中用最小项数作为标签标定变量(变量组)。对比两函数中变量(变量组)的“标签”,可以删除不可能的排序,从而加快匹配过程。在提取变量标签时,提出简约二分决策图-SBDD,并利用其节点少的特性进一步提高“标签”提取算法的效率。实验结果表明本算法执行速度快,变量区分能力强。 相似文献
2.
本文对具有高通讯延迟的多处理机系统(机群系统)上的任务调度算法进行了研究,与以往算法主要考虑任务图的关键路径不同,本文给出了任务图的调度与其偶图匹配的对应关系,并由此提出了一种新的启发式算法,通过模拟试验显示本算法具有较好的调度效果。 相似文献
3.
4.
《计算机应用与软件》2018,(1)
生物蛋白质相互作用网络,简称PPI网络,是一种生物信息学中用来表示蛋白质之间相互作用关系的图模型。不同物种PPI网络之间的比对,有着重要的生物学意义,一个好的PPI网络比对算法,显得尤为重要。针对该问题,首次提出了LOBM(Local Optimization based on Bipartite graph Matching)算法。LOBM是一种能够局部优化既有比对结果,并且利用二分图匹配这一经典图论模型,来提高既有比对算法的比对效果。实验表明,LOBM相比一些现有的比对算法,在比对结果上有较大的提升。 相似文献
5.
基于二分图最优匹配算法的毕业论文选题系统 总被引:3,自引:1,他引:2
本文在介绍毕业论文选题系统的系统用例、功能模块和流程图的基础上,针对学生选题不均衡这一突出问题,引入了二分图最优匹配的经典算法—KM算法,该算法能够根据学生的题目预选、自命题、未定题等多种情况,完成题目与学生的智能匹配,使最终题目的整体满意度最高,从而提高学生的毕业论文选题质量。该系统在武汉科技大学管理学院04级毕业论文选题中实施效果良好。 相似文献
6.
针对位置服务中的身份隐私泄露问题,提出了一种基于二分图的身份推理攻击算法。其基本思想是构建移动用户真实身份和假名间的有权二分图,运用Kuhn-Munkres算法找到其最佳完美匹配,确定用户的真实身份完成攻击。通过实验验证了该算法的有效性,并分析了隐私保护机制、位置服务隐私泄露率和假名生存期等因素对算法的影响。 相似文献
7.
8.
9.
徐雯 《数字社区&智能家居》2012,(7X):5178-5180
在中型组足球机器人的决策模型中,用状态自动机模型实现了Robocup中机器人各个角色的决策过程,形成了决策知识库。根据比赛场上的信息,调用知识库,利用二分图最佳匹配算法的思想来实现角色分配,提高队伍的成绩。 相似文献
10.
对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O(n^3),但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O(n*degree(n)),degree(n)为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。 相似文献
11.
一种基于图模式匹配的逻辑单元映射算法 总被引:2,自引:2,他引:0
基于数学中图模式匹配的概念,根据电路特征在于图同构算法中加入图约束条件,研究了针对不同结构的FPGA逻辑单元都能适用的映射算法FDUMap.实验中应用FDUMap将测试电路映射到不同的逻辑单元中,该算法比现有的专用的逻辑单元映射算法通用性更好,而平均性能上仅相差3%。 相似文献
12.
13.
14.
信息科学中许多组合优化问题可抽象为二分图最大权完美匹配问题.由于数据量的增长,经典算法难以平衡匹配问题求解效率和求解精度的矛盾.基于此,提出一种适用于求解通用最大权完美匹配的智能优化方法.该方法将原始的矩阵形式的匹配候选解转换成可被智能优化算法处理的演化基结构,通过子代选择和量子策略协同过程,自适应地从改进的离散粒子群策略以及模拟退火策略中选择适用于当前演化过程的有效策略,并在保持种群稳定进化的同时促使种群快速收敛.通过不同类型检验函数以及不同维度匹配矩阵的实验,结果表明:与其他方法相比,该方法在有限迭代次数内具有较高的收敛精度以及较快的收敛速度,体现出对经典问题以及高维匹配问题的适应能力. 相似文献
15.
二部图作为一种非常重要的数据结构有很多特殊性质,针对文献[4]中的二部图的所有极大匹配求解算法,给出了反例证明了该算法是错误的,同时证明了二部图的所有极大匹配的求解是NP难问题. 相似文献
16.
针对二部图完美匹配问题,提出了一种基于DNA计算自组装模型的算法.首先,通过该算法求解了一个具有10个顶点的二部图完美匹配问题的实例,实例中给出DNA计算自组装模型算法所涉及到的DNA Tile的编码设计方案、自组装计算步骤及结果分析;然后,给出了任意二部图完美匹配问题的求解方案;最后,针对DNA计算自组装模型算法解决任意二部图完美匹配问题的时间和空间消耗进行了讨论.结果表明:对任意二部图只需14种Tile类型就能够得到完美匹配. 相似文献
17.
18.
基于二分图匹配的语义Web服务发现方法 总被引:15,自引:0,他引:15
如何从大规模服务集合中快速而准确的发现目标服务是应用Web服务技术的关键.现有基于语义的Web服务发现方法应用实施难度大且效果存在较大提升空间.文中首先提出了Web服务注册的信息模型,该模型不受限于具体的Web服务模型和表达语言,支持接口语义标注和接口依赖关系的申明.进而提出了基于二分图匹配的语义Web服务发现方法,通过对二分图最佳匹配进行扩展,将服务匹配问题转化成二分图的扩展最佳匹配的求解问题,支持服务接口之间的依赖关系,从而提高服务发现的效果.一系列仿真实验表明文中方法不仅能较大提高服务发现的召回率和准确率,而且还能以线性时间复杂度满足用户请求. 相似文献
19.
20.
一个基于DFS编码的图形匹配算法 总被引:1,自引:0,他引:1
快速有效的图形查询是图形数据库成功应用的关键。文章利用图的词典顺序,用唯一的最小DFS(深度优先搜索)编码表示每个图。根据两个图同构当且仅当它们的最小DFS编码相同这一性质,将图形匹配转化为图的最小DFS编码的比较:在判断两个标记图形是否同构时,可以先求出图的最小DFS编码,再用有效的匹配算法进行比较。 相似文献