非バイナリツリーのルートからリーフまでのすべてのパスを見つける最適化された方法

Question

私は同じ配列のいくつかの場所へのバックポインタのリストを格納する2D配列を持っています。 2d配列の最後のエントリから、バックポインタが格納されていないエントリに移動する必要があります。技術的には、非バイナリツリーを横切るようなものです。

私の現在の素朴な実装は

def traverse_tree (root,cur_path,backpointer_array,pathlist): 
    print "adding root " + str(root) 
    cur_path.append(root) 
    children = backpointer_array[root[0]][root[1]] 
    if(len(children)==0): 
     pathlist.append(cur_path) 
    else: 
     for child in children:   
      traverse_tree(child,cur_path[:],backpointer_array,pathlist) 

ある行列のサイズが小さい場合、コードは正常に動作します[5 * 5]が、私は大きな行列[50×500]、コードでそれを実行しようとすると、永遠に実行されます。この実装を最適化する方法はありますか？

Answer 1

マルチスレッドとキューを使用する場合は、パフォーマンスが大幅に向上します。

ここでは使用例を示していますが、これを書き直してシナリオに実装する必要がある場合は、私が助けてくれることを喜んでお勧めします。

from Queue import Queue 
from threading import Thread 

# Set up some global variables 
worker_threads = 64 
my_queue = Queue() 

# the data we work on 
my_data = range(1000) 

def Worker(i, q,): 
    # This is the worker thread function. 
    # It processes items in the queue one after another. 
    # These daemon threads go into an infinite loop, 
    # and only exit when the main thread ends. 
    while True: 
     data = q.get() 

     print "[*] ", data, " i am", i 

     q.task_done() 


# Set up some threads to fetch the enclosures 
for i in range(worker_threads): 
    worker = Thread(target=Worker, args=(i, my_queue,)) 
    worker.setDaemon(True) 
    worker.start() 

# Put the enclosure data into the queue. 
for data in my_data: 
    my_queue.put(data) 

# Now wait for the queue to be empty, indicating that we have processed all of the data. 
print '*** Main thread waiting' 
my_queue.join() 
print '*** Done' 

Answer 2

を再利用することができ、メモリ「サブパス」に格納する使用動的計画あなたは、各ノードをマップするマップMを必要としています。ここ

は簡単なデモですあなたの配列をそのノードからのパスのリストに追加します。

あなたのデータ構造が木である場合、あなたは何を得ることはありませんが、一般的なケースでは、あなたが

擬似コード

M = map<Node, List<Path>> // Path is just a list of Nodes 
List<Path> traverse_tree (CurrentNode) 
    if(M contains CurrentNode) 
     return M[CurrentNode] 
    answer = List<Path> 
    for each children C of CurrentNode 
     subpath = traverse_tree(C) 
     // Shorthand to say prepend CurrentNode to all paths in subpath 
     answer.append(CurrentNode+subpath) 
    M[CurrentNode] = answer // Dynamic programming time! 
    return answer 

Full_Path_List_From_Root = traverse_tree(Root) 

ノート線形する指数時間から行くことができます。

を

• サイクルがある場合、これは無限ループすることができます（ただし、有限時間内にすべてのパスを取得することはできません）
• 各ノードはここでは、一度だけ
• 探求興味深い例である

2つのノードのNスタックは（ピクチャ3のみが存在する）が存在する想像。合計で、2^N個のパスがあります。素朴な実装は、葉に指数関数的な時間数だけアクセスします。サブパスを保存する場合は、指数関数ではなく、各ノードに1回だけアクセスします（ただし、奇跡はありません。指数関数的な数のパスがあれば、指数関数のリストが指数関数になります）