Abstract
Shuffle-Exchange（SE）是一相當有效率的文換網路，其功能由交換元件（switching element ）來達成。由於前人之研究均限於使用2 ×2 交換元件，我們乃擴充其至一能傳送p 項訊息之pXp 交換元件，稱之為p-SE網路，其中p 為任意正整數。本文之研究目的在於探討p-SE網路上之路徑問題（routing problem ）。p-SE網路之路徑問題是將N 項訊息自N 個源點（source node ）繞徑至N 個終點（terminal node ）；因此，它是一個排列問題（permutation problem ）。此問題經由適當之轉換，可視為一架橋問題（bridge finding problem〔6 〕）。由於此問題之大小為N ！，適當分割為某些排列等級有下列二優點：在硬體上，使用較少之階數（pass）；在軟體上，可找到較快速之演算法。故，本文針對三種排列等級：線性等級（linear class），位元交換等級（digit-permute-constant class）和全等級（all class ），討論其路徑問題。此乃吾人所採用之研究方法。本文之研究成果如下：在為各種排列等級尋找繞徑之中，我們發現一個相當有用的線性性質（linear property ），利用此性質，我們設計了二個演算法來解決架橋問題。Lin （）可以實現線性和位元交換等級，它使用2n-1階交換元件，時間複雜度為O（nN）。它比Etzion和Lempel所提出的方法〔3 〕迅速，使用的處理器亦較少。All（）可以實現全等級，它使用3n-3階交換元件，時間複雜度為O （nN log N/P）。它是〔6 〕的推廣（〔6 〕僅言及2-SE網路）。其中，N ＝p**n。除此之外，在理論證明上，我們利用線性性質，得到相當簡潔且易明瞭之定理證明。另外，graph theory中的塗色問題和路徑問題中的一個子問題是相等的，我們之另一研究成果為蒐集各種文獻，並提供讀者目前最佳之解（〔1 〕）。