两图之间的编辑距离 [英] Edit distance between two graphs

问题描述

我只是想知道，如果，像我们有Levenshtein距离两个字符串之间（或编辑距离）的字符串，是有相似的图形的东西吗？

I'm just wondering if, like for strings where we have the Levenshtein distance (or edit distance) between two strings, is there something similar for graphs?

我的意思是，一个标量的措施，确定原子操作的数量（节点和边插入/删除），以变换曲线 G1 来图 G2 。

I mean, a scalar measure that identifies the number of atomic operations (node and edges insertion/deletion) to transform a graph G1 to a graph G2.

推荐答案

我觉得图形编辑距离就是你要找的措施。

I think graph edit distance is the measure that you were looking for.

格拉夫编辑距离测量图形编辑操作的最小数量来变换一个图形至另一个，并且允许的图形编辑操作，包括：

Graph edit distance measures the minimum number of graph edit operations to transform one graph to another, and the allowed graph edit operations includes:

• 插入/删除孤立点
• 插入/删除一边
• 更改顶点/边的标签（如果标记图）

然而，计算两个图形之间的图形编辑距离是NP难。最有效的算法计算，这是一甲*的算法，并有其它次优算法。

However, computing the graph edit distance between two graphs is NP-hard. The most efficient algorithm for computing this is an A*-based algorithm, and there are other sub-optimal algorithms.

这篇关于两图之间的编辑距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！