计算最少的运算以使两个树结构相同 [英] 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
- 任何
- > minimum
- any
- in some sense minimal
操作顺序
-
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 BDELETE (A)- deletes the node A (with the whole subtree)
将一棵树转换为树
显然，在某些情况下，这种转换是不可能的，琐碎的是将根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.
推荐答案
不仅有关于图同构的Wikipedia文章（如Space_C0wb0y所指出的），而且还有关于图同构问题。它有一个已解决的特例，已知多项式时间解。树木就是其中之一，它引用了以下两个引用：
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:
- PJ凯利，树的一个同余定理，《太平洋数学杂志》，7（1957），第961–968页，a。
- Aho，Alfred V .；约翰·霍普克罗夫特（John Hopcroft）； Ullman，Jeffrey D.（1974），《计算机算法的设计和分析》，马萨诸塞州雷丁：Addison-Wesley。
这篇关于计算最少的运算以使两个树结构相同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
