An Efficient A* Algorithm for the Directed Linear Arrangement Problem

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

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: 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	394	检视/开启

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

TAIR相关文章