はじめに
少しずつですが、アルゴリズムの学習を始めていこうと考えています。
今回しっかりと学ぼうと思った理由ですが、エンジニアとして習得しておかなければならないスキルになりつつあると感じたからです。
海外のIT企業の面接ではアルゴリズムの理解力を問うことが当たり前になっています。特に、Amazon, Facebook, AppleやMicrosoftなどの有名なIT企業では必ず技術的なインタビュー（面接）があります。
日本の中途採用でもリクルートを始めとした企業では、中途採用で入社試験としてアルゴリズムを題材にしたプログラミングで足切りを行っているところも増えてきています。
また、最近流行りのAIやDeepLearningなどの分野では、アルゴリズムの理解が必須になりますので、知っておいて得こそあれ損はないと思います。
何か新しいことを学ぶなら、枝葉からではなく全体像から見ていくのが良いとされていますので、まず入門的な記事のまとめを書きたいと思います。
今回の教材
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～
本記事では「気軽にアルゴリズムに触れられるような」6つのアルゴリズム例が紹介されています。
| 問題 | アルゴリズム |
|---|---|
| 年齢当てゲーム | 二分探索法 |
| マッチング問題 | マッチング法 |
| 虫食算パズル | 深さ優先探索法 (DFS) |
| 迷路 | 幅優先探索法 (BFS) |
| 音声認識パターンマッチ問題 | 動的計画法 (DP) |
| ディープラーニング | 勾配降下法 |
年齢当てゲーム
これは年齢でなくても別にいいのですが、例えば20から35の数字の中から1つの選んでもらって、4 回だけ Yes / No で答えられる質問をすると、正解にたどり着けるというものです。
これを2分探索方法というそうです。対象をどんどん半分にしていき解を求めるというものです。
上記の例で言うと、20〜35なので16個の要素を四回半分にする（16 -> 8 -> 4 -> 2 -> 1）と答えが得られることがわかります。応用情報技術者試験でも頻出のテーマとのことです。
マッチング問題
記事では「恋活・婚活サービス」を題材にした例が紹介されています。詳しくないですが、日本で有名なマッチングサイトOmiaiなどがこれに当たるでしょう。（アルゴリズムは違うかもしれませんが）
この例で面白かったのは、マッチングのアルゴリズムでは偏りが出ないように全体を「最適化」することが求めるという部分です。記事の例で言うと、お互いの相性を数値化し（例えば共通の趣味や趣向を持った人通しは相性がいいので高いポイント、年齢が離れすぎる低いポイントなどで)、どの組み合わせだと全体の利益が最大なのか？を求めるという部分です。一部のイケメンと美女に人気が殺到してしまわないようにするために、全体の利益を優先する。つまり、ブサメンでもそれなりの美女に出あえる可能性がある！？ということになるのでしょう。
このアルゴリズムは現代社会のあらゆるところで使用されているようで、非常に興味深いです。
虫食い算パズル
虫食いパズルと言うものを見たことがあるでしょうか？私はあの手のパズルが苦手で正直敬遠していました。しかし、プログラムを使うとものすごいスピードで総当り的に検証を繰り返せば、解を求めることができるとのことで、人が人力で解く場合もそうやってるのか？それとも他にやり方があるのか？どうなのでしょうか。
ここで使うアルゴリズムは深さ優先探索法 (DFS: Depth-first search) といい、
– とりあえず仮定して突き進む」ことを、行き詰るまで繰り返す
– 行き詰ったら一歩戻って、次の選択肢を試す
を繰り返します。基本的には力任せの全探索アルゴリズムです。
迷路
続いては迷路の最短経路を求める、幅優先探索法 (Breadth-first search)です。記事の具体例が非常に分かりやすくて理解が早かったです。こちらは深さ優先探索 (DFS) 似ていて、力任せの全探索アルゴリズムです。ただし「最小手順を見つけたい」というシーンで活躍するでしょう。ルービックキューブやカーナビの最短経路問題でもこのアルゴリズムが採用される場合があるとのことで、これも身近なところで使われているのが面白いと思います。
音声認識パターンマッチング問題
音楽が好きな私はこれを使っているアプリをよく使います。ShazamやSoundHoundで、レストランやバーなどで流れてきた曲の情報が欲しい！という時に使い倒しています。
これの仕組みはなんとなく想像できていて、スマホに聞かせた曲を波形（ビット信号？）に変換し、サーバー内の情報と照らし合わせて類似するものを選択するという具合です。ここの「類似するものを調べる」という部分に動的計画法 (DP) というアルゴリズムが使用されています。他にも、写真の人物やものを認識して、それとデータベースを比較するというユースケースが考えられますね。指名手配犯なんかは、監視カメラの顔認証システムが発達するともう逃げられませんね。これも実社会にすでに利用されているのでとても興味深いです。
ディープラーニング
こちらは最近話題なのでよく耳にしますが、勾配降下法というアルゴリズムが使われるそうです。こちらはまだ良く理解できていないので、ここでは省略します。また学習後に書いていきます。
まとめ
今回は基本となる6つのアルゴリズムを学んだのでまとめました。数式もほとんどなく、分かりやすかったです。
これからは一つ一つ掘り下げて見ていこうと考えています。
ただしちゃんと理解するためには数学の知識は必須だなと感じました。数学の学習も並行してやっていく必要がありそうです。やることがありすぎて大変ですね。それではこの辺で。