『アルゴリズム図鑑』の元となったのは、Appleが2016年末に発表した「ベストApp10選」に選ばれたアプリ「アルゴリズム図鑑」です。
勉強しようと思っても、文字や少数の図解だけでは仕組み・概念を理解しづらいのがアルゴリズム。アプリではイラストで表現することでその課題を解決し、大変な好評を得ました。本書は紙幅を活かして一覧での見やすさを高め、26種類のアルゴリズムを徹底的にイラストで表現しました。
今回は本書から、データ構造の「リスト」、グラフを探索するアルゴリズムの「幅優先探索」、データを暗号化するアルゴリズムの「公開鍵暗号方式」、データを似たもの同士に分類するクラスタリングアルゴリズムの「k-means法」を紹介します。
リスト――データ構造
アルゴリズムの仕組みを理解するのであれば、そこで扱うデータの構造について知っておく必要があります。データはメモリに蓄えられており、その際にデータの順番や位置関係などを規定したものがデータ構造です。
データ構造の一つが「リスト」。データを一直線に並べた構造をしていて、データの追加や削除がしやすいメリットがある反面、アクセスには時間がかかるというデメリットもあります。
これはリストの概念図で、三つのデータが格納されています。各データを繋いでいるのがポインタで、メモリ上の位置を指し示します。
リストではポインタが位置関係を規定するため、メモリ上の連続した領域に格納される必要がありません。データは一般的に離れた領域に格納されています。
格納場所が異なるため、各データにはポインタを順に辿らないとアクセスできません（順次アクセス、またはシーケンシャルアクセス）。RedにアクセスしたいときはBlueからアクセスし、Yellowを経る必要があります。
データを追加するときは、追加する前後のデータのポインタを指し替えるだけなので簡単です。BlueとYellowの間にGreenを追加したいときは……
BlueのポインタをGreenに、GreenのポインタをYellowに向けます。これでデータが追加されたことになります。もちろんGreenのデータはメモリ上のどこにあっても構いません。
データの削除もポインタの指し替えで行います。Yellowを削除したいなら……
GreenのポインタをRedに指し替えましょう。Yellowはどこからもアクセスできないので、消す必要もなく、その領域は別のデータに上書きされて再利用されます。
ここで紹介したリストは最も基本的なもので、拡張されたものもあります。リストの最後尾のデータであるRedはポインタを持っていませんでしたが、Redから先頭のBlueへポインタを指せば「環状リスト（循環リスト）」ができ上がります。常に一定個の最新データを保持したいときに有用です。
また、各データに双方向のポインタを持たせて、「双方向リスト」を作ることもできます。リストを前からでも後ろからでも辿れるので便利ですが、ポインタの数が増えることでデータ格納のための領域が多くなる欠点もあります。
幅優先探索――グラフ探索
では、ここからアルゴリズムを紹介していきましょう。最初に紹介するのはグラフを探索するアルゴリズムの「幅優先探索」です。
そもそもコンピューターサイエンスでいうグラフとは、複数個の頂点（ノード）が辺で結ばれたものをいいます。人間関係（ソーシャルグラフ）、路線図、コンピューターネットワークなど、様々なものをグラフで表現できます。
これらのグラフを探索するためのアルゴリズムの一つである幅優先探索は、全貌のわからないグラフにおいて、始点から辺を辿りながら頂点を探索し、指定された頂点（ゴール）に辿り着けば目的達成です。端的には、頂点を探索する際、始点に近い頂点から優先的に探索していくアルゴリズムです。
まず、始点を定めましょう。今回はAです。ゴールとしてGを設定しますが、Gがどこにあるかは最初の時点ではわかりません。
Aから辿れる頂点B、C、Dが次に進む頂点の候補です。
候補の中から頂点を一つ選びます。選択の基準は、最も早く候補に追加されたものです（同じタイミングのときはどれでも構いません）。
今回はB、C、Dが同じタイミングで候補となったのでBを選択します。
Bに移動すると、Aが探索済みとなります。
Bから辿れるEとFを候補に追加しましょう。これで候補がC、D、E、Fとなりました。
C、D、E、Fのうち、最も早く候補になったのはCとDです。今回も左側のCを選択します。
Bから、選択したCに移動します。Bが探索済みとなります。
Cから辿れるHが新たに候補に加わります。現在の候補はD、E、F、Hです。
このように、ゴールに辿り着くか、すべての頂点を探索し終えるまで探索を繰り返します。
今回の例での選択順はA、B、C、D、E、F、H、I、J、K、そしてGとなりました。
幅優先探索では文字どおり幅広く探索を行っていく特徴があります。当たり前のことですが、始点の近くにゴールがあるほうが探索が早く終了します。
ちなみに、ここまで例として用いてきた連結して閉路のないグラフは木と呼ばれています。また、始点と終点が同じ頂点である（閉路がある）グラフも同様に探索することができます。
公開鍵暗号方式――セキュリティのアルゴリズム
次に紹介するのはセキュリティのアルゴリズム、その中でも最も有名で重要な「公開鍵暗号方式」です。
インターネットを使ってデータをやり取りする際、安全に利用するためにセキュリティを確保しなければなりません。データを暗号化する方式は数々考案されてきては脆弱性が暴かれてきました。公開鍵暗号方式は、これまでの暗号方式が抱えていたとりわけ大きな課題、鍵配送問題を解決したのです。
たとえデータを複雑に暗号化しても、復号する（平文に戻す）にはそれを解く鍵が必要です。その鍵は暗号化した人の手から復号したい人の手に安全に送り届けなければなりません。いったいどうすれば安全に送れるのか？ 鍵を暗号化したら、さらにそれを復合するための鍵を送る必要があり……さて。
公開鍵暗号方式はどのような仕組みで課題を解決し、安全を確保しているのでしょうか（ちなみに、公開鍵暗号方式にもいくつか種類があり、強力なRSA暗号がよく使われています）。
では、公開鍵暗号方式を利用したデータのやり取りの全体像を見ていきます。AさんがBさんにインターネット経由でデータabcを送ろうとします（Xさんがその様子を見ています）。
まず、受け手のBさんが公開鍵P（public key）と秘密鍵S（secret key）を作成します。もちろんこれらの作業を行うのはコンピューターです。
Bさんは公開鍵をAさんに送信します。のちほど説明するように、公開鍵は第三者に知られても問題ありません。
AさんはBさんから受け取った公開鍵でデータを暗号化します。
Aさんは暗号化されたデータ（暗号文）をBさんに送信し、Bさんは秘密鍵を使って復号します。これでBさんはデータabcを取得することができました。
公開鍵と暗号文はインターネットで送信されるため、悪意のある第三者Xさんに盗み見されるかもしれません。しかし、公開鍵では暗号文を復号できないので、Xさんは元のデータabcを取得できないのです。
公開鍵暗号方式には不特定多数間でのやり取りがしやすいというメリットがあります。具体的に見てみます。
公開鍵はその名のとおり、人に知られても問題ありません。一方で、秘密鍵は誰にも知られないように管理する必要があります。
さて、複数人がBさんにデータを送信したいとしましょう。
データを送信する人は、Bさんが公開している公開鍵を取得します。
そして、送信したいデータを暗号化します。
その後、暗号文をBさんに送ります。
Bさんは暗号文を自分の秘密鍵を復号します。これでBさんは元のデータを取得できました。このように、データを送信する相手ごとに鍵を用意しなくていいのがこの方式のいいところです。データの受け手だけが秘密鍵を持つので、安全性も高いのです。
公開鍵の信頼性は重要です。しかし実は、Xさんが悪巧みできる余地も理屈から言えば残されているのです。それを知るために、Bさんが公開鍵PBと秘密鍵SBを使ってデータのやり取りをする場面を見てみましょう。
ここで、データを盗み見しようとするXさんも公開鍵Pxと秘密鍵Sxを作成します。
Bさんが公開鍵PBをAさんに送るとき、事件が起こります。
なんと、Xさんが公開鍵PBを自分の公開鍵Pxにすり替えてしまいました。
当然、Aさんに届くのはXさんの公開鍵Px。公開鍵自体は誰が作成したものかわからないので、Aさんは公開鍵のすり替えに気づけません。
そのため、Aさんは公開鍵Pxでデータを暗号化してしまいます。
そして、AさんがBさんに暗号文を送ろうとしたとき、Xさんが暗号文を受け取ります。
何が起きるかは明白でしょう。Xさんは秘密鍵Sxで暗号文を復号できてしまいます！ Xさんはデータを盗み見ることに成功しました。
次に、XさんはBさんの公開鍵PBでデータを暗号化します。
Xさんはその暗号文をBさんに渡します。この暗号文はBさんの公開鍵PBで作成したものなので、Bさんは自分の秘密鍵PBで復号できます。Aさん同様、データを盗み見されたことに気づけません。
このように、公開鍵をすり替えてデータを盗み見る攻撃手法を「man-in-the-middle攻撃」と呼びます。
この攻撃は防げないのでしょうか？ 解決策はあります。公開鍵の作成者を証明するための「デジタル証明書」というアルゴリズムを利用するのです。その仕組みについては、ぜひ本書で。
k-means法――クラスタリング
最後に紹介するのは、クラスタリングのアルゴリズム「k-means法」です。
クラスタリングとは、多数のデータを似たもの同士のグループに分類する操作のことで、それぞれのグループをクラスターと呼びます。データ間の距離を定義できれば、距離の遠近でそれぞれのデータがどれくらい似ているかを判断でき、クラスタリングすることができます。
k-means法は基本的・代表的なもので、クラスターが事前に与える数（k個）になるようにクラスタリングするアルゴリズムです。
まず、クラスタリングを行いたいデータを用意しましょう。次に、クラスター数を決めます。今回は3とします。このイラストでは、データを点で表し、データ間の距離は2点間の直線距離を用います。
クラスターの中心点として、3点をランダムに設置します。
各データについて、3つの中心点のうち最も近い点を計算します。
各データを決定したクラスターに分類します。これで三つのクラスターができました。
各クラスターに属するデータの重心を計算し、クラスターの中心点をそこに移動させます。
最も近いクラスターの中心点を再計算し、各データをクラスターに再分類しました。
各データのクラスターへの分類と、中心点の重心への移動を中心点が収束するまで（動かなくなるまで）繰り返します。
これは3回目の繰り返しが終わったあとの状態です。
4回目の繰り返しが終わったところです。これ以上やっても中心点は移動しないので、クラスタリング完了です。
k-measn法では操作を繰り返すと中心点が必ずどこかに収束することが証明されています。設定するクラスター数が適切でないと、有意な結果が得られないこともあるので気をつけましょう。
ビジュアライズされたアルゴリズム
紹介した三つのアルゴリズムを既に知っていた方、あるいは全然知らなかった方も、このように仕組みをイラストでしっかり表現すれば、一気に視覚的にイメージしやすくなったのではないでしょうか。
『アルゴリズム図鑑』にはほかのアルゴリズムも掲載していますので、気になる方はチェックしてみてください。
