QRcode to hig3.net
携帯キャリア自動判別
http://hig3.net

安上がりな高速道路整備 --- グラフ理論と最小シュタイナー木

使える数学!(2011年度)
Time-stamp: "2011-10-17 Mon 17:39 JST hig"

担当教員による追加資料などを提供するサポートサイトです.

目次

  1. 2点間の最短経路
  2. 3点を結ぶ最短経路
  3. シュタイナー点
  4. 石鹸水を利用した解法

追加情報

計算量的側面

VODではあまり深く触れられませんでしたが, 4点以上の場合, どの順でつないでいくかに関してしらみつぶしに調べるようなことをしないと, 最短の結び方を見つけることは出来ません. このときに必要な計算量(そういう話は第5回 楽してトランプをそろえよう --- アルゴリズムと計算量 でするのですが)は多く, NP完全な問題であることが知られています. なるべく小さい計算量で見つけようとする試みは, 特に文献「数学とは何か」や「最適配置の数理」に述べられています.

参考文献

補足

シュタイナー木の長さというのを授業の中ではきちんと定義していなかったかもしれませんが, それぞれの枝(線分)の長さの合計のことです.
Copyright © 2007-2010 Saburo Higuchi. All rights reserved.
樋口三郎, hig's mail address