植基於頂點對排序的關聯性資料排列法的探討

南華大學機構典藏系統 > 科技學院 > 資訊管理學系 > 博碩士論文 > Item 987654321/19525

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://nhuir.nhu.edu.tw/handle/987654321/19525

题名:	植基於頂點對排序的關聯性資料排列法的探討
其它题名:	Solving the Directed Linear Arrangement Problem with successive vertex pair ordering technique
作者:	藍弘文 Lan, Hung-wen
貢獻者:	資訊管理學系碩士班蔡德謙 Te-chien Tsai
关键词:	有向線性排程;貪婪搜尋 Directed linear arrangement;greedy search
日期:	2010
上传时间:	2015-03-16 11:42:02 (UTC+8)
摘要:	有向線性排程在於工作排程及無線資料廣播中應用很廣泛且具研究的問題。這著作提出的演算法有不同等級的複雜度來解決此問題，像混合比率切割貪婪排序演算法，其中有數個演算法是根據連續頂點對排序技術及等同邊叢集演算法。混合比率切割貪婪排序演算法是應用雙向貪婪排序以及遞迴二分法，故混合比率切割貪婪排序演算法在全域最佳化中有高效能的區域搜尋。連續頂點對排序技術應用在兩種環境，一種是在於權重邊下的最大延遲縮減技術，另一種是在於優先邊下的搶占邊技術。最大平均延遲縮減比起傳統以切割為基礎的演算法，更可以達成較佳解，如果在權重邊只有優先順序的情形下，搶占邊演算法可以採用且有效。等同邊叢集演算法應用等同邊來取代邊，且使用有向HAC結合頂點成為片斷(segment)。透過實驗來確定不同啟發演算法的效率。　　Directed linear arrangement is a widely adopted and studied problem in task-scheduling and wireless data broadcasting. This work presents algorithms with various levels of complexity to solve this problem, including a hybrid ratio cut greedy sort algorithm, several algorithms based on the successive vertex pair ordering technique, and a equivalent edge clustering algorithm. The hybrid ratio cut greedy sort algorithm, which adopts the two-way greedy sort and recursive bipartition, is a highly efficient local search algorithm with global optimization. The successive vertex pair ordering technique comprises the maximum latency reduction technique for weighted edges, and the preemptive edge technique for priority edge. The algorithm based on maximum average latency reduction could delivers a better solution outcome than a classic cut-based algorithm, and the algorithm based on the priority edge and be adopted when only the edge priority (or preference) is available. The equivalent edge clustering algorithm adopts the equivalent edge technique to replace edges, and adopts the directed HAC process to merge vertices into a segment. Experiments are conducted to check the effectiveness of different heuristic algorithms.
显示于类别:	[資訊管理學系] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
098NHU05396007-001.pdf		1328Kb	Adobe PDF	260	检视/开启
index.html		0Kb	HTML	161	检视/开启

在NHUIR中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....