期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2006
卷号：6
期号：11
页码：59-64
出版社：International Journal of Computer Science and Network Security
摘要：This paper proposes a gradient ascent learning algorithm of the Hopfield neural networks for solving fixed linear crossing number problem. The fixed linear crossing number problem is an important problem in printed circuit board layout, VLSI circuit routing, and automated graph drawing. The objective of this problem which is shown to be NP-hard is to embed the edges so that the total number of crossings is minimized. The proposed algorithm uses the Hopfield neural network to get a near-minimal edge crossings, and increases the energy by modifying weights in a gradient ascent direction to help the network escape from the state of the near-minimal edge crossings to the state of the minimal edge crossings or better one. The proposed algorithm is tested on complete graph. We compare the proposed learning algorithm with some other existing algorithms. The experimental results indicate that the proposed algorithm could yield optimal or near-optimal solutions and outperforms the other algorithms.
关键词：Fixed linear crossing number problem, Graph layout, NP-complete problem, Hopfield neural network, Gradient ascent learning
