58

九州産業大学情報科学会誌

1
10巻1号 (2011年11月)

電話連絡網アルゴリズムへの招待 (その 1)
朝廣 雄一

Yuichi ASAHIRO

九州産業大学 情報科学部 情報科学科
Faculty of Information Science, Kyushu Sangyo University

asahiro@is.kyusan-u.ac.jp, http://www.is.kyusan-u.ac.jp/~asahiro/

1. はじめに：台風が来るので休校です

について書きます．最後のアルゴリズムの評価に関しては，実験的な評価ではなく，理論的な評価を行います．

私が高校生の頃に，住んでいた地域へ向かって台風が夜間のうちに接近してきていました∗1 ．当時の私は，通っていた高校から結構離れたところに住んでいました∗2 ．さ

2. 電話連絡網の設計て翌朝，風雨が強い中，いつもの時刻に家を出て高校にまず，課題 (問題) を明確に決定する必要がある∗4 ．電向かいました．ところが，高校に着いてみると休校です．

話連絡の目的としては，先生がクラスの生徒全員に何ら私が家を出た後に，クラスの電話連絡網により，休校のかの連絡をすることである．連絡をする際に，先生が全電話連絡が来たそうです．

員に直接連絡する必要はなく (もちろん連絡してもよい)，∗3

さて，以上の思い出に浸りながら ，この記事では電連絡が伝わった人が別の人に連絡をしても良いとする．ま話連絡網の設計について書きます．電話連絡網についてた電話で連絡する間に，(伝言ゲームのように) 伝わる情本気で議論したいわけではなく，電話連絡網を題材にし報が変化したりはしないとする．て，私が行っているアルゴリズムに関する研究の雰囲気さらに以下を仮定する．

を紹介することが本記事の目的です．電話連絡網は今や［仮定 1］ 電話は同時に 1 人にしかかけられず，連絡時代遅れで，「クラスへの連絡なんてメールです」という内容を伝えるのに必要な時間は，正確に 1 分 (1 分より長ご意見の方は，余興だと思って読んで頂ければ幸いです．

くも短くもない) とする．

もしくは，以下で「人」と「電話」と書いてある語句をこの仮定は，現実の電話連絡を反映したものではない．

「コンピュータ」と「データ通信」と読みかえてもらい，例えば 3 者間通話が出来たりするし，1 回の電話に必要複数のコンピュータ間でのデータ共有の話と理解してもな時間が正確に 1 分のはずはない．また，例えば，電話らうと良いかもしれません．なお，本記事で説明する内をかけるのに必要な時間が何らかの確率分布に従うなど

容は，高校生対象の模擬講義で何度か話した内容でして，として期待値で評価するなど言い出すと複雑になるので，岩間一雄先生の著書 [1, 1.2 節] にある，“共通テストの順

ここでは，このような単純な仮定をおくものとする．

位と点数を連絡する方法” を，ずっと簡単にした内容とも言えます．

以上の問題設定において，出来るだけ早く全員に連絡するための電話連絡アルゴリズムを設計したい．アルゴ

アルゴリズムという語句は，“(計算) 手法” と理解でき

リズムの役割はどういう順序で，誰から誰へ連絡するかます．なにか目的 (課題) があって，それをどのように解を指示することである．すなわち電話連絡網の構造その決するかという，解決方法と言っても良いでしょう．ア

ものがアルゴリズムである．以下に続く節において，簡ルゴリズムの研究とは，以下のような流れで行われるこ

単なものから若干複雑なものまで，いくつかのアルゴリとが多いと思います．

ズムとその性能に関する評価 (解析) を紹介する．アルゴ(1) 目的 (課題，問題) を明らかにし (難しく書くと，明確に定義し)，(2) アルゴリズムを設計し，(3) 設計したアルゴリズムを (理論的または実験的に)リズムの名称として，難易度の相対関係を表すように学校の階層を用いる∗5 ．

3. 小学生アルゴリズム 1

