Abstract
本篇論文之主要內容為討論排列及一些限制性排列之生成演算法。排列(permutation) 系一基本而重要的組合結構(combinatirial structure),也是許多組合問題的解空間。因此排列之列舉演算法可運用於(一)解列舉問題(Enumeration problem)。(二)以窮舉搜索法(Exhaustive search) 解NP_hard 問題。雖然有一些困難的組合問題已發展出避免窮舉之演算法，例如Branch and bound, 但是仍然有許多復雜而困難的問題無法避免窮舉搜尋。例如在的現實問題中，許多都是要解多目標最佳化問題(Multi-criteria optimization problem),甚至有些目標函數根本無法完美的量化。對此類問題，無可避免的必須使用窮舉搜尋來列舉一些可能的答案。因此，如何有效的列舉組合結構仍然是非常重要的。尤其近年來平行計算機快速的發展，平行列舉亦益發顯的重要。本論文除發展平行列舉演算法外，也展現了如何在這些組合結構中產生隨機組合物件的演算法(algorithms for generating random combinatorial objects)。這是設計蒙地卡羅式的隨機演算法(Monte-Carlo random algorithms) 的基礎，而後者為求大型困難問題之近似解的重要方法。本論文之主要結果簡述如下(一)於線性陣列多處理機系統上產生ｎ個物件所有排列之平行演算法。模式(model)---含n 個處理機之線性陣列多處理機系統，每個處理機只使用常數個計意體，且只使用小數字的計算。復雜度(complexity)--- 每個排列在常數時間內產生。為最佳成本(cost optimal) 之演算法。(二)產生任一序位之排列(permutation unranking) 的平行演算法。模式---CREW PRAM model。復雜度---O(rlogr/N+logrloglogN) ，對產生n 取r 的韭旬，其中N 是處理機的個數。(三)對一前序樹(precedence tree),其拓樸須序(topologic order) 之生成演算法。內容包括---ranking,unranking,next,and parallel enumerating。復雜度---ranking unranking--O(nlogn) next---O(n)。平行列舉---O(M*n/N+nlogn) 其中Ｍ是拓樸順序之個數，而n 是前序樹中節點(node)個數。(四)Hypercube 上不相效路徑之生成演算法。此係一新的限制性排列，尚未被研究。內容包括---ranking,unranking,next,and parallel enumerating復雜度---ranking及unranking--O(nlogn) next--O(n) 平行列舉--O(M*n/N+nlogn)M 是路徑之個數,ｎ是所給兩點之距離。