最短ネットワーク問題:シュタイナー問題

最短ネットワーク問題:シュタイナー問題
3-G 023145
長谷川 和弘
最短ネットワーク問題とは?
線的な施設の最適配置
(水道、電気、ガス、電話、石油パイプラインなど)
ボロノイ図
例 日本主要46都市を結ぶ光ケーブル網
東京、名古屋、新潟の3都市を結ぶ
<条件>
2地点を結ぶケーブルは、ほぼ直線で結べる
ケーブル敷設コストは地形の影響を受けず、1km
当たり1000万円
ケーブルの途中どこでも分岐点を設置でき、分岐
点の敷設コストはなし
建設コストCを比較すると…
a:C=(253km+261km)x1000万/km=51億4000万円
b:C=(252km+261km)x1000万/km=51億3000万円
c:C=(95km+238km+170km)x1000万/km=50億3000万円
距離を最短にするには?
→3点の分岐点を120度にする
d:C=(79km+210km+205km)x1000万/km=49億4000万円
分岐点を実際に求めるには?
トリチェリの作図法
1 東京、名古屋、新潟を3頂点とする三角形ABCを書
く。
2 辺AB、BC、CAのうち1つを選び、その辺を1辺とす
る正三角形を残りの頂点の反対側に作る。いま、辺
ABを選び、正三角形ABXをつくったとする。
3 残りの頂点CとXを結びCXと正三角形ABXの外接
円との交点を求める。この点Sが求める分岐点の位
置で、点Sをシュタイナー点という。ちなみに
SA+SB+SC=CXが成り立っている。
シュタイナー問題
平面上にP1、・・・、Pnが与えられたとき、これらを線
分で結ぶ最短ネットワークを作れ。ただし、任意の
点Q1、・・・、Qnを任意の位置に付け加えてもよい(n、
mは自然数)
NP完全問題
n=3のときは先ほどの場合でOKだが、nが4以上の
場合はメルザグの方法が最も効率がよい。
P1~Pnがあり新たに付け加えた点Q1~Qnを少し
動かしてもネットワークが短くならない、また各点を
結ぶ線分のうち、どれを取り除いてもネットワークが
二つに分かれてしまうネットワークをT木と呼び、最
短ネットワークをS木と呼ぶ。
メルザグの方法は与えられたP1~Pnに対してT木
をすべて列挙し、長さ最小のS木を求めるというもの
である。
ちなみにT木の数はnが増えるにつれ膨大になって
いくので、現在の計算機を使っても、n=29までが、
解ける問題の大きさの限界だといわれている。
シュタイナー問題を発見的に解く方法
シュタイナー問題はn=29までしか解けないので、
日本全国の主要46都市を結ぶ最短ネットワークは
解けない。そこで距離は同じか少し長くなるS’木を求
めることにする。
1 P1~Pnに適当なQ1~Qmを付け加え最小木を作
る。
2 Q1~Qmを少しずつ動かし、この最小木の長さ
を少しずつ減少させていく。
3 Q1~Qmを少し動かしても長さが減らなくなった
ら、Qiを新たに付け加えたり削除したりする。そして
またQ1~Qmを少しずつ動かし、この最小木の長さ
を少しずつ減少させていく。
4 この操作を繰り返し、もう付け加えたり、削除する
QiがなくなったらそれをS’木とする。
まとめ
最初に述べた計画の日本全国の主要46都市を結
ぶ最短ネットワークは、最小木を用いると、
3425km x 1000万/km = 342億5000万円
となり、S’木を用いると、
3275km x 1000万/km = 327億5000万円
となり4%ネットワークを短くでき、15億円コストダ
ウンが出来る。もちろん、実際の計画には他に考慮
すべき点が多々あるが、これは実際の計画をたてる
さいにひとつの目安を与えてくれるのではないだろ
うか。