評価する．
以下では，この流れにそって，電話連絡網アルゴリズム∗1 南九州に住んでいました．福岡に住むようになって驚いたことの一つは，台風がほとんど接近しないことです．他に驚いた
ことは，ラーメンの麺が細いというのもありますが，書き出すときりがないのでやめます．
∗2 私が通っていた高校は，朝の課外授業というのか (1 時間目の前の勉強?) がなかったので，朝は結構ゆっくりで良いはずなのですが，自宅の最寄りのバス停を通る 2 番目の便 (始発の次の便) に乗らないと遅刻する程度に離れていました．
∗3 ごめんなさい．嘘を書きました．

本節では，小学生でも考え付きそうなアルゴリズムについて説明する∗6 ．まず例として，クラスの生徒数が 15∗4 ここから，「です・ます」調から「である」調に文体を変更します．例えば卒業論文などを執筆する際には，全体を通して文体を統一する必要があるので，このように途中で文体を変更することをお勧めしない．
∗5 その学校レベルで学習する算数または数学で，そのアルゴリズムの解析が理解できるような対応関係が緩やかにある (が厳密ではない)．
∗6 実際の小学生は，もっと賢いと期待される．

2
電話連絡網アルゴリズムへの招待（その1）

1

先生

アイナ

2

イーサン

3

九州産業大学情報科学会誌

ウッディ

1

先生

アイナ

10 巻 1 号（2011 年 59月）

2n権兵衛

4
5エリオット6オリヴァー

7カマリア

図2

キタモト

8
クリス

9

セシリア

ケリィ

10

コバヤシ

11131312

シャルロッテ
スレンダー

14

セシリア

1514

スレンダー

サリー

12
シャルロッテ

小学生アルゴリズム 1 (n 人の場合)

サリー
ソフィ

1110

コバヤシ

9
ケリィ

図1

小学生アルゴリズム 1 (15 人の場合)

図3名とする．

ソフィ
アイナ
151
イーサン
2
3
ウッディ
先生
4

クリス

8

7
キタモト

56エリオット
オリヴァー

カマリア

小学生アルゴリズム 2 (15 人の場合)

図 1 に示すのが，小学生アルゴリズム 1 であり，四角で囲まれたものが人間であり，矢印が誰から誰へ電話をかけるかを表している．矢印の近くにある数字は，先生が最初の電話をかけ始めてから何分目にその電話が行われているかを表す．例えば，図 1 では 1 分目に先生がアイナに電話をかけ，2 分目にはアイナがイーサンに電話をかける，と理解する∗7 ．紙面の都合で，途中で折り返しているが，生徒を一列に並べ，列の先頭に先生が連絡した後，連絡を受けた人は順に次の人へ連絡していくものが小学生アルゴリズム 1 と考えるとよい．
実際の電話連絡網においては，全員へ連絡が伝わったことを確認するため，列の最後の人は先生に電話をかけるように指示されることがある．よって，実際の電話連
絡網について何らかの知識を持つ読者は，小学生アルゴ
リズム 1 が不完全なものに見えるかもしれない．しかし話を簡単にするために，本稿ではその最後の電話は必要ないとする．本来は先に書くべきであったが，以上の説明の都合で，ここに問題の仮定として記載する．
［仮定 2］ 列の最後に位置する人は，先生に電話をしない．
さて，小学生アルゴリズム 1 の性能を評価する．性能と書くと大げさに聞こえるが，ここでは，最後の人への連絡が完了するまでに必要な時間 (完了時間と呼ぶことにする) を評価する．とりあえずは，この完了時間が短いほど，良いアルゴリズムと考えてよい∗8 ．図 1 から，以下のことが分かる．
［特徴 1］ 15 人の生徒に対して，小学生アルゴリズム∗7 どこの国のクラスかなどと気にしてはいけない．某ロボットアニメの one year war 時代のキャラクタ名の一部であり，かつ普通に利用されているものを選んだ．これを見て，該当キャラクタのフルネームとビジュアルを即座に思い浮かべられる人は，かなりの通と思われる．実は，本稿で最も時間がかかった部分は，この名前を選ぶところである．
∗8 他の評価基準もあり得る．

