Steiner tree problem's heauristic algorithm(Open 23/Feb/2002 : The 1st Revision Monday, 03-May-2004 11:22:33 JST)
Algorithm in this applet
Assume that there are N points.
1. Locate M(smaller than N-1) points in the convex hull of N points.
2. Draw the minimum spanning tree.
3. If the length of the tree isn't minimum,then goto 1.
4. Compute the best location of Additional points by using itteration method. Goto 1.
References
Frank K. Hwang, Dana S. Richards,Pawel Winter, North-Holland, The Steiner tree problem
Hans Jürgen Prõmel, Angelika Steger, vieweg, The Steiner Tree Problem msteiner.java
If you have a message, don't hesitate to send it by using
E-mail: Easy subject (which starts with 'about nirarebakun.com') to understand, please. Because I'm afraid to get a virus mail or ad-mail, I delete the mail if the subject is abnormal.
Good example for subject:
About nirarebakun.com:Voronoi diagram
About nirarebakun.com:I'm interested in Steiner problem
Bad example for subject:
'Hello', 'Thank you', 'How do you do', 'Please', 'I love you', 'Re', 'Document', 'Excel file', 'Product' and so on.
And don't attach the file when you send the first mail.
or BBS English Home of Takashi Ohyama Japanese Home of Takashi Ohyama
