最短ネットワーク問題：シュタイナー問題 ３－G　０２３１４５ 長谷川　和弘.

Presentation on theme: "最短ネットワーク問題：シュタイナー問題 ３－G　０２３１４５ 長谷川　和弘."— Presentation transcript:

1 最短ネットワーク問題：シュタイナー問題 ３－G　０２３１４５ 長谷川　和弘

2 最短ネットワーク問題とは？ 線的な施設の最適配置 （水道、電気、ガス、電話、石油パイプラインなど） ボロノイ図
　（水道、電気、ガス、電話、石油パイプラインなど） ボロノイ図 例　日本主要４６都市を結ぶ光ケーブル網

3 東京、名古屋、新潟の３都市を結ぶ ＜条件＞ ２地点を結ぶケーブルは、ほぼ直線で結べる
ケーブル敷設コストは地形の影響を受けず、１ｋｍ当たり１０００万円 ケーブルの途中どこでも分岐点を設置でき、分岐点の敷設コストはなし 建設コストCを比較すると…

4 ａ：C＝（253km+261km）ｘ1000万/km＝51億4000万円
ｃ：C＝（95km+238km+170km）ｘ1000万/km＝50億3000万円 距離を最短にするには？ →３点の分岐点を１２０度にする ｄ：C＝（79km+210km+205km）ｘ1000万/km＝49億4000万円 分岐点を実際に求めるには？

5 トリチェリの作図法 １ 東京、名古屋、新潟を３頂点とする三角形ABCを書く。
２　辺AB、BC、CAのうち１つを選び、その辺を１辺とする正三角形を残りの頂点の反対側に作る。いま、辺ABを選び、正三角形ABXをつくったとする。 ３　残りの頂点CとXを結びCXと正三角形ABXの外接円との交点を求める。この点Sが求める分岐点の位置で、点Sをシュタイナー点という。ちなみにSA+SB+SC＝CXが成り立っている。

6 シュタイナー問題 平面上にP1、・・・、Pnが与えられたとき、これらを線分で結ぶ最短ネットワークを作れ。ただし、任意の点Q1、・・・、Qnを任意の位置に付け加えてもよい（ｎ、ｍは自然数） NP完全問題

7 ｎ＝３のときは先ほどの場合でOKだが、ｎが４以上の場合はメルザグの方法が最も効率がよい。
　　P1～Pnがあり新たに付け加えた点Q1～Qnを少し動かしてもネットワークが短くならない、また各点を結ぶ線分のうち、どれを取り除いてもネットワークが二つに分かれてしまうネットワークをT木と呼び、最短ネットワークをS木と呼ぶ。 　　メルザグの方法は与えられたP1～Pnに対してT木をすべて列挙し、長さ最小のS木を求めるというものである。 　　ちなみにT木の数はｎが増えるにつれ膨大になっていくので、現在の計算機を使っても、ｎ＝２９までが、解ける問題の大きさの限界だといわれている。

8 シュタイナー問題を発見的に解く方法 シュタイナー問題はｎ＝２９までしか解けないので、日本全国の主要４６都市を結ぶ最短ネットワークは解けない。そこで距離は同じか少し長くなるS’木を求めることにする。

9 　１　P1～Pnに適当なQ1～Qｍを付け加え最小木を作る。
　３　 Q1～Qｍを少し動かしても長さが減らなくなったら、Qiを新たに付け加えたり削除したりする。そしてまたQ1～Qｍを少しずつ動かし、この最小木の長さを少しずつ減少させていく。 　４　この操作を繰り返し、もう付け加えたり、削除するQiがなくなったらそれをS’木とする。

10 まとめ 最初に述べた計画の日本全国の主要４６都市を結ぶ最短ネットワークは、最小木を用いると、
３４２５ｋｍ　ｘ　１０００万/ｋｍ　＝　３４２億５０００万円 　　となり、S’木を用いると、 ３２７５ｋｍ　ｘ　 １０００万/ｋｍ　＝ ３２７億５０００万円 　　となり４％ネットワークを短くでき、１５億円コストダウンが出来る。もちろん、実際の計画には他に考慮すべき点が多々あるが、これは実際の計画をたてるさいにひとつの目安を与えてくれるのではないだろうか。