今天在解一個問題,發現需要用圖論中的 BFS 演算法來解~

問題類似下面這樣:每個 task 可能會有零到多個 sub-task,

而 sub-task 又可以再遞迴包含零到多個 sub-task...

但如果上層的 task 已經被標示成不需要跑的時候,希望子孫也都直接標成不要跑~

 

原本自己在實作時,一開始是像這麼寫的:

yielded_tasks_old_rounds = []

while task_list:
    yielded_tasks_cur_round = []
    kept_tasks = []

    for task in task_list:
        if not task.parent or task.parent in yielded_tasks_old_rounds:
            yielded_tasks_cur_round.append(task)
            yield task
        else:
            kept_tasks.append(task)

    yielded_tasks_old_rounds.extend(yielded_tasks_cur_round)
    task_list = kept_tasks

 

原本的想法是先走過一輪,把沒有父代的 task 找出來 yield 出去,

在下一輪的時候,把父代是已經被 yield 過的 task 找出來 yield 出去,

持續這種步驟直到 task_list 不再有 task 為止~

這個作法雖然算是 O(n),但是有個嚴重的問題:假設 A, B 兩個 task 在同一層,

那麼 A 和 B 的直接的 children 應該要是 A 的先出現、再出現 B 的 children,

但上面的實作是照原本 task_list 的順序,所以雖然還是廣度優先,但在同一層看起來像是在亂跳...

 

重新研究了一下 BFS (breadth-first search),原來應該是要將上層的 task 放在 queue 裡,

依序把他們的 children 放到 queue 的後面,再依序處理下去~

這個作法也是 O(n),但確保了同一層中先出現的 task,其 children 在下一層也會先出現~

只是這個演算法會需要 parent->children 的關係,因此需要先建立起來,

不像我原本 (錯誤的) 實作是只需要原有的 child->parent 的關係:

dict_task_children = {}
result_list = []

for task in task_list:
    if task.parent:
        # Construct a dict for mapping task->children tasks
        dict_task_children.setdefault(task.parent, []).append(task)
    else:
        # Initialize result list with tasks without parents in order
        result_list.append(task)

i = 0
while i < len(result_list):
    task = result_list[i]
    yield task

    # Add children of current task at end of queue
    result_list.extend(dict_task_children.get(task, []))
    i += 1

 

結論:蠻有趣的,不過我的演算法該重修了... Orz

 

參考資料:Graph Traversal: Breadth-first Search

 

文章標籤
創作者介紹

亂打一通的心情日記

ephrain 發表在 痞客邦 PIXNET 留言(0) 人氣()