Abstract
分枝與界定演算法通常用來解 N-P Complete 之組合最佳化問題。在本篇 論文中，我們提出一種平行最佳分枝與界定法以解推銷員問題。此方法是 架構在一個簡單的相鄰處理器之動態平衡演算法上。此演算法能夠使得搜 尋負擔大量減少，並且不會產生太多的通訊負擔。對推銷員問題而言，我 們用選或不選某個邊來加以分枝。在每次分枝時，我們選擇具有最小成本 的邊作為我們分枝的憑據。而這個邊必須無法造成一個循環，除非我們找 到了一個可行解。分枝完畢後，新生成的節點將被放入每個處理器的權限 佇列中，以便選擇下一次分枝的節點。在平行最佳分枝與界定演算法中， 為了提高整體的加速率，我們必須讓每一個處理器選出“有用的”的節點 加以分枝。這裡所謂有用的節點指的就是那些出現在循序演算法中的節點 。但是在平行演算法中那些節點是有用的我們是無法預先知道的，除非我 們事先知道在循序演算法中出現的節點有那些。一個比較合理而又可以達 成的方法是讓平行演算法所選出的分枝節點儘量相似或趨近於循序演算法 所選出的分枝節點。對任一處理器而言，在每一次分枝完畢後，它都會執 行一次平衡演算法。這個演算法首先將別的處理器送過來的節點與第二最 小下界值(如果有的話)分別放入權限佇列與表格中。然後它會比對表格中 的值是否超過其第二最小下界值。如果是的話，它就將其第二最小下界的 節點送給該處理器。最後它會將其最新的第二最小下界值傳給所有與其相 鄰的處理器。我們將我們的演算法寫成程式，並在有 128 個處理器的 nCUBE/2 平行計算機上執行。結果顯示:第一，我們的演算法在平行環境 中所選出來的分枝節點數目只多出循序演算法中節點數目極少的百分比。 這表示我們的平衡演算法可以使得每一個處理器都選出“有用的”的節點 加以分枝。第二，我們的演算法只花掉極少比例的時間在訊息的交換上。 第三，我們的演算法可以達到趨近線性的加速率。 Branch and bound is an important design strategy of algorithm to solve NP-complete combinatorial optimization problems. In this thesis, we present a best-first branch and bound scheme for parallel computers to solve the traveling salesperson problem (TSP). This scheme is based on a simple nearest- neighbor dynamic balancing strategy which reduces the redundant search overhead but doesn't involve too much communication overhead. For the TSP, we branch the search tree by choosing or discarding a certain edge which has the minimal cost. This edge does not cause a circle unless it has been the feasible solution. To promote the speedup, each processor should choose the "useful" nodes for branching. These nodes are those which appear in the sequential algorithm, but could not be known in advanced. A more reasonable and achievable method is choosing the nodes which is similar to those chosen by the sequential algorithm. After each branching, each processor enters the balancing algorithm. This algoirthm first puts the lower bounds and nodes come from its neighbors to its priority queue and table, respectively. Then it selects the neighbors by checking if its value in the table is greater than or equal to the processor's second best lower bound. If there is such lower bound, it sends the second best node to the corresponding processor. After that, it sends the new second best lower bound to all its neighbors. We implemented our algorithm and experimented on the nCUBE/2 parallel computer which has 128 processors. The results show that, first, the number of nodes chosen by our algorithm in the parallel environment is just a few larger than the number of nodes chosen by the sequential algorithm, which implies little search overhead. Second, our algorithm spends only few time in the exchange of information. Third, our algorithm approaches nearly linear speedup.