頁籤選單縮合
題名 | 平行演算法在座位安排上應用=Parallel Algorithm on Seat Allocation |
---|---|
作者姓名(中文) | 廖炳松; | 書刊名 | 正修學報 |
卷期 | 9 1996.07[民85.07] |
頁次 | 頁143-148 |
分類號 | 310.153 |
關鍵詞 | 座位安排; 漢彌頓環路; 平行處理; Seat allocation; Hamiltonian cycle; Parallel processing; |
語文 | 中文(Chinese) |
中文摘要 | 克門女同學問題(Kirkman's Schoolgirl Problem):對於一群參加聯誼活動而 彼此又不認識的女同學,主辦單位該如何安排她們之間的座位,才能使得她們有更多的機會 去認識新朋友。而此座位問題本身就是漢彌頓環路( Hamiltonian Cycle )的應用 [1][2] 。 本文根據傳統的座位問題之順序處理( sequential processing )方法,在資料的連結 結構方面重新加以組合,並順利將它轉換成平行處理( parallel processing )問題。 對 於一群 N 個對象的座位安排問題,若以順序處理所需時間為 T,則以 M 個心跳架構處理器 ( systolic processor element )進行平行處理,其所需要作業時間為 T ( 1+N/M ) / ( N+1 )。 |
英文摘要 | Kirkman's schoolgirl problem is a seat allocation problem. In order to make a group of strange girls have more chances to make friends with each other. the organizer wants to know how to deal with their seats in this social gathering. Seat allocation itself is one application of Hamiltonian cycle [1][2]. To rearrange a linkage structure of sequential processing on seat allocation, this study proposes a parallel architecture to process it. For a group of N persons, if the time of seat allocation by sequential processing is T, it should be T(1+N/M)/(N+1) by parallel processing with M systolic processor elements. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。