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:

私は以下のように子（ノード）を書きました、そして私は現在それに取り組んでいます-

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

同点を処理しないか、任意に 1 つのオプションを選択します。

(注: 半テスト済み)

于 2016-12-11T01:53:19.230 に答える
0

私は問題を見つけたと思います。子を見つけたすべてのノードの実行中のリストを保持したかったので (歩いたパスを追跡します。imgur pic を参照してください)。Illvatar のルーチンを追加して編集しました

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

このようにして、すべての親とその子を再帰的に連結します。

于 2016-12-14T16:40:26.180 に答える