「楽しいパズルを解くように、アルゴリズムやプログラミングが使えたら……？」
ITエンジニアの無期雇用サービス「BUILDICT」主催にて、関西エリア在住のエンジニアに向けたイベントを実施しました。数理工学を専門にしている大槻兼資さんを講師としてお迎えし、とっつきやすいパズルを用いて、アルゴリズムの基本や応用を理解できるイベントです。本レポートでは、その様子をお届けします。
【講 師】大槻兼資さん
1988 年生まれ。2014 年東京大学大学院情報理工学系研究科修士課程修了。修士（情報理工学）。現在、株式会社 NTT データ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の諸分野の教材開発や啓蒙活動に従事。「けんちょん」の愛称で親しまれている。著書に『問題解決力を鍛える！アルゴリズムとデータ構造』（講談社）がある。数理最適化や機械学習を活用した数理コンサルティング業務の経験も多数。趣味は競技プログラミング、虫食算作り、国内旅行など。
アルゴリズムとは、問題を解くときに普遍的に使える手順や方法
大槻さんが自己紹介のあとに説明したのは「アルゴリズム」という言葉の定義です。アルゴリズムとは、「ある問題を解くための方法、手段」のこと。アルゴリズムをコンピュータ上で動作するように実装したものが「プログラム」ということです。
アルゴリズムはあくまで「考え方」の部分を指すのであって、コンピュータ上で動作するものであるかどうかは関係ないようです。実際、身近なアルゴリズムの例として「料理のレシピ」などを紹介されていました。
ここで、アルゴリズムを使って実際にパズルを解いていきます。
「Sがスタート、Gがゴール。1回で上下左右に1マスだけ動くことができるとき、最短で何手でゴールできるか、考えてみてください」（大槻さん）
参加者の方々に呼びかけて答えてもらうと、「16」と正解が出ました。
「では、どうすれば『16が最短だ』と言い切れるでしょうか。また、場面が変わっても通用する方法を見出すにはどうすればいいでしょう。それを見出すのがアルゴリズムです」（大槻さん）
まず、スタートから1手で行ける箇所に「1」を記します。その後、2手で行けるところに「2」、3手には「3」と続けていくと、ゴールには16手でたどり着くとわかります。
最短の手数がわかったところで、「最短経路をどう求めるか？」を大槻さんが参加者に尋ねました。「ゴールから行く」と答えた方が大正解。スタートから行くと分岐があるため、どちらに進んでいいかわかりませんが、ゴールから1ずつ減少する数をたどっていけばわかります。同じ数で分岐がある場合は、どちらに行っても最短経路となります。
「このアルゴリズムは、違う迷路にも対応できるのがすごいところで、カーナビや電車の乗換案内にも応用されています。ほかにも、15パズルの最短手数なども同じ解き方になります」（大槻さん）
このようなアルゴリズムパズルを解けるようになると、さまざまな力が身につきます。
- 問題を理解する力（理解力）
- ロジカルに考える力（思考力）
- コーディング力（技術力）
- アルゴリズムを説明する力（説明力）
- 何かを楽しんで主体的に楽しんだ経験そのもの
「これらは、キャリアだけでなく、実生活でも大いに役立ちます。IT技術も含めて考えると、AIや量子コンピュータなどの流行にとらわれない、一生もののスキル。また、畑違いの分野でも、似たような問題をたくさん抱えており、同じ方法で問題を解決できる機会が多くあります。さらに、プログラミングではライブラリの仕組みを理解し、速度性能を上げる勘所をつかめるようにもなります」（大槻さん）
グラフでモデル化すると、さまざまな問題に応用ができる
さまざまな問題を解決するためにモデル化すると、現実世界の問題を言い換えてパズルのように捉えられ、アルゴリズムで解くことができます。今回紹介するモデルの例として、大槻さんは「グラフ」を紹介しました。
折れ線グラフや棒グラフとは異なり、物事の関係性を〇と線を使って表すもので、線に矢印がある有向グラフも存在します。〇は「頂点」、線は「辺」と呼びます。
世の中にあるグラフを参加者の方に上げてもらうと、次のような意見が出ました。
- 星座
- フローチャート
大槻さんは、さらにいくつかの実例をスライドに映しながら、それぞれの活用シーンなども紹介します。
- 友人関係
- 鉄道路線図
- 数独ソルバー
- 8パズルの最小手数
- タスクの依存関係（有向グラフ）
- 電気回路
- 家系図
- 化学式
- しりとり
- マッチング
「これらのアルゴリズムやパズルは単なる遊びではなく、何をやっていても似たような問題にたどり着くくらい、汎用的に使えるすごいものなんです」（大槻さん）
油断禁物。少しの違いで膨大な計算量や計算時間の差に！
休憩を挟んだあとの後半では、計算量の話です。プログラミングでは、わずかな計算方法の違いによって、驚くほどの計算時間の差が生まれてしまう場合があります。
大槻さんが例に出したのは、年齢当てゲーム。20歳以上27歳未満であるとわかっている人に対して、Yes/Noで答えられる質問を3回まで許されているとしたら、年齢を当てることは可能でしょうか。
実際に、大槻さんが20歳以上27歳未満の数から1つを思い浮かべて、参加者に質問をしてもらいました。
「24歳未満ですか」「ノーです」
「26歳未満ですか」「イエスです」
「25歳未満ですか」「ノーです」
3回の質問で、「25歳」と言い当てられました。質問した方は、「半分ずつ聞いていく」という手法を取りました。
「効率が悪いのは、『20歳ですか？』『21歳ですか？』と1つずつ聞いていく方法で、『線形探索』と言います。これは、最悪の場合7回聞かなくてはなりません。今のように半分ずつ聞いていくのは『二分探索』といい、3回で言い当てられます」（大槻さん）
では、次の問いです。
「例えば、1000通りのものを二分探索したら何回でできるでしょう？」
参加者に尋ねます。答えは「10回」。
「1000通りもあるのに10回で当てられるのは驚きませんか？」と大槻さん。
Yes/Noで毎回2通りに分けられるため、2×2×……と2を10回掛けると1024通り。それ以下であれば区別できるというわけです。
10倍サイズのデータを扱うと、所要時間が10倍になる、は間違い
「もっと大きくして、65535通りになった場合、線形探索では65535回かかりますが、二分探索法ではなんと16回で答えにたどり着けます」（大槻さん）
年齢当てゲームであれば6万通りもの場合を扱うことはありませんが、システムやサービスを扱うときには、ユーザー数がそのような値に到達することもあります。
「例えばソシャゲなどでは、ユーザー数が10万以上になることもしばしばあります。スコアを高い順に並べるといった簡単に見える問題でも、アルゴリズムを間違えると膨大な時間がかかってしまいます」（大槻さん）
※Twitter／現在はX
プログラムを組むうえで、データ量が10倍だから計算時間も10倍になる、というイメージを持っている方は多いものの、必ずしもそうとは限りません。10倍のサイズを扱って、100倍や1000倍になることもあります。逆に、2倍で済むケースもあります。
「計算時間を測るのが、『オーダー』という物差しです。Nに比例する計算時間をO(N)と表記してオーダーNと読み、N²に比例する計算時間をO(N²)と表しオーダーN・2乗と読みます。データ量が10倍なら計算時間が10倍になるのはO(N)のほうになります」（大槻さん）
この表では、データ量が10万から100万になると、処理速度が28秒から2900秒になっており、実際に100倍になっているのがわかります。これは、大槻さんが実際にMacBook Airを使って計測した結果です。ただし、O(N²)のほうの問題の大きさが100万以上の部分は、計算によって導いた数字になります。
ここで、与えられたデータをデータベースへ逆順に格納していく問題を考えましょう。
空のデータベースにデータを順に挿入したい。最後に挿入されたものが先頭に来るようにしたい。
例：鈴木君,渡辺君,青木君, → （青木君,渡辺君,鈴木君）
スライドは、Pythonを想定して記述しています。方法1ではリストの先頭に挿入します。方法2ではリストの末尾に挿入したあと、最後にreverseしています。このプログラムは、どちらかがO(N)で、どちらかがO(N²)となっています。
参加者に問うてみると、「方法1がO(N²)」と大正解でした。
「方法1では、鈴木君を入れたあとに渡辺君を入れるとき、最初に入れた鈴木君を後ろにずらしてから入れます。次は、鈴木君と渡辺君を後ろにずらしてから青木君を入れます。データが大きくなっていくと、毎回の操作で膨大なデータを後ろにずらす必要があるため、全体の計算量はO(N²)となるんです。一方、方法2は、毎回の操作で後ろに入れているので、後ろにずらす処理が発生しません。よって、全体の計算量はO(N)です」（大槻さん）
さらに、大槻さんが友人から相談されたという「2つのデータ系列の『共通の要素』の個数を求める」という問題にも、O(N²)が潜んでいた例を挙げました。
これは、スライド右側のように「set」に変え、ハッシュを使うことで解決しました。
「C++で実装する場合であっても、vector型で書いてみてから、set型を使うと違いがわかると思います」（大槻さん）
実装での活かし方。必ずしもO(N²)がNGではないことに注意
最初から高速化ができればスマートだが、必要のない場合もある、と大槻さんは言います。
「効率のよいアルゴリズムを考えるコツとしては、まずは愚直な方法で問題を問いてみましょう。愚直な方法は往々にしてO(N²)などの計算量になりますが、そのあとで、二分探索やsetなどを使ってO(N log N)やO(N)といった計算量にしていく、というアプローチがよいと思います。また、Nがそれほど大きくないとわかっているならば、O(N²)という計算量が必ずしも悪いとは限りません。O(N log N)の計算量のアルゴリズムがとても複雑なものであるとき、それを実装してしまうと、保守がしづらくなることもあります」（大槻さん）
イベントの時間が残り5分ほどになったところで、グラフ探索の幅優先探索や深さ優先探索を簡単に説明し、大槻さんはアルゴリズムのすばらしさを強調して締めくくりました。
「アリゴリズムは、どんな分野に挑戦するうえでも重要な基盤となるので、やっておくのはとてもおすすめです。また、純粋にとても楽しいので、アルゴリズムをどんどん楽しんでいただきたいです」（大槻さん）
最後に、リクルートスタッフィングの事業紹介があり、イベントが終わりました。また、イベントの感想アンケートにお答えいただいた方には、大槻さんの著書を1冊プレゼント。参加者の発言も多く、楽しんだ様子が見られ、充実した内容となりました。
ライター：栃尾 江美（とちお えみ）
リクルートスタッフィングが提供する、ITエンジニアの無期雇用派遣サービス「BUILDICT」。キャリアプランに寄り添って、エンジニア一人ひとりをサポートしています。
https://www.r-staffing.co.jp/sol/contents/buildict/
