1

我在应用数学中有一个问题,几乎可以完美地映射到在多路树中找到最长的路径。

我有一个函数 child() 给出子节点(空间中的点满足条件)。唯一需要注意的是 child() 需要连接到它的所有先前节点,包括根节点。正是在这里,我正在努力递归地编写我的代码。到目前为止,我有类似下面的东西。

def multitree(node):
     tmp_list = child(node)
     for child2 in tmp_list:
           if len(child(child2)))==0:       #if you hit a leaf (dead end), go to next element
                 continue
           else:
                 multitree(child2)

但在这一点上,我不确定要返回什么。我基本上想映射整个多路树,直到我找到所有东西的叶子。有什么想法或提示吗?多谢你们。

编辑:

更新 1:为了完整起见,我勾勒出输入 child() 需要什么的粗略概念:https ://i.imgur.com/3MkfsYc.png基本上是为了找到箭头 child() 标记的节点的子节点需要根节点和节点本身之间的节点列表,即用红点标记的节点。

更新 2:

我已经写了 child(node) 如下,我目前正在处理它——

def pathwalk(node):

    children = child(node)
    paths = [child(node.append(kid)) for kid in children]

    return paths
4

2 回答 2

1

你可以做这样的事情来获得最长的路径。在这里它为您提供节点列表,您可以从那里提取任何相关信息:

def longest_path(node):
    children = child(node)

    if not children: # leaf node
        return [node]

    children_vals = [longest_path(c) for c in children]
    longest = max(children_vals, key=len)
    return [node] + longest

不处理关系,或者更确切地说是任意选择一个选项。

(注:半测试)

于 2016-12-11T01:53:19.230 回答
0

我想我找到了问题所在。因为我想保留所有节点的运行列表,您可以找到其子节点(您可以跟踪所走的路径,请参见 imgur pic)。我通过添加编辑了 Illuvatar 的例程

children_vals = [longest_path(node+[c]) for c in children]

通过这种方式,您递归地将每个父级与其子级连接起来。

于 2016-12-14T16:40:26.180 回答