1 の完了時間は 15 分である．
ところで，クラスの生徒数が 15 人とは限らないので，より一般的な人数に対しても同様に考える必要がある．
クラスの生徒数を記号 n で表すことにする∗9 ．生徒数がn 人の場合には，図 2 のように電話連絡が行われる (最後の生徒名は権兵衛とした∗10 )．よって以下の定理が得られることは，容易に分かる．
［定理 1］ n 人の生徒に対して，小学生アルゴリズム

1 の完了時間は n 分である．
以下の節で他のアルゴリズムを紹介し，これらのアルゴリズムの性能を比較する．この際には，15 人といった具体的な数値に対する性能の比較よりも，この一般的なn 人に対する性能で比較を行うことが汎用性の観点から重視される．

4. 小学生アルゴリズム 2
小学生アルゴリズム 1 は，先生は 1 回だけ電話をかけ，あとは生徒で頑張っている印象のあるアルゴリズムである．さて，「先生はもっと働くべきである」という意見もあるかもしれないので∗11 ，それに耳を傾け，先生が生徒全員に直接連絡するという，小学生アルゴリズム 2 を考える．図 3 が 15 人の場合の小学生アルゴリズム 2 である．仮定 1 により，先生からは同時に 1 人にしか電話をかけられないので，このアルゴリズムには以下の特徴がある．
［特徴 2］ 15 人の生徒に対して，小学生アルゴリズム∗9 「なぜ数多ある記号のうちから，n を選んだのか?」という問に答えると the number of students の n である．
∗10 名無しである．
∗11 緊急連絡のためのものを，そのような基準で評価することが適切とは思えないが．

電話連絡網アルゴリズムへの招待(その 1)
60

先生

12アイナ

九州産業大学情報科学会誌

先生

1ア

2

イ

3

3
10巻1号 (2011年11月)

ウ

4エ

5オ

2イーサン

3カ

3

キ4ク

5ケ

6コ

nサ
図5権兵衛
図4

小学生アルゴリズム 2 (n 人の場合)

先生

14シ

5ス

6セ

7ソ

中学生アルゴリズム 2 (15 人の場合)

s1,12

s1,23s1,n/3

2
2 の完了時間は 15 分である．
一般の n 人に対する小学生アルゴリズム 2 を図示すると，(図 3 と少し書き方が異なるが) 図 4 のようになる．

3s2,1 3s2,2 4s2,n/3s3,1 4s3,2 5s3,n/3

そして，このアルゴリズムの性能について以下の定理が
図6得られる．
［定理 2］ n 人の生徒に対して，小学生アルゴリズム2 の完了時間は n 分である．
以上のように，小学生アルゴリズム 1 と小学生アルゴリズム 2 は，ずいぶん様子の異なるアルゴリズムであるが，完了時間を評価すると全く同じ性能を持つことが分かる．次の節では，もう少し複雑なアルゴリズムについて説明する∗12 ．

5. 中学生アルゴリズム 1
ここまでに説明した小学生アルゴリズム 1，小学生ア
ルゴリズム 2 は，筆者が実際に目にしてきた電話連絡網とは非常に異なる構造を持つ∗13 ．具体的には，生徒を何

中学生アルゴリズム 1 (n 人の場合)ある．
［特徴 3］ 15 人の生徒に対して，中学生アルゴリズム

1 の完了時間は 7 分である．
特徴 1 や特徴 2 と比較して，このアルゴリズムの完了時間は約半分である．生徒を 3 列にすることにより，完了時間を約半分にすることが出来たわけである．ここから得られる結論として，どちらか片方だけではなく，先生と生徒両方が努力することが良い結果をもたらす ∗15 という思想を述べても良いのだが，それは本稿の目的ではない．たしかに生徒数が 15 人の場合には，完了時間が約半分になったが，それは生徒数が何人でもそうであるのか? ひょっとすると，生徒数が多かったり少なかったり列かに並べ，先生は列の先頭の生徒に連絡し，後はそのすると，完了時間は半分よりも長くなったり短くなった列にそって電話連絡を行うのが一般的であるように思わりするのではないか? という次の疑問について考えたい．

