シュタイナー問題とは、(なかなか説明しにくいのではありますが、)Ｎ個の点があるとき、線の長さが最小になるように点達を結ぶネットワークを作る問題です。この時、シュタイナー問題では、線がＮ個の点同士を結ばなくてもいいとします。(線は点同士しか結べない問題は最小木問題です。) このアプレットでは、もともとある点の数をＮ（Ｎは●の数）として、Ｎ以外に新しくできた点の数をＭとしています。Ｍは□の数になります。□の位置は正しい答えに近づく度に動いたり消えたり新設されたりします。これを見ているのは楽しいです。
はっきりいって上の説明は不十分でわかりにくく、しかも正しい答えがすばやく得られるホショウはないので、参考文献を紹介します。
ここで使っているアルゴリズム
Ｎ個の点が適当に置かれているものとします。
1. N個の点の凸法内に適当にＮ−２以下の点を追加します。
2. 追加した点も含めて最小木を描きます。
3. 長さがこれまでの最小でなかったら1へ。
4. 追加した点の最適点を反復法で求めます。1へ。
●参考文献
・秋山仁、R.L.Graham著、朝倉書店、離散数学入門
・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
●Javaプログラムのダウンロード(msteiner.java 23KB)
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
●大山崇のホームページの利用について
●大山崇のホームページ