チャレンジ！ アルゴリズム④ 解答
こんなふうに計算します。最初に、左上の、図で赤く囲った候補地を選んだとします。そして、選んだ候補地から連絡が取れるところを調べます。調べた結果、連絡が付かない物を候補から消し、残りの候補は25個。その中から2番目の場所（赤い四角で囲ってあります）を選んだのが、下の図です。
さて、次は3番目なのですが、よくよく考えると、ここで全部の候補を調べる必要はないですよね。3番目に選ぶところは、1番目、2番目に選んだところ両方と連絡できなければいけません。少なくとも最初に消した「1番目と連絡できないところ」は候補に入れなくていいですよね。なので、上の図の候補全て、25カ所と、2番目の場所が連絡できるかどうか調べましょう。連絡できないところは消すことにします。消したところで下の図になります。
残りは12個。この中から1個、3番目を選びましょう。次は4番目なのですが、同じく4番目を選ぶときには、「3番目を選ぶときの候補」の中から選べばいいですよね。残りは1,2,3番目のどれかと連絡できないので、選べません。3番目を選んで、3番目と連絡できないところを消したのが下の図です。これが4番目を選ぶときの候補になります。
以後同様に、「１つ選んで、選んだところと連絡できない候補を消す」ということを繰り返します。これを何回か行えば、どことどこでも連絡できる無線基地局、を作ることができます。さて、計測の回数ですが、最初は49回。でも、次は半分に減って25回。その次はまた半分に減って12回、となります。どの候補も、だいたい半分としか連絡できないので、平均的には毎回半分くらいになりますよね。ということは、「等比数列の和」というやつになりまして、合計100回程度のテストをすれば無線基地局ネットワークができる、ということがわかります。7カ所の候補を選んだら、普通の方法だと300回程度かかるので、これは大きな経費削減ですね。
すでにえらんだどれかと連絡できない不要な候補をあらかじめ消しておくことで、あとの苦労を減らすっていう所がミソです。今日できることを明日に延ばすな、ってやつですね。わかりました？？？