れる．本節では，そのような構造の電話連絡網について［疑問 1］ どのような生徒数であっても (どのような n議論する．

に対しても)，生徒を 3 列にすると，完了時間は小学生ア

生徒を 3 列に並べることを考える．生徒数 n が 15 の場合，15/3 = 5 なので，各列を 5 人ずつとする．このように設計した電話連絡網が図 5 である．特に意味はな

ルゴリズム 1，2 と比較して約半分 (n/2 程度) となるか?
ここからの話を簡単にするために，以下の仮定をおく．

うように，ある時間帯に複数の連絡が同時に実行される［仮定 3］ n は 3 の倍数とする．
3 列に生徒を分けるので，n/3 人ずつの 3 列を作ることになる．i 列目 (i は 1，2，3 のいずれか) の先頭から j番目 (j は 1 以上 n/3 以下の整数) の生徒を si,j と呼ぶことにする∗16 ．生徒数が n の場合の中学生アルゴリズム
1 を図示すると図 6 のようになる．この図において，列ところである．このアルゴリズムにおいては，小学生アの最後の生徒への連絡を示す矢印に何分目かを書いていいので∗14 ，今後は図中の生徒名は頭文字だけを示す．このアルゴリズムがこれまでの 2 つのアルゴリズムと大きく異なるのは，例えば 2 分目には，アからイへの連絡が行われるとともに，先生からカへも連絡が行われるといルゴリズム 1 よりも先生が多く電話連絡し，小学生アルゴリズム 2 よりは生徒も多く電話連絡することになる．
このアルゴリズムには，図から分かるように次の特徴が∗12 今までも十分に複雑で，これ以上ついていけないという読者が少ないことを期待する．
∗13 小学生アルゴリズム 1 や小学生アルゴリズム 2 のような電話連絡網をご存知の方は御一報頂きたい．
∗14 「意味がないなら始めからやるな」というご指摘はごもっともである．

ないが，それについて以下で議論する．
いきなり全体を考えるのは大変なので，1 つの列だけに注目する．各列の先頭 si,1 から列の最後 si,n/3 だけを見ると，si,1 を先生と考え，その後ろに n/3 − 1 人の生徒が並んでいると考えた小学生アルゴリズム 1 と同じ構
∗15 努力が無駄になる場合もある．
∗16 「なぜ s を選んだのか?」という問に対する答は「Studentの s である」．

4
電話連絡網アルゴリズムへの招待（その1）九州産業大学情報科学会誌

10 巻 1 号（2011 年 61月）

造をしている．よって，定理 1 より，si,1 が連絡を行っ

わち，n が 3 の倍数か否かに関わらず，完了時間がてから，n/3 − 1 分後に，この列全体へ連絡が完了する．

n/3 + 2 のアルゴリズムを設計できると言える．
(2) n が 3 の倍数で，列数を 3 とする場合は，中学生アルゴリズム 1 に対して少し工夫することにより，完了時間を 1 分減らして n/3 + 1 分に出来る．どうすればよいか?
(3) 生徒を 3 列ではなく，同じ長さの 5 列にすると完了時間はどうなるか? いい加減な答を書いておくと，大体 n/5 分になる∗19 ．
(4) 中学生アルゴリズム 1 と (3) より，3 列にするとn/3 になり 5 列にすると n/5 になるように，列数を増やすと完了時間がどんどん短くなる．では n 列にすると n/n = 1 分で完了するのではないか? そんなはずはない．それは小学生アルゴリズム 2 であり n分必要なはずである．どこの議論が変なのだろうか?
何列に分けると，完了時間が最も短くなるか?∗20(5) 上の (1) と (2) のヒントでもあるのだが，列に分けすなわち，以下の補題を得られる．
［補題 1］ i 列目の先頭の生徒 si,1 に先生から連絡が届いたのが ti 分目だとする．すると i 列目の最後の生徒
si,n/3 に連絡が届くのは ti + (n/3 − 1) 分目である．
上の補題から，中学生アルゴリズム 1 において，以下のことが分かる．

