0

我有一棵树，如下所示。

  • 红色表示它具有某种属性，未填充表示它没有它。我想尽量减少Red检查。
    1. 如果Red所有祖先也是Red（并且不应再次检查）。
    2. 如果Not Red比所有后代都是Not Red.
  • 树的深度为d。
  • 树的宽度为n。

  • 请注意，子节点的值大于父节点。

    • 示例：在下面的树中，
      • 节点 '0' 有子节点 [1, 2, 3]，
      • 节点 '1' 有子节点 [2, 3]，
      • 节点“2”有孩子 [3] 和
      • 节点“4”有孩子 []（没有孩子）。

    • 因此，孩子可以构造为：

      if vertex.depth > 0:
    vertex.children = [Vertex(parent=vertex, val=child_val, depth=vertex.depth-1, n=n) for child_val in xrange(self.val+1, n)]
else:
    vertex.children = []

这是一个示例树：

那个树

我正在尝试计算Red节点数。树的深度和宽度都会很大。所以我想做一种深度优先搜索，另外使用上面的属性 1 和 2。

我如何设计一个算法来遍历那棵树？

PS：我标记了这个 [python] 但任何算法大纲都可以。

更新和背景

  1. 我想尽量减少财产检查。
  2. 属性检查正在检查从我的树的路径构造的二分图的连通性。 示例：
    • 示例树中左下角的节点的路径= [0, 1]。
    • 让二部图有集合R和C大小r和c。（注意，树的宽度是n=r*c）。
    • 从路径中，我通过从完整图开始并删除路径中所有值的边 (x, y) 来到达图的边缘，如下所示：x, y = divmod(value, c).

属性检查的两条规则来自于图的连通性： - 如果图是在删除了边 [a, b, c] 的情况下连接的，那么它也必须在删除了 [a, b] 的情况下连接（规则 1）。- 如果图在删除边 [a, b, c] 的情况下断开连接，那么它也必须在删除附加边 d [a, b, c, d] 的情况下断开连接（规则 2）。

更新 2

所以我真正想做的是检查从[0..n]中挑选d个元素的所有组合。树结构有些帮助，但即使我得到了一个最优的树遍历算法，我仍然会检查太多的组合。（我刚才注意到了。）

让我解释。假设我需要检查 [4, 5] （所以 4 和 5 如上所述从二分图中删除，但在这里无关紧要。）。如果它显示为“红色”，我的树将阻止我仅检查 [4]。那很好。但是，我也应该将 [5] 从检查中剔除。

如何更改树的结构（可能是图表？）以进一步减少检查次数？

4

3 回答 3

2

使用删除-收缩算法的变体来评估完整二部图 K_{r,c} 上的 Tutte 多项式（在 (1,2) 处评估，给出生成子图的总数）。

在一个句子中，想法是任意排序边，枚举生成树，并为每个生成树计算有多少大小为 r + c + k 的生成子图具有最小生成树。生成树的枚举是递归执行的。如果图 G 恰好有一个顶点，则关联生成子图的数量是该顶点上的自环数选择 k。否则，在 G 中找到不是自循环的最小边并进行两次递归调用。第一个在图 G/e 上，其中 e 收缩。第二个是在图 Ge 上删除了 e，但前提是 Ge 是连通的。

于 2013-07-13T15:30:38.430 回答
1

Python 足够接近伪代码。

class counter(object):
    def __init__(self, ival = 0):
        self.count = ival

    def count_up(self):
        self.count += 1
        return self.count

def old_walk_fun(ilist, func=None):
    def old_walk_fun_helper(ilist, func=None, count=0):
        tlist = []
        if(isinstance(ilist, list) and ilist):
            for q in ilist:
                tlist += old_walk_fun_helper(q, func, count+1)
        else:
            tlist = func(ilist)
        return [tlist] if(count != 0) else tlist
    if(func != None and hasattr(func, '__call__')):
        return old_walk_fun_helper(ilist, func)
    else:
        return []

def walk_fun(ilist, func=None):
    def walk_fun_helper(ilist, func=None, count=0):
        tlist = []
        if(isinstance(ilist, list) and ilist):
            if(ilist[0] == "Red"): # Only evaluate sub-branches if current level is Red
                for q in ilist:
                    tlist += walk_fun_helper(q, func, count+1)
        else:
            tlist = func(ilist)
        return [tlist] if(count != 0) else tlist
    if(func != None and hasattr(func, '__call__')):
        return walk_fun_helper(ilist, func)
    else:
        return []

# Crude tree structure, first element is always its colour; following elements are its children
tree_list = \
["Red",
    ["Red", 
        ["Red", 
            []
        ], 
        ["White", 
            []
        ],
        ["White", 
            []
        ]
    ],
    ["White",
        ["White", 
            []
        ],
        ["White", 
            []
        ]
    ],
    ["Red", 
        []
    ]
]

red_counter = counter()
eval_counter = counter()
old_walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up())
print "Unconditionally walking"
print "Reds found: %d" % red_counter.count
print "Evaluations made: %d" % eval_counter.count
print ""

red_counter = counter()
eval_counter = counter()
walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up())
print "Selectively walking"
print "Reds found: %d" % red_counter.count
print "Evaluations made: %d" % eval_counter.count
print ""
于 2013-07-13T06:29:34.490 回答
0

您为快速进行连通性测试付出了多少努力？

为了测试图的连通性，我会以随机顺序选择边，并在看到连接它们的边时使用 union-find 合并顶点。如果图是连接的，我可以提前终止，并且我有一种连通性证书 - 连接两个以前未连接的顶点集的边。

当您在二分图上沿树向下工作/遵循路径时，您正在从图中删除边。如果您删除的边不在连通性证书中，则该图仍必须是连通的——这对我来说似乎是一个快速检查。如果它在连通性证书中，您可以备份到添加边之前的联合/查找状态，然后尝试添加新边，而不是重复完整的连通性测试。

根据您定义路径的确切方式，您可以说该路径的扩展永远不会包含使用顶点子集的边 - 例如到目前为止位于路径内部的顶点。如果源自那些不可触碰的顶点的边足以使图连接起来，那么路径的任何扩展都不能使其不连接。然后至少你只需要计算不同路径的数量。如果原始图是规则的，我希望找到一些动态编程递归，让您在不显式枚举它们的情况下计算它们。

于 2013-07-13T13:38:10.650 回答