计算最少的运算以使两个树结构相同
问题内容:
这更多是一个CS问题,但有趣的是:
假设我们有2个树状结构,其中或多或少地重组了相同的节点。你怎么会找到
- 任何
- 在某种意义上说 极小
操作顺序
MOVE(A, B)
-将节点A移动到节点B下(带有整个子树)INSERT(N, B)
- 在节点B下插入 新 节点NDELETE (A)
-删除节点A(带有整个子树)
将一棵树转化为另一棵树。
显然,在某些情况下不可能进行这种转换,琐碎的操作是将带有子B的根A转换为带有子A的根B等)。在这种情况下,该算法将简单地传递“ 不可能 ” 的结果。
对于网络来说,更通用的版本是通用的,即当我们假设一个节点可以在树中出现多次(有效地具有多个“父级”)时,则禁止循环。
免责声明:这 不是 家庭作业,实际上是来自一个实际的业务问题,我想知道是否有人知道解决方案非常有趣。
问题答案:
不仅有Wikipedia关于图同构的文章(如Space_C0wb0y所指出),而且还有关于图同构问题的专门文章。它有一个Solved special cases
已知多项式时间解的部分。树是其中之一,它引用了以下两个引用:
- PJ Kelly,“树木的同余定理” Pacific J. Math。,7(1957年),第961–968页
- Aho,Alfred V .;约翰·霍普克罗夫特(John Hopcroft);Ullman,Jeffrey D.(1974),《计算机算法的设计和分析》,雷丁,马萨诸塞州:Addison–Wesley。