• 1 列目の連絡が完了 (1 列目最後の s1,n/3 に連絡が到達) するのは，1 + (n/3 − 1) = n/3 分後である．
• 2 列目の連絡が完了 (2 列目最後の s2,n/3 に連絡が到達) するのは，2 + (n/3 − 1) = n/3 + 1 分後である．
• 3 列目の連絡が完了 (3 列目最後の s3,n/3 に連絡が到達) するのは，3 + (n/3 − 1) = n/3 + 2 分後である．
よって，一番最後に連絡が届くのは，3 列目の最後 s3,n/3であるので，以下の定理を得ることができる．
［定理 3］ n 人の生徒に対して，中学生アルゴリズム
1 の完了時間は n/3 + 2 分である．
疑問 1 では，約半分 (n/2) になるのではないか，と書いたが，中学生アルゴリズム 1 の完了時間は，小学生ア
ルゴリズム 1，2 と比べて，約 1/3 になっていることが分かる∗17 ．以上のようにくどくどと書くことでもないかもしれないが，3 列にしたから 1/3 の時間で良くなったというのが直観的な捉え方ではある．ところで，n = 15 の場合に完了時間が約 1/3 であるとは理解せず，約 1/2 とる際に列の長さを統一する必要はない．うまくやると，(4) よりも完了時間を短くすることができる∗21 ．

(6) 仮定 2 に関連して，列の最後の人は先生に確認の電話をしないといけないとすると話が変わってくる．
例えば，生徒数が 15 人の場合の小学生アルゴリズ
ム 1 は，最後のソフィが 16 分目に先生に電話をかけて，それで終了できるので，完了時間は 16 分になる．小学生アルゴリズム 2 はどうだろうか? 小学

考えてしまった理由は，完了時間の式にある “+2” にあ生アルゴリズム 2 では列に 1 人しかいないので，先る．計算してみると分かるが，15/3 + 2 = 5 + 2 = 7 と生に確認の電話をかけるのはそもそも無駄であるが，なり，n/3 の部分に対して 2 が占める割合が大きいため，そのようなちょっとした誤解を生むことが理解できる．

6. おわりに (宿題を含む?)
電話連絡網アルゴリズム 3 個の設計と，それらの性能の評価 (解析) について説明した．実は，本記事の内容には続きがあり，中学生アルゴリズム 2，高校生アルゴリ
ズム 1，2 というものも用意してあるのだが∗18 ，また次回，本誌に執筆する機会があれば続きを書きたいと思う．
タイトルに “（その１）” と付けたのは，このような理由無理矢理考えてみる．1 分目に連絡をもらったアイ
ナは，2 分目に確認の連絡を先生にしようと試みるが，先生は話中 (イーサンに電話中) なので連絡できない．どうするのか?
(7) 本稿の最初に書いた思い出話に関係あるが，実際の電話連絡網を作成する場合には，自宅の位置を考慮し，自宅が遠い人の方に先に連絡が届くようにする必要があると思われる．

♦ 参 考 文 献 ♦
岩間一雄，アルゴリズム理論入門，昭晃堂，2001．のためである．
本文中の仮定などについていくつか補足を書き，終わりにする．興味のある読者は暇潰しに考えてみて欲しい．

(1) 仮定 3 で，n は 3 の倍数であるとしたが，3 の倍数でない場合にどうするか? 列数を 3 とすると，中学生アルゴリズム 1 を少し変更することで，完了時間が n/3 + 2 分のアルゴリズムを設計できる．ここで n/3 は n/3 の小数点以下を切り捨てた整数であり，n が 3 の倍数の場合は n/3 と等しい．すな∗17 約 3 倍の速度で連絡が進むので，Red Comet アルゴリズムという別名を付けたい．
∗18 というより，それらが本題である．

∗19 この点を考慮したものが，中学生アルゴリズム 2 である．
∗20 この点を考慮したものが，高校生アルゴリズム 1 である．
∗21 この点を考慮したものが，高校生アルゴリズム 2 である．