lin*_*llo 19 language-agnostic algorithm edit-distance levenshtein-distance
我只是想知道,对于我们在两个字符串之间有Levenshtein距离(或编辑距离)的字符串,是否有类似于图形的东西？
我的意思是,标识了图来变换原子操作(节点和边的插入/缺失)的数目的标量量度G1到的曲线图G2.
jas*_*n.Z 18
我认为图形编辑距离是您要寻找的尺度.
图形编辑距离测量将图形转换为另一图形的最小图形编辑操作数,允许的图形编辑操作包括:
但是,计算两个图之间的图编辑距离是NP难的.计算它的最有效算法是基于A*的算法,还有其他次优算法.
笔记：
编辑距离（或编辑距离）位于两个字符串之间
但在 Graph 中，您应该在至少 N 个之间进行搜索！您找到每个边和顶点的标识的位置。您可以通过唯一索引轻松比较两个图，但主要问题是定义每个顶点和边的标识。这个问题（找到两个图中可以变换的每个顶点和边的标识）非常困难，被称为同构问题（NP完全）。你可以搜索同构图。