A NEURAL-NETWORK FOR THE STEINER MINIMAL TREE PROBLEM

The problem of finding the shortest tree connecting a set of points is called the Steiner minimal tree problem and is nearly three centuries old. It has applications in transportation, computer networks, agricu lture, telephony, building layout and very large scale integrated circ uit (VLSI) design, among others, and is known to be NP-complete. We pr opose a neural network which self-organizes to find a minimal tree. So lutions found by the network compare favourably with the best known or optimal results on test problems from the literature. To the best of our knowledge, the proposed network is the first neural-based solution to the problem. We show that the neural network has a built-in mechan ism to escape local minima.