設計產生基本組成個體之平行演算法

Abstract

在本研究中，我們將提出一些平行演算法以產生下列之組成個體：排列、 子集合和集合分割，我們提出之平行演算法有下列之優點：首先，他們是 有效率的和擁有較低之計算花費，其次，他們能在簡單規律的陣列上被執 行，因此特別適合在超大型積體電路上製作，另外，我們所提出之平行演 算法能以某些特別之次序來產生組成個體，例如﹕字母順序排列或最小變 化排列。當我們與其他研究者之相關設計做比較，這些優點即被突顯出來 。 In this research, we shall propose several parallel algorithms for the generation of the following combinatorial objects: permutations, subsets, and set partitions. The proposed parallel algorithms have the following advantages. First, they are time efficient and have low computation cost. Second, they can be executed on simple regular array processors, and hence are amenable to VLSI implementation. Third, they generate combinatorial objects in some desired order, such as lexicographic order or minimum change order. These advantages can be seen from the evaluation of the proposed designs and the comparisons of them with existing ones.