基于图编辑距离的图匹配算法研究

摘要

图编辑距离在图匹配中是一种灵活有效的方法,在图模式识别及相关领域有多种用途,然而,它不同于其它图匹配算法,图编辑距离使得原图的每个节点都可以与另一个图的节点进行匹配,这种特点使得图编辑距离算法更适用于噪声数据,但在另一方面相对于简单图匹配模型它增加了计算复杂度。图编辑距离的空间复杂度与所匹配的两个图的节点数目呈指数关系。这意味着对于大图其编辑距离的计算是很困难的。
　　在本文中,构造出了一种优化的EGED(Exactgrapheditdistance)算法,它利用贪心算法外加代价复杂度剪枝对EGED算法中的搜索树进行了剪枝,同时采用欧氏距离对代价函数进行优化。在实验部分分别对改进的EGED算法,原EGED算法和AGED(Approximategrapheditdistance)算法这三种算法的分类精确度和算法的运行时间进行了效能测试。实验结果证明,首先,本文构造的EGED优化算法相比于原EGED算法和AGED算法显著提高了算法运行速度并降低了编辑操作的代价,使得图之间的相似性衡量更加有效。其次,该优化算法在分类精确度上比起原EGED算法和AGED算法也得到了明显的提高。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1研究背景及意义

1.2国内外研究现状与分析

1.3论文组织结构与技术路线

2 图匹配与图编辑距离的基础理论

2.1图匹配的符号与定义

2.2现有的图匹配方法

2.3图编辑距离概述

2.4图编辑距离的基本定义及性质

2.5 现有图编辑距离算法

2.6本章小结

3 EGED算法的改进与实现

3.1 EGED算法存在的问题

3.2 EGED算法的改进与实现

3.3改进EGED算法的简单效能测试

3.4实验结果

3.5本章小结

4 改进EGED算法在建筑信息模型图匹配中的应用

4.1建筑信息模型

4.2建筑信息模型图匹配过程

4.3实验评估与分析

4.4本章小结

5 总结与展望

5.1主要工作内容

5.2成果及创新点

5.3后续研究建议

致谢

参考文献

攻读硕士期间发表的论文情况