图编辑距离概述  

Summary of Graph Edit Distance

作　　者：徐周波[1] 张鵾 宁黎华[1] 古天龙[1] XU Zhou-bo;ZHANG Kun　;NING Li-hua;GU Tian-long(Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China)

机构地区：[1]桂林电子科技大学广西可信软件重点实验室,广西桂林541004

出　　处：《计算机科学》2018年第4期11-18,共8页Computer Science

基　　金：国家自然科学基金(61572146;61363030;U1501252;61762027);广西自然科学基金(2017GXNSFAA198172;2015GXNSFAA139285;2014GXNSFAA118354);桂林电子科技大学研究生教育创新计划项目(2017YJCX08;2017YJCX54)资助

摘　　要：图编辑距离是图模式匹配技术中常用的方法之一。基于图编辑距离的匹配方法能够处理多种类型的图数据,因而受到了学术界的广泛关注。首先介绍了图编辑距离的相关概念;然后简述了基于启发式搜索技术的精确图编辑距离算法,重点分析了基于二分图匹配的近似图编辑距离算法;最后对现存的一些图编辑问题进行了总结,并对未来的发展趋势进行了展望。Graph edit distance is one of the most flexible and general graph pattern matching models available.This matching method has provoked wide concern from scholars owing to its capability to handle many kinds of graph data.Firstly,the related concepts of graph edit distance were introduced.Then the exact graph edit distance algorithms based on heuristic search technology were described briefly,and the inexact edit distance algorithms of bipartite graph matching was emphatically analyzed.Finally,some existing problems were summarized,and the future development trend was simply discussed.

关 键 词：图编辑距离 二分图匹配 A*算法 Hausdorff匹配 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]