计算使两个树结构相同的最小操作

编程入门行业动态更新时间:2024-10-09 07:21:09

本文介绍了计算使两个树结构相同的最小操作的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

这更像是一个 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

任何

在某种意义上最小

操作顺序

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: