1

想象一下，给定一组树ST，每棵树的每个顶点都被标记。还给出了另一棵树T（也带有标签顶点）。问题是我怎样才能找到 ST的哪些树可以从T的根开始跨越树T，使得生成树T ' 的顶点的标签与T的顶点的标签一致。注意T的每个顶点的子节点应完全覆盖或根本不覆盖 - 不允许部分覆盖儿童。换句话说：给定一棵树和以下过程：选择一个顶点并删除该顶点下方的所有顶点和边（顶点本身除外）。找到ST的那些树，使得每棵树都是通过一系列应用于T的过程生成的。例如给定树T

在此处输入图像描述

树

在此处输入图像描述 在此处输入图像描述

在此处输入图像描述 在此处输入图像描述

覆盖 T 和树

在此处输入图像描述

不是因为这棵树有孩子 3, 5 不像 T 有 2, 3 作为孩子。我能想到的最好的事情是要么暴力破解它，要么找到一组树，其中每一个都具有与 T 相同的根标签，然后在这些树中搜索答案，但我猜这两个都不是方法是最优的。我正在考虑以某种方式对树木进行散列，但没有任何结果。有什么想法吗？

笔记：

  • 树不一定是二元的
  • 一棵树T可以覆盖另一棵树T'如果它们共享一个根
  • 树是有序的，这意味着您不能交换任何两个孩子的位置。

TL; DR找到一个有效的算法，在查询给定树T时，该算法从给定（固定/静态）集合ST中找到所有能够覆盖T的树。

4

2 回答 2

1

我将草拟一个答案，然后提供一些工作源代码。

首先，您需要一种算法来散列树。我们可以假设，不失一般性，每个树节点的子节点是从最小到最大排序的（反之亦然）。

在ST的每个成员上运行此算法并保存哈希值。

现在，获取您的测试树T并生成其所有保留原始根的子树TP 。您可以通过以下方式执行此操作（可能效率低下）：

  1. 制作一组S的节点
  2. 生成S的幂集P
  3. 通过从T的副本中删除P的每个成员中存在的节点来生成子树
  4. 将保留原始根的那些子树添加到TP。

现在生成一组TP的所有哈希值。

现在检查您的每个ST散列是否属于TP。

ST哈希存储需要STO(n)中的空间，并且可能需要保存树的空间。

您可以优化会员代码，使其不需要存储空间（我的测试代码中没有这样做）。该代码将需要大约 2 N 次检查，其中N是 **T 中的节点数。

所以算法在 中运行O(H 2**N)，其中H是ST的大小，N是T中的节点数。加快速度的最佳方法是找到一种改进的算法来生成T的子树。

下面的 Python 代码实现了这一点：

#!/usr/bin/python
import itertools
import treelib
import Crypto.Hash.SHA
import copy

#Generate a hash of a tree by recursively hashing children
def HashTree(tree):
  digester=Crypto.Hash.SHA.new()

  digester.update(str(tree.get_node(tree.root).tag))

  children=tree.get_node(tree.root).fpointer
  children.sort(key=lambda x: tree.get_node(x).tag, cmp=lambda x,y:x-y)

  hash=False
  if children:
    for child in children:
      digester.update(HashTree(tree.subtree(child)))
    hash = "1"+digester.hexdigest()
  else:
    hash = "0"+digester.hexdigest()

  return hash

#Generate a power set of a set
def powerset(iterable):
  "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
  s = list(iterable)
  return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

#Generate all the subsets of a tree which still share the original root
#by using a power set of all the tree's nodes to remove nodes from the tree
def TreePowerSet(tree):
  nodes=[x.identifier for x in tree.nodes.values()]
  ret=[]
  for s in powerset(nodes):
    culled_tree=copy.deepcopy(tree)
    for n in s:
      try:
        culled_tree.remove_node(n)
      except:
        pass
    if len([x.identifier for x in culled_tree.nodes.values()])>0:
      ret.append(culled_tree)

  return ret

def main():
  ST=[]

  #Generate a member of ST
  treeA = treelib.Tree()
  treeA.create_node(1,1)
  treeA.create_node(2,2,parent=1)
  treeA.create_node(3,3,parent=1)
  ST.append(treeA)

  #Generate a member of ST
  treeB = treelib.Tree()
  treeB.create_node(1,1)
  treeB.create_node(2,2,parent=1)
  treeB.create_node(3,3,parent=1)
  treeB.create_node(4,4,parent=2)
  treeB.create_node(5,5,parent=2)
  ST.append(treeB)

  #Generate hashes for members of ST
  hashes=[(HashTree(tree), tree) for tree in ST]

  print hashes

  #Generate a test tree
  T=treelib.Tree()
  T.create_node(1,1)
  T.create_node(2,2,parent=1)
  T.create_node(3,3,parent=1)
  T.create_node(4,4,parent=2)
  T.create_node(5,5,parent=2)
  T.create_node(6,6,parent=3)
  T.create_node(7,7,parent=3)

  #Generate all the subtrees of this tree which still retain the original root
  Tsets=TreePowerSet(T)

  #Hash all of the subtrees
  Thashes=set([HashTree(x) for x in Tsets])

  #For each member of ST, check to see if that member is present in the test
  #tree
  for hash in hashes:
    if hash[0] in Thashes:
      print [x for x in hash[1].expand_tree()]

main()
于 2013-09-23T17:21:33.033 回答
0

要验证一棵树是否覆盖另一棵树，必须至少查看第一棵树的所有顶点一次。通过查看第一棵树的所有顶点恰好一次来验证一棵树是否覆盖另一棵树是微不足道的。因此，如果只需要检查一棵树，最简单的可能算法已经是最优的。

下面的一切都是我病态想象的未经检验的果实。

如果有许多可能T必须针对同一个进行检查ST，那么可以将 ST 的树存储为像这样的事实集

root = 1
children of node 1 = (2, 3)
children of node 2 = ()
children of node 3 = ()

这些事实可以存储在两个表中的标准关系数据库中，“根”（字段“树”和根节点）和“分支”（字段“树”、“节点”和“孩子”）。然后是 SQL 查询或可以构建一系列查询来快速找到匹配的树。我的 SQL-fu 很简陋，所以我无法在单个查询中管理它，但我相信它应该是可能的。

于 2013-09-23T14:59:27.263 回答