この記事は、ミラパブのメンター・米田優峻さん（E869120）にご寄稿いただいたものです。
皆さん、アルゴリズムをご存知でしょうか。
アルゴリズムとは、主にコンピュータを使って問題を解く方法のことです。計算の手順、と言っても間違っていないと思います。
ここで、同じ問題を解くにしても、たくさんのアルゴリズムが考えられます。そしてアルゴリズムの工夫によって計算が高速になり、100 年かかるはずの問題が 0.01 秒で解けることがあります。
例として、1 から 50 までの足し算をすることを考えてみましょう。1+2=3、3+3=6、6+4=10、という感じで単純に 1 個ずつ足していくと、以下のように 49 回の計算がかかります。
しかし下図のように、1 から 50 までのカードとして考え、合計が 51 になるようにペアにする、という別の方法を使うと、1 回の掛け算で答えが分かってしまいます。このように、アルゴリズムの工夫で、計算にかかる時間が大きく変わります。
今回は「100 年が 0.01 秒になる」を体感できる迷路の問題をベースに、中高生向けにアルゴリズムの面白さを説明していきます。アルゴリズムを学ぶと、いま重要なプログラミング的思考力も上がります。後半に楽しい「アルゴリズム・パズル」も用意しておりますので、ぜひお読みいただければと思います。
1. 迷路の問題
以下の迷路について、スタートからゴールまで何手で移動できるかという問題を考えてみましょう。1 手では、上下左右の方向に移動することができます。
この問題を解く一番簡単な方法は、あり得るすべての経路を全列挙することです。全部の経路の中で一番短いものを計算すると、理論的には答えを出すことができます。
しかし、一体どれくらいの数の経路があるのでしょうか。同じマスを通らないものだけを考えますが、10 万通りの経路を計算しても、まだ答えが出ません。
100 万通りの経路を計算しても、まだ答えは出ません。
最終的に、3,400 万通り以上の経路を探索し、ようやく答えが出ました。スタートからゴールまで 27 手です。しかし、現代のパソコンでは 1 秒で数千万通り程度しか計算できないため、迷路を解くだけで 1 秒かかってしまいます。
さらに迷路が大きくなると、探索パターン数が数十億通りを超え、数分経っても答えが出なくなります。その倍の大きさになると、数千兆通りまたはそれ以上の経路のパターンを調べる必要があり、100 年かかっても答えが出ません。
たとえば、毎秒 1 億通り探索できると考えても、もし探索パターン数が 10 の 18 乗 (1 兆の 100 万倍) になれば 300 年以上かかる計算になります。その 10 の 18 乗という数字は、20x40 程度の大きさの迷路であれば十分あり得る数字です。
2. 迷路の問題の解法
そこで、アルゴリズムを工夫してみましょう。まず、スタート地点に「0」を書きます。それに隣り合うマスに「1」を書きます。
次に、「1」に隣り合うマスに「2」を書きます。
次に、「2」に隣り合うマスに「3」を書きます。この「3」という数字は、スタートから最短で 3 手でたどり着けるという意味です。
それを 4, 5, 6, 7 と続けていきます。
すると最終的には、ゴール地点に数字「27」が書かれます。書かれた数字が最短の手数です。
続いて、どの経路が最短であるのかを調べていきましょう。下図のように、ゴールから順に、27, 26, 25, 24, ... と数字が下がる方向に進んでいくと、実際の最短経路を得ることができます。なお、このような方法は幅優先探索と呼ばれています。
最初の方法では何千万通りも調べる必要がありました。しかし、アルゴリズムを工夫すれば、人間でも頑張れば計算できる程度の問題に変わり、コンピュータであれば 0.01 秒で答えが出ます。アルゴリズムは、文字通り、100 年かかる問題を 0.01 秒で解くことができる、魔法のような技術なのです。
3. アルゴリズムと世界
それでは、アルゴリズムはどのようなところで使われているのでしょうか。
まず、最も分かりやすい例として、経路検索があります。東京駅から新宿駅まで、車でどのように行けばよいかを考えます。一番簡単な方法は、駅間の経路をすべて調べることですが、東京は道路が非常に密集しているため、何億通りもの経路があり、コンピュータをもってしても計算できません。そこで、ダイクストラ法という方法を使うと、数秒以内で答えを求めることができます (※実用上は、さらに賢いアルゴリズムが使われています)。
もう一つの例として、数字を大きい順に並べ替える「ソートアルゴリズム」があります。たとえば、生徒を得点順に並べたい場合など、数字を大きい順に並べたい場面は実生活でも多いです。しかし、場合によっては数万件のデータを処理する必要があり、自然な方法では実行に数秒から数分かかってしまいます。そこで、クイックソートなどの方法を使うと、わずか 0.01 秒で答えを求めることができます。
4. アルゴリズム・パズルに挑戦
それでは、皆さんも「アルゴリズムの工夫」をぜひやってみましょう。実際にプログラムを書く、というのは初心者には大変なので、以下のパズル問題を考えてみてください。
問題 1
A 君は、1 以上 10 以下の整数を思い浮かべています。Yes か No かで答えられる質問を 5 回以下行うことで、A 君の思い浮かべている整数を当ててください。
見て良いヒント: 以下のように、答えは 1 ですか、答えは 2 ですか、答えは 3 ですか、という質問を順に繰り返すと、答えが 10 であった場合に 9 回の質問をする必要があります。それではゲームに勝つことができず、何らかの「アルゴリズムの工夫」が必要です。
問題 2
A4 用紙があります。線を引く、という操作をできるだけ少ない回数行うことで、同じ大きさの正六角形を 10 個切り出す方法を考えてください。
見て良いヒント: たとえば以下のように、1 個ずつ正六角形を描くと、合計で 10×6=60 回、直線を引く必要があります。それより少ない回数は出来るのでしょうか。ちなみに、かなり難しいですが、頑張ると 12 回まで減らせます。
問題 1 の解答
最初に「5 以下ですか？」と聞いてみましょう。すると、答えが Yes の場合は 1, 2, 3, 4, 5 のいずれか、答えが No の場合は 6, 7, 8, 9, 10 に絞り込むことができます。
後は 1 個ずつ聞いていけばよいです。たとえば No の場合、6 ですか、7 ですか、8 ですか、9 ですかと順に聞き、すべての回答が No であった場合は 10 が答えになります。
ちなみに、もう少し工夫すると 4 回まで減ります。以下のように、現在あり得る範囲の真ん中を聞くという方法です。そのような方法は、アルゴリズム界では二分探索と呼ばれており、実用上の様々な場面で使われています。
問題 2 の解答
様々な方法があります。まず画像左のように、六角形を重ねるという方法があり、その方法を使うと 60 回から 41 回まで削減できます。
もう少し思いつくのが難しい方法として、画像中のように上下 2 列の長い直線を引き、それを通る斜線を各方向 11 回ずつ書くという方法があります。それで 24 回まで削減できます。
最後に、画像右のように 3 方向の長い直線を引き、さらに紙の端を有効活用すると、12 回に削減することができます。
5. アルゴリズムに興味を持った皆さんへ
今回の記事で、アルゴリズムやプログラミング的思考に興味を持った方は、競技プログラミングがおすすめです。競技プログラミングについては、以下の記事に書かれておりますので、ぜひお読みください。
宣伝: ミラパブについて
現在、ミラパブは外部の優秀な人材を生かし、中高生の能力を開花させようとする活動を行っています。興味のある方はこちらのページから応募ください。また、大学生以上でメンターに興味のある方はこちらのページをご覧ください。私もメンターであり、既に出張授業を 10 回ほど経験しております。