平行化的B 演算法

Abstract

在人工智慧的領域中, B 搜尋演算法是用來解決一些狀態搜尋的問題, 在這些問題中 , 每一節點被附子一個可能的範圍值, 利用這些節點範圍值可以找到由根(root)往外 分支中的最好一支, 在此篇論文中將提出一個全新平行化的B 搜尋演算法, 而且將證 明由平行北的B 演算法所得出的結果, 和原來的B 演算法所得結果是一樣的。對於執 行平行北的B 演算法所獲得的速率增加( 順序性B 演算法所需時間除以平行化B 演算 法所需時間) 將作仔細分析, 另外對於處理器的使用率也將作一分析; 平行化的B 演 算法是在一部稱為Transputer的多處理器系統上執行的, 將利用1 至6 個處理器來執 行B 演算法, 比原來順序性的B 演算法有更佳更有效率的表現。