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

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

使える数学!(2007年度)
Time-stamp: "2007-11-05 Mon 13:41 JST hig"

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

ビデオ視聴

ビデオ視聴

目次

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

追加情報

計算量的側面

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

参考文献

BBSとコメントBoxから

確認テストでは, 作図で長さを求めるという問題でしたが, 「きっちりと」計算で求めることができるのか? という疑問をもたれた方もいましたね. どんな形の三角形の問題場合でも, 頂点の座標が与えられていれば, 座標や三角関数の例えば余弦定理などを使って計算で求めることは可能です. そういうプログラムもかけます. この授業では, 文系の方もいらっしゃるということで, 作図して最終的な数値だけ答えるという問題にしました.(2007-10-08)

確認テスト略解

確認テスト略解
Copyright © 2007 Saburo Higuchi. All rights reserved.
樋口三郎, hig's mail address