计算使两个树结构相同的最小操作 [英] Calculate minimal operations to make two tree structures identical

问题描述

这更像是一个 CS 问题，但很有趣:

This is more of a CS question, but an interesting one :

假设我们有 2 个树结构，其中重组了或多或少相同的节点.你怎么找

Let's say we have 2 tree structures with more or less the same nodes reorganized. How would you find

1. 任何
2. 在某种意义上最小

操作顺序

• MOVE(A, B) - 将节点 A 移动到节点 B 下(包括整个子树)
• INSERT(N, B) - 在节点 B 下插入一个 新 节点 N
• DELETE (A) - 删除节点 A(包括整个子树)

• MOVE(A, B) - moves node A under node B (with the whole subtree)
• INSERT(N, B) - inserts a new node N under node B
• DELETE (A) - deletes the node A (with the whole subtree)

将一棵树变成另一棵树.

that transforms one tree to the other.

显然在某些情况下这种转换是不可能的，比如根 A 和孩子 B 到根 B 和孩子 A 等等).在这种情况下，算法只会给出不可能"的结果.

There might obviously be cases where such transformation is not possible, trivial being root A with child B to root B with child A etc.). In such cases, the algorithm would simply deliver an result "not possible".

更壮观的版本是网络的泛化，即当我们假设一个节点可以在树中多次出现(实际上有多个父节点")，而循环是被禁止的.

Even more spectacular version is a generalization for networks, i.e. when we assume that a node can occur multiple times in the tree (effectively having multiple "parents"), while cycles are forbidden.

免责声明:这不是作业，实际上它来自一个真正的业务问题，我发现这很有趣，想知道是否有人可能知道解决方案.

Disclaimer : This is not a homework, actually it comes from a real business problem and I found it quite interesting wondering if somebody might know a solution.

推荐答案

不仅有一篇关于图同构的维基百科文章(正如 Space_C0wb0y 指出的)，还有一篇关于 图同构问题.它有一个部分已解决的特殊情况，其中多项式时间的解决方案是已知的.Trees 就是其中之一，它引用了以下两个参考文献:

There is not only a Wikipedia article on graph isomorphism (as Space_C0wb0y points out) but also a dedicated article on the graph isomorphism problem. It has a section Solved special cases for which polynomial-time solutions are known. Trees is one of them and it cites the following two references:

• P.J.凯利，树的同余定理"太平洋 J. 数学，7 (1957) pp. 961–968
• 啊，阿尔弗雷德 V.；霍普克罗夫特，约翰；Ullman, Jeffrey D. (1974)，计算机算法的设计和分析，雷丁，马萨诸塞州:Addison–Wesley.

这篇关于计算使两个树结构相同的最小操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！