もう一度(これでだめな時は更新してください。) : 新しいNと場所で描き直します。
自動的編最小木ネットワークの最小木重み付きネットワークの最小木
だいたい正しい答えが得られる場合もあるシュタイナー問題(注:ちょっと重いです。)
クリック編最小木ネットワークの最小木-
だいたい正しい答えが得られる場合もあるシュタイナー問題(注:ちょっと重いです。)
スクリーンセーバー

だいたい正しい答えが得られる場合もあるシュタイナー問題(2002年2月23日公開、2010年06月03日22:20:01第5回の改訂)

上はJAVAで作られています。メモリを大量に使ったり、重くなるかもしれません。その時は、ごめんなさい。
実行後に画面をスクロールしたり、アプレット全体が画面に入ってないと、間違った画面になるかもしれないので、気をつけてください。画面の大きさを決めてから”もう一度”をクリックするか、更新(reload)してください。


●シュタイナー問題
シュタイナー問題とは、(なかなか説明しにくいのではありますが、)N個の点があるとき、線の長さが最小になるように点達を結ぶネットワークを作る問題です。この時、シュタイナー問題では、線がN個の点同士を結ばなくてもいいとします。(線は点同士しか結べない問題は最小木問題です。) このアプレットでは、もともとある点の数をN(Nは●の数)として、N以外に新しくできた点の数をMとしています。Mは□の数になります。□の位置は正しい答えに近づく度に動いたり消えたり新設されたりします。これを見ているのは楽しいです。
はっきりいって上の説明は不十分でわかりにくく、しかも正しい答えがすばやく得られるホショウはないので、参考文献を紹介します。

ここで使っているアルゴリズム
N個の点が適当に置かれているものとします。
1. N個の点の凸法内に適当にN−2以下の点を追加します。
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)

ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、
●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。


●大山崇のホームページの利用について
●大山崇のホームページ