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