一种高效的图编辑距离计算方法

摘要

图编辑距离是用来衡量图相似性的一个重要方法,在很多领域都有应用。图编辑距离问题是NP-Hard问题,现有图编辑距离算法主要基于顶点映射搜索,由于搜索空间大,时间和空间效率较低。本文提出一个高效的基于A*的图编辑距离算法,针对图对称性引起的映射冗余问题,利用Symmetry-Breaking方法,通过减少扩展映射数量,提高算法的运行效率。最后,在真实数据集上进行实验,实验结果验证了其优化效果。