ユビキタスの街角

Wednesday, March 21, 2007

点を結ぶ線の長さの和を最小にしようとするシミュレーション

固定された点A, B, Cと移動可能な点Dがあるとき、角ADB, BDC, CDAが120°となるように Dを配置するとAD, BD, CDの長さの和が最小にになる。 Dをいろいろ動かしてみて長さが短くなる方向に移動させるシミュレーションを行なうと、 実際Dはこのような点まで移動して停止する。
3個以上の点に対してこのような計算を行なう シミュレータを作ってみた。 黄色の点をドラッグして動かしたり点の数を変更したりすると面白い。

(追記: Steiner Treeという 有名な問題だということを教えてもらいました。)