チャレンジ！ アルゴリズム④
アルゴリズムは計算の仕方を考える学問。その一端に触れてみましょう。
-------- ■ チャレンジ ④ ■ ----------
いくつかの無線基地局をいくつか作って、それぞれが連絡できるようにアンテナを立てたいと思っています。図のように候補地が50カ所あるのですが、山やビルなどがあり、近ければ連絡が取れるというものではありません。２つの候補地の間で連絡が取れるかどうかは、実際に計測をしてみないとわからなくて、その計測には10万円かかります。図の黒線で結ばれた４つの候補地のように、互いに連絡できるものを見つけたいと思っています。
今、最初に一つ基地局を建てる場所を決めて、以後一つずつ、全部の基地局から連絡が取れる場所に基地局を追加していくことにします。最初の一カ所目は何も計測がいらないのですが、２つめを建てるときには、99カ所について連絡が付くかどうかチェックしなければいけません。３つ目を立てるときには、２つ目の基地局から連絡が取れるかどうか、98カ所について連絡を取らなければいけません、、、となると、けっこうなお金がかかります。さて、この計測コストを少なくするには、どのような方法をとればいいでしょうか？ 各候補地は、平均的に、半分くらいの場所とは連絡が取れると思いましょう。
