Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.13 No.2, pp.335-354 (June 1997)
Neural Mesh for the Steiner Tree Problem*

Cheng-Yuan Liou and Quan-Ming Chang
Department of Computer Science and Information Engineering
National Taiwan University
Taipei, Taiwan, R.O.C.

The Steiner minimal tree is the tree having the shortest length with the given vertices and some extra points. In this paper, a neural-based approach to solving the Steiner minimal tree problem, which has been shown to be NP-complete, is proposed. The algorithm is based on minimizing an energy function which controls the mesh. The mesh, which is composed of many elements called snakes, is designed to emulate the soap film. To further simplify the emulation, we simulate the film boundary only. The simplified version turns to be a variant type of elastic rings with added normal driven forces devised by Goodhill and Willshaw. This version is also an inverse type of the balloon model devised by Cohen. We show why the elastic ring is used in solving the optimal path problem and show the right way to closely follow the soap film mechanics to obtain optimal paths with elastic rings. Several experiments have been carried out, and the results show that our approach is promising for solving the Steiner minimal tree problem.

Keywords: Steiner tree, soap film, neural network, Hopfield network, elastic mesh

Received October 22, 1996; revised December 10, 1996.
Communicated by Hsin-Chia Fu.
* This work has been supported by National Science Council of the Republic of China.