Download presentation
Presentation is loading. Please wait.
1
“まっすぐ”と最短経路 - “直線”,ビリヤード,ネットワーク -
首都大学東京 数理情報科学専攻（数理科学コース） 倉田 和浩 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
2
’’まっすぐ’’と’’直線’’ 平面上でまっすぐ歩くには？ PからQまでの最短コースは直線コースである 曲線の長さとは何か？ 折れ線近似
Ｐ３ Ｑ Ｐ２ Ｐ１ Ｐ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
3
曲がった曲面上を”まっすぐ”歩く..とは？ 円柱上に住む”あり”がまっすぐ歩くと？ 円柱上での2点を結ぶ最短経路は？ 切り開いてみれば…
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
4
円柱面上を”まっすぐ”歩く.. 切り開いてみれば… Qの座標は, (cos θ,sin θ,k θ) らせん曲線 まっすぐ歩く Ｑ Ｑ Ｏ
ｚ ｚ Ｒ Ｐ Ｐ Ｒ z=k θ(k: 定数) θ 角度θ=弧PRの長さ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
5
＊らせん曲線・・・円柱面上での’’直線’’
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
6
球面上での最短経路 球面上の2点を結ぶ最短経路は？ 大円（2点と球の中心を通る平面での切り口）に沿った経路が最短となる
球面上の ”三角形”は？ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
7
球面上での最短経路はなぜ大円？ 大円での近似 ＰＱ＝ γ ＜ α＋ β ＝ＰＲ＋ＲＱ なぜなら, α ＞ α’ β ＞ β’
γ ＝ α’＋ β’ Ｒ Ｑ Ｑ Ｐ 大円 Ｒ P Ｐ Ｑ α β γ α’ この方向から見てみると。。。 α 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
8
ビリヤード問題 右のような長方形型ビリヤード台で, 球Xを突いて,2度壁で反射させて球Yにぶつけるにはどの角度で打ち出せばいいのでしょうか？
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
9
反射の原理 Ａ地点からいったん川に寄ってからＢ地点に行く最短経路は？ AP+PBを最小にする地点Pは？ Bの鏡映点B’を考える
AP+PB=AP+PB’>AB’ Ｂ’ 川 P’ Ｐ Ｂ Ａ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
10
ビリヤード問題・・鏡映を考えよう！ 鏡映を考えると見えてくる最短経路・・ＡＣ，ＣＤに２回ぶつかってXからYに到達する最短経路！
応用例:Xの一にある球を２回壁に当ててから四角隅Bの穴にいれるには？ B Ａ Ａ B X’ Ｘ Ｐ Ｙ Ｑ D C C D D C D D C C Y’ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
11
＊ビリヤード問題・・2クッションボール！ 応用例:Xの一にある球を２回壁に当ててから四角隅Bの穴にいれるには？ B Ａ Ａ B Ｘ Ｐ D
C C D D C D D D C C B Ａ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
12
さまざまな形状のビリヤード台では？ 周期軌道（有限時間でまた同じ軌道をくりかえすもの）の存在 周期軌道の描く軌道 円では？楕円では？
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
13
＊三角形ビリヤードの周期軌道 鋭角三角形ABCの各辺上に頂点をもつ小さな三角形PQRの中で辺の全長Lが最小のものは？
Q’PRQ’’が直線のときに最小！ 三角形の相似性より 2AQ’sin A=2AQsin A=L となって, AQが最小のとき, すなわち AQがBCに垂直のときとなる！ 結局P,Q,RはそれぞれC,A,Bからおろした垂線の足と一致する. A Q’’ Q’ R’ P’ R P B Q C 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
14
円形ビリヤードでの軌道 (0,-1)から角度θで打ち出した軌道 θ=π/2.5 θ=π/2.3 ・・・さまざまな周期軌道
θ=1.365 ≒ π/2.3 ・・・周期軌道ではなくて,軌道が中心の小さい円を除いて密に埋めつくす θ θ=1.365 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
15
楕円形ビリヤードでの軌道 楕円(x/a)^2+(y/b)^2=1 a=2,b=1 (0,-1)から角度θで打ち出した軌道 θ=π/5
θ=π/１０ θ=π/６ 周期軌道は？ θ=π/5 θ=π/１０ θ=π/６ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
16
最短ネットワーク問題（シュタイナー木） 3都市A,B,Cを光ケーブルで結びたい 費用を最小限にするために最短に結ぶネットワークを考えたい
中継点を置いてもよい（シュタイナー問題） Ｂ Ｓ Ａ Ｃ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
17
どの角の120°より小さい場合 ＡＰを60°回転して正三角形APP’を作る AP’C’はAPCと相似な三角形
BP+AP+CP=BP+PP’+P’C’に注意して, BPP’C’が直線になるときが最短! 角BPA=120°, 角AP’C’=角APC＝１２０°のときとなる（このときの点Pをシュタイナー点という） Ｃ‘ 60°回転 Ａ Ｐ‘ Ｐ Ｂ Ｃ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
18
どれかの角が120°より大きい場合 角A>120°とする AP’C’はAPCとが相似な三角形になるようにC’をＢＡの延長上にとる
角PAP’<60°よりPP’<AP BP+AP+CP>BP+PP’+P’C’>BC’=BA+AC よってA=Pのときが最短！ Ｃ‘ Ａ Ｐ‘ Ｐ Ｂ Ｃ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
19
3点の場合の最短ネットワーク 中継点Pは三角形ABCの外にはない
AP+BP+CP>AQ+BQ+CQとなりPよりQを中継点とした方が短い 中継点は２つ以上ない方がいい よって１つのシュタイナー点を中継点としたものが最短ネットワークとなる Ｐ Ａ Ｑ Ｃ Ｂ Ｐ１ Ｐ２ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
20
3点を結ぶシュタイナー点の作図 Ｂ 120° Ａ コンパスと定規でできる！！ 120° Ｃ 2018/12/2
2006年8月11日・ひらめき☆ときめきサイエンス
21
４点の場合の最短ネットワーク １つの中継点より,もう１つ中継点を増やした方がいい場合がある
中継点はすべてシュタイナー点であるべき・・・極小シュタイナー木 中継点の個数は最大２個まで 極小シュタイナー木が最短ネットワ－クの候補 Ａ Ｄ Ｐ Ｃ Ｂ P1 P2 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
22
中継点が少ないこともありうる 中継点が１つの場合 中継点なしの場合
一般にN点を結ぶ場合の中継点の個数はN-2個以下！であることが知られている。 D A B C A B D C 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
23
4点を結ぶ（極小）シュターナー木の作図 Ａ Ｄ Ｂ Ｃ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
24
５点を結ぶ（極小）シュタイナー木の作図 正五角形の頂点を結ぶシュタイナー木の作図 Ｅ Ｄ Ａ Ｃ Ｂ 2018/12/2
2006年8月11日・ひらめき☆ときめきサイエンス
25
石鹸膜の実験 平行なプラスチック板に支柱を立てて,それを石鹸水にざぶんと浸してもちあげると…
表面張力のために石鹸膜の面積を最小にするように, 垂直方向は平面になって, ネットワークの長さが自動的に最小になるように石鹸膜が張られる！ シャボン玉を膨らませると・・・？ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
26
石鹸膜の実験でシュタイナー点を見よう 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
27
石鹸膜で5点を結ぶシュタイナー点を見よう 実験… 6点では？7点では？ 一般にN点では？？ いろいろ実験してみたくなりませんか？
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
28
変分問題・最適化問題としての視点 さまざまな条件のもとでの経路の長さを最短にする問題を見てきた
一般に、ある条件のもとで”ある量”（エネルギーとか）を最小にする問題を変分問題（あるいは最適化問題）という 例：等周問題（与られた長さのロープで囲む図形の面積を最大にするには？） 長さLのロープで囲む 面積S 4πS≦L2 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
29
等周問題（シュタイナーの方法） 周の長さを変えずに,面積を増やすように,凸な図形へ,さらに軸対称な図形へと変形できる
最後に角APB=90°のときが面積がおおきくなり… 円！ P A B 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
30
もっと広い領域を囲える？ 設定を少し変えて考えると。。。円が最適解ではなくなる！ 海 同じ長さで倍の面積が囲える！ 2018/12/2
2006年8月11日・ひらめき☆ときめきサイエンス
31
太鼓の形・・・無限次元変分問題 同じ面積をもつさまざまな太鼓のうちで,最も低い音の出せる太鼓の形は何でしょうか？ 2018/12/2
2006年8月11日・ひらめき☆ときめきサイエンス
32
2種類の皮で太鼓を作る … 無限次元最適化問題
一定の形の太鼓を2種類の皮（一定の比率とする）で貼り合わせて最も低い音のでる太鼓をつくるにはどういう貼り合わせ方がいいか？ B A 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
33
体験実習 パソコン(maple)によるビリヤードの軌道（円形,楕円形ビリヤード)を見てみよう！ 最短ネットワークを見てみよう！
コンパスと定規で！ パソコン(mapleで実験） 石鹸膜での実験 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
34
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
35
一般の曲面上での最短経路は？ 測地線の問題 穴のいくつか開いた浮き袋上には、閉じた測地線はいくつある？ 2018/12/2
2006年8月11日・ひらめき☆ときめきサイエンス
36
ビリヤード問題・・・力学系 楕円型ビリヤードでの周期軌道は？ 運動場のトラック型ビリヤード問題・・・さらに面白い, しかし・・・難しい
2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
37
N点を結ぶ最短ネットワークは？ 49都道府県の県庁所在地を結ぶ最短ネットワークは？・・・効率のよいアルゴリズムの作成は難しい
NP完全問題の１つ 2018/12/2 2006年8月11日・ひらめき☆ときめきサイエンス
Similar presentations
