TarZの日記： 「トリビアの種」と二分探索の拡張アルゴリズム 5
1/26(水)放送のトリビアの泉で、「トリビアの種」がなかなか興味深い内容だった。いろいろと
考えることがあったので、忘れないうちにメモ。
… … … …
■種
「ファミリーレストランの呼び出しベルは、どれくらいの距離まで店員さんを呼べる？」
（呼び出しベルで一番普及しているのがベルスターという商品だそうで、無線（電波）でボタンが
押されたことを店に通知する。この電波が、どの距離まで届くのかを調べようという趣旨）
■結論
「ファミリーレストランの呼び出しベルを外に持ち出した時、117mまで店員さんを呼べる」 九分咲き
… … … …
番組での調査のやり方はこうだ。
まず店外にテーブル席を設け、そこで呼び出しボタンを押す。店員が注文を受けに来るようであれば
電波が届いていると判断し、テーブルをファミレスからさらに5m離して同じ手順で試行する。
0m 5m 10m … 115m 120m ← 調査ポイント
┃ ┃ ┃ … ┃ ┃
↑ ↑ ↑ … ↑ ↑
(1) (2) (3) (24) (25) ← 試行回数
OK OK OK OK *NG!* ← 試行結果
0m, 5m, 10m, ... 115m(OK), 120m(*NG!*) 120mで電波が届かないと判明するまでに試行回数は25回。
正確なポイントを突き止めるため、ここから調査ポイントを1m刻みで減らしていく。
115m 116m 117m 118m 119m 120m
┃ │ │ │ │ ┃
↑ ↑ ↑ ↑ ↑
(24) (28) (27) (26) (25)
OK *OK!* NG NG NG
119m(NG), 118m(NG), 117m(*OK!*) ときて、結論「117mまで届く」となるまでに28回試行している。
# 事前のタモリの予想は「30mくらいではないか」。私も100m以上届くことにびっくりした。
# ベルスターの性能としては、もともと120mくらいまで到達するらしい。
試行回数が多く、終盤は、店員さんが来ても注文するものが紅茶ばかりになっていた。(笑)
店員さんも大変だし、ボタンを押す担当の外人さんもずっと店外で寒そうだった。番組的には
面白いのでこのやり方でOKだが、より試行回数を減らしたい場合はどうすればよいだろう。
… … … …
「電波が届くかどうかは、距離の大小によってのみ決定する」という理想的な条件で実験が
行われたとすると、これはソートされたデータ列から目的のデータを探す問題に等しい。
「ある地点で電波が届く」かどうかは、「あるポイントのデータが目的のデータより小さい」
かどうか、ということに置き換えできる。
これが、ある決まった区間内で電波が届くかどうかのポイントを見つける問題であれば、
二分探索でよい。n個の区間から二分探索するときの計算量（試行量？）は O(log2n) という
オーダーになる。具体的には、log2n +1回の試行で十分だ。例えば、100mの区間から1mの精度で
ポイントを探すなら、log2(100)=6.6なので、最悪でも7回の試行で目的のポイントを見つけられる。
しかし、今回のトリビアの種では、どこまで電波が届くのか全く不明という前提で実験していた。
この場合は、単純な二分探索ではできない。
そこで、二分探索を拡張してみる。探索範囲を大まかに調べる第1段階と、正確な場所を割り出す
第2段階に分ける。第1段階では、調べる範囲を倍々に増やしていく。あるところで範囲が確定する
ので、そこからは通常の二分探索に切り替える。
実際にトリビアと同じ条件でやってみよう。（簡単にするために、1mからスタートとする）
1m(OK), 2m(OK), 4m(OK) ... 64m(OK), 128m(*NG!*) となるので、8回目で「128mで電波が届かない」
ということが分かる。ここからは普通の二分探索に切り替えるが、探索範囲は全体の半分の65～127m
なので、最悪でも6回の試行で見つかる。つまり、今回の場合はトータルで14回以下の試行で117m
というポイントを見つけられるということで、番組のやり方の半分ちょっとの試行回数で済む。
トリビアの種で行っていた「一定間隔」刻みだと、距離に比例して試行回数が増える。もし電波の
到達距離が2倍であれば、試行回数も2倍になる。
ここで挙げた拡張二分探索の場合は、距離が2倍になっても試行回数は2回増えるだけで済む。
この場合の計算量(?)としてはやはり O(log2n) のオーダーで、具体的な試行回数にすると
最悪でも log2n *2 +1 回となる。
なんとエキサイティングなアルゴリズムでしょう！ **素晴らしい！**
… … … …
似たような遊びで、数当てゲームがある。
相手に、1～1000までの数で1つ思い浮かべてもらう。こちらが言った数に対し、思い浮かべた数が
大きいか小さいかを答えてもらい、ある回数以内で当てるというものだ。
トリビアの種は、この数当てゲームで範囲制限なし、自然数全体に広がったケースと思えばよい。
アラビア数字として紙に書き出せるようなサイズの数であれば、拡張二分探索なら現実的な時間で
正解を見つけ出せる。
相手が思いついた数が、既知の最大のメルセンヌ素数だったとしても、拡張二分検索なら試行回数は
1億回に満たない。人間にはムリだろうが、コンピュータならどうにか回答にたどり着けるだろう。
# 二分検索で1億回の試行を要求するメルセンヌ素数の巨大さも、ある意味すさまじいのだが。
… … … …
ところで、せっかく思いついたこの拡張二分探索、どこかに応用できる分野はありませんかね。
純粋数学ならともかく、アルゴリズムで応用分野がないと、ホントにtrivia（ムダ知識）で
終わってしまうんですが。
増加量 (スコア:1)
倍々に増える測定値が実体に合わないこともあるかと。
呼び出しベルは電磁波なので、減衰が距離の2乗に反比例する。
-> f(n+1) = sqrt(2) * n くらいの増加量の方が早いかも
# 測定値の間隔が広すぎるのもいけないわけで...
数字当ても素数に限るなら素数定理を導入するとか
# 未証明なんですけどね(w
# 最適値は決めにくいんでしょうけど...黄金比とか自然対数の底とか色々よさげな係数はあるわけ
などと妄想してみた。
M-FalconSky (暑いか寒い)
残念ながら・・・ (スコア:1)
（doublingの手続きまでを含めて，二分探索と言うことも多い）
Re:残念ながら・・・ (スコア:1)
Re:残念ながら・・・ (スコア:1)
> ところで、せっかく思いついたこの拡張二分探索、どこかに応用できる分野はありませんかね。
に対して，アルゴリズム分野（？）では普通に使われています，といっているわけです．
とりあえず (スコア:0)
もちろん解説は秋山仁先生を指名
# 応用じゃねぇょ :-)