是否有任何经典算法以最少的步骤将一棵树（或图形）转换为另一棵树

Question

假设我有两个图（在本例中为树）：

graph 1:
    root
        child_1
            leaf_1, leaf_2, leaf_3
        child_2
            leaf_1, leaf_2, leaf_4

graph 2:
    root
        child_1
            leaf_2, leaf_4
        child_2
            leaf_2, leaf_3

我想找到从 graph 1 转换为 graph 2 的最小步骤序列。
我至少有两个选择：

 child_1.delete(leaf_1)
 child_1.delete(leaf_3)
 child_1.add   (leaf_4)

 child_2.delete(leaf_1)
 child_2.delete(leaf_4)
 child_2.add   (leaf_3)

 child_1.delete(leaf_1)

 child_2.delete(leaf_1)

 root  .delete(child_1)
 root  .append(child_1)

那么一般情况下如何求最小序列呢？

Answer 1

这与 图形编辑距离 (GED) 问题 (1, 2) 有关。

这是一个 NP-hard 问题 (3):

Therefore, graph edit distance can also be used to determine the subgraph isomorphism which is NP-Complete.
Then we can derive the following lemma.

Lemma 2.3. GED problem is NP-Hard.

计算 GED 的精确算法通常基于 A* 搜索算法 (3)：

The most widely used method for computing exact graph edit distance is based on the well-known A* algorithm

还有多项式approximate/heuristic算法(1):

Most of them have cubic computational time

对于算法实现，我建议在 Github.

寻找 "graph edit distance"

参考文献：

(1) Graph edit distance（维基百科）
(2) A survey of graph edit distance
(3) Comparing Stars: On Approximating Graph Edit Distance

是否有任何经典算法以最少的步骤将一棵树（或图形）转换为另一棵树

Is there any classical algorithm to transform one tree (or a graph) to another in minimal number of steps

graph-theory

graph-algorithm