An Efficient A* Algorithm for the Directed Linear Arrangement Problem

南華大學機構典藏系統 > 科技學院 > 資訊工程學系 > 期刊論文 > Item 987654321/27350

請使用永久網址來引用或連結此文件: http://nhuir.nhu.edu.tw/handle/987654321/27350

題名:	An Efficient A* Algorithm for the Directed Linear Arrangement Problem
作者:	張介耀;Chang, Chieh-yao
貢獻者:	資訊工程學系
關鍵詞:	Directed Linear Arrangement;Directed Clustering;A* Search
日期:	2008-12
上傳時間:	2019-11-20 10:57:01 (UTC+8)
摘要:	In this paper we present an efficient A* algorithm to solve the Directed Linear Arrangement Problem. By using a branch and bound technique to embed a given directed acyclic graph into a layerwise partition search graph, the optimal directed ordering is then be identified through a A* shortest path search in the embedding graph. We developed a hybrid DC+BDS algorithm to approximate the optimal linear arrangement solution, which includes directed clustering and bidirectional sort technique. Along with a lower bound based on the maximum flow technique, this approximation solution is used as an upper bound to prune the state space during the A* search. In order to reduce the memory requirement of the A* search, we also discuss a implementation of the relay node technique from Zhou and Hansen.
關聯:	WSEAS TRANSACTIONS on COMPUTERS vol. 7, no. 12 pp.1958-1967
顯示於類別:	[資訊工程學系] 期刊論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
An Efficient A.pdf		472Kb	Adobe PDF	395	檢視/開啟

在NHUIR中所有的資料項目都受到原著作權保護.

TAIR相關文章