qiita.com/drken/items/f909b79ee03e679c7142

アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ #機械学習 - Qiita 2540 いいねしたユーザー一覧へ移動 2744 X（Twitter）でシェアする Facebookでシェアする はてなブックマークに追加する more_horiz 記事を削除する close 一度削除した記事は復旧できません。 この記事の編集中の下書きも削除されます。 削除してよろしいですか？ キャンセル 削除する delete info この記事は最終更新日から5年以上が経過しています。 @ drken ( けんちょん (Otsuki) ) in 株式会社NTTデータ数理システム アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズム 機械学習 DeepLearning 競技プログラミング 新人プログラマ応援 2540 最終更新日 2021年01月24日 投稿日 2018年04月19日 0. はじめに NTTデータ数理システム でアルゴリズムの探求をしている大槻 (通称、けんちょん) です。好きなアルゴリズムは 二部マッチング です。 アルゴリズム という言葉を聞いたことがある方は多いかもしれません。アルゴリズムとは「問題を解くための手順」のことです。しかしそのように聞いても、具体的なイメージが沸かない方が多いかもしれません。 本記事ではアルゴリズムとは何か、というのを具体例を交えて紹介します。特に前半は文系の方が読んでもわかる記述になったと思います。本記事では各アルゴリズムを雰囲気で掴むことを目標としましたが、より詳しく学びたい方向けに詳細な解説・プログラミング方法へのポインタも示しました。また 最後の章 にて、アルゴリズムを学ぶ意義について個人的に思うことを書いています。 アルゴリズムを理解するためには「実際に手を動かしてアルゴリズムをプログラミングする」のが一番だと思います。そのような実装込みの勉強ができるサービスとして、 AtCoder が最近話題になっています。AtCoder を始めるためのチュートリアル記事: AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ も執筆してみましたので、興味のある方は読んでいただけたらと思います。 アルゴリズム本を出版！ (2020/9/30) 僕は、アルゴリズムの面白さ・考え方を伝える記事を、Qiita 上に多数執筆してきました。それらを有機的にまとめあげる形で、アルゴリズム本を出版しました。 amazon ページ アルゴリズムをより深く学びたい方は、ぜひ読んでみてください。 本記事で扱うアルゴリズムたち 「アルゴリズムとは何か」を紹介する多くの資料では「 線形探索 」や「 ソート 」がメインに取り上げられていると思います。アルゴリズムの Hello World なテーマであり、応用情報技術者試験で頻出のテーマであることも影響しているでしょう。これらについても記事を書いています: 「線形探索」を極める！ 〜 for 文で色んなことができることを知る 〜 「ソート」を極める！ 〜 なぜソートを学ぶのか 〜 これらのテーマはアルゴリズムを腰を据えて勉強しようとなったときには最初に通る道です。 計算量オーダー といった重要な概念についてもソートを題材にして学ぶ方も多いでしょう。しかしここではもっと気軽にアルゴリズムの面白さに触れられるようなテーマを 6 個取り上げます。「気軽に面白いテーマ」と言っても、掲載しているアルゴリズムたちは本格的かつ正統派なものになっています。 問題 アルゴリズム 年齢当てゲーム 二分探索法 / 二分法 応用情報でもお馴染みです マッチング問題 マッチング法 面白いです 虫食算パズル 深さ優先探索法 (DFS) すべての基礎です 迷路 幅優先探索法 (BFS) 同じく重要な基礎です 音声認識パターンマッチ問題 動的計画法 (DP) DP はとても用途が広いです ディープラーニング 勾配降下法 超流行中です 1. アルゴリズムとは アルゴリズムと聞くと、私たちの生活には関係ないような難しい概念と感じられるかもしれませんが、実際はとても身近なものです。 ちょっとした 年齢当てゲーム を考えてみましょう！ 1-1. 年齢当てゲームに学ぶ、二分探索法 A さんの年齢を当てようとしています。 A さんが、20 歳以上 36 歳未満だというのはわかっているとしましょう。あなたは A さんに 4 回だけ Yes / No で答えられる質問をすることができます。A さんの年齢を当てられるでしょうか？？？ それができるのです！！！！！ まず、現在わかっている年齢幅は 20 歳以上 36 歳未満 と 16 歳分もの幅がありますが、「28 歳以上ですか？」と聞いてみます。 Yes なら: 28 歳以上 36 歳未満だとわかり、選択肢が一気に 8 歳分まで絞れます No なら: 20 歳以上 28 歳未満だとわかり、やはり選択肢が一気に 8 歳分まで絞れます どっちの答えだったとしても、 選択肢が半減 するのです！！！ これを繰り返すと、A さんが 31 歳だったとして、以下のようにストーリーが進行するでしょう: 人物 セリフ 備考 あなた 「A さんは 28 歳以上ですか？」 A さん Yes あなた 「A さんは 32 歳以上ですか？」 28 以上 36 未満に絞れているので、その真ん中で切ります A さん No あなた 「A さんは 30 歳以上ですか？」 28 以上 32 未満に絞れている (28, 29, 30, 31 のどれか) ので、その真ん中で A さん Yes あなた 「A さんは 31 歳以上ですか？」 30 以上 32 未満に絞れている (30 か 31 か) ので、その真ん中で A さん Yes あなた 「A さんは 31 歳ですね！」 決まりました！ A さん 正解です 今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには 二分探索法 という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場します。例えばキャンプにおいてテントを組み立てるときの 組立手順書 が示すものもアルゴリズムの一種です。他にもコンビニの仕事でお客さんにお釣りを渡す場面において渡す紙幣やコインの枚数を最小にするためには、 まず 10000 円札を渡せるだけ渡す 残りを 5000 円札を渡せるだけ渡す 残りを 1000 円札を渡せるだけ渡す 残りを 500 円玉を渡せるだけ渡す 残りを 100 円玉を渡せるだけ渡す 残りを 50 円玉を渡せるだけ渡す 残りを 10 円玉を渡せるだけ渡す 残りを 5 円玉を渡せるだけ渡す 残りを 1 円玉を渡せるだけ渡す とすればよいですが、このような手順も立派なアルゴリズムであるといえます。 このようにアルゴリズムとはあくまで問題を解くための方法・手順のことであって、その手順を実現する手段については問いません。原理的には人手で実行できるものです。 しかしながら現実世界の大きな問題を解決する場合には、人手では実行速度や正確さにおいて限界があります。そのため通常、アルゴリズムはコンピュータプログラムとして実装して計算実行することになります。 1-3. アルゴリズムのすごいところ アルゴリズムのすごいところは、ある決まった問題に対して 想定内であれば、どんな場合に対しても 同じやり方で 答えを導けることです。つまり 1 つの プログラム であらゆる場合を処理できるということです (想定内であればです)。今の世の中は既にそういうシステムが溢れています。カーナビを使えば現在地がどこであっても目的地までの経路を示してくれますし、銀行口座は預金額と引出額がいくらであっても正しくお金を引き出すことができます。こういったシステムはアルゴリズムによって支えられています。 アルゴリズムのもう 1 つのすごいところとして、コンピュータプログラムとして実装することにより、人手では到底調べ切れない問題を解決できることが挙げられます。現実世界で直面する多くの問題は「 答えは原理的にはある 」しかし「 それが人手ではわからない 」というものです。例えば、練馬駅を 2018 年 3 月 18 日 11:34 に出発して、最速で神保町駅にたどり着く方法というのは、原理的にはあるはずです。しかしそれが人手ではパッとはわかりません。一方でこれは、コンピュータなら一瞬で計算できますし、そういうアプリもあります。 このような「原理的にはあるはずの答え」を見つけ出すのがアルゴリズムです。 2. マッチング問題に学ぶ、マッチング法 年齢当てゲームに続いて次の問題を考えてみたいと思います。 マッチングアプリ と呼ばれる恋活・婚活サービスが流行している昨今、 マッチング という言葉を聞いたことのある方は非常に多いと思います。マッチングアプリはユーザ側から見ても面白いサービスですが、運営側から見ても考えることの多い楽しい題材です。世界的にも " Online Dating " というキーワードで盛んに研究されているテーマです。 ユーザ 1 人 1 人に合いそうな異性をどうやって レコメンド するか？ 男性ユーザと女性ユーザの顔の好みの相性をどうやって推定するか？ 男性ユーザと女性ユーザの性格の相性をどうやって推定するか？ 特定の個人に「いいね」が集中しすぎないようにするにはどうするか？ 古典的な 輸送問題 から、今流行りの 機械学習手法 や、 ディープラーニング技術 まで、幅広いテクニックを総動員して挑む甲斐のある面白い題材だと言えるでしょう。 さて、ここではマッチングを題材にした次のような問題を考えてみましょう: 左下図のように男女間の各ペアについて「そこがペアになったらお互いどれだけ嬉しいか」が数値化されている状態を考えます。そこからペアリングして 各ペアの利得の総和が最大 になるようにする問題です。 この図の場合は (1, 2), (2, 3), (3, 1) をペアリングして得られる利得 13 が最大です (他の組み合わせを色々試してみてください)。必ずしも、それぞれの男・女にとって一番理想の相手とペアになっているわけではないことに注意しましょう。例えば男 1 にとっては女 3 が一番いいのですが、そこを結びつけてしまうと、残りのペアをどう結び付けても全体の利得は小さくなってしまいます。 このように二部マッチング問題というのは基本的に 全体最適 を目指す考え方です。マッチングアプリの例で言えば、個人最適を追い求めすぎると人気の男女に「いいね」が殺到してしまうため、運営側としては二部マッチング問題的な手法を取り入れることで全体最適な方向性に引っ張っていくことが重要になると考えられます。 二部マッチングは、男女間のマッチング問題に限らず、 インターネット広告分野 で、ユーザの興味に合う広告を出す (「 ユーザ 」と「 広告 」) 従業員シフト割当問題 で、従業員全員の不満の少ない割当をする (「 従業員 」と「 シフト 」) トラック配送計画問題 で、どの荷物をどのトラックに割当てるかを最適化する (「 荷物 」と「 トラック 」) 輸送問題 で、どの工場からどの店舗へどの分量の製品を輸送するかを最適化する (「 工場 」と「 店舗 」) 箱根駅伝 で、チームの総合タイムが最小となるように選手を各区に割当てる (「 選手 」と「 区 」) といった様々な場面で応用ができます。具体的なアルゴリズムなど詳しくは 実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬ を読んでいただけたらと思います。 3. 虫食算パズルに学ぶ、深さ優先探索法 (DFS) 虫食算は、筆算のうちのいくつかの数値が □ や文字に置き換えられてしまったものが与えられ、元の筆算を復元するパズルです。ルールとしては、 同じ文字には同じ数字が入り、異なる文字には異なる数字が入る □ マスにはどんな数字が入ってもよい (他の文字と数字が被ってもよい) となっています。 虫食算パズルを解くテクニックはもちろん色々あるのですが、このくらいの問題はコンピュータによって力任せに探索を行うことで簡単に解くことができます。そのように言うと、昔ながらのパズル愛好家さんたちに嫌がられてしまうのですが、コンピュータを用いてパズルを解く営みにも、様々な工夫を凝らす楽しみがあります。左上の「２１１」の虫食算を「 深さ優先探索法 (DFS) 」で解くとこんな感じです。 このように、深さ優先探索法 (DFS) は 「とりあえず仮定して突き進む」ことを、行き詰るまで繰り返す 行き詰ったら 一歩戻って 、次の選択肢を試す というのを繰り返す探索アルゴリズムです。基本的には力任せの全探索アルゴリズムなのですが、 探索順序 を工夫することで劇的な性能差が出ることも珍しくないです (例えば「 虫食算を作るアルゴリズム 」を参照)。深さ優先探索は様々なアルゴリズムの基本となるアルゴリズムで、応用範囲も広いです: 数独 も解ける (数独は、人間的には探索ではなく理詰めで解くものではありますが...) フリーセル も解ける Ponanza などの コンピュータ将棋ソフト でも使われているような ゲーム木探索 makefile の仕組みは トポロジカルソート で根本的には DFS メモしながら DFS すれば 動的計画法 (DP) にもなる ネットワークフローアルゴリズム のサブルーチンでもある なお、上での深さ優先探索法の説明では、「グラフ上の探索」という言い方をしなかったのですが、深さ優先探索 (DFS) も次の節の幅優先探索 (BFS) も、グラフ上の探索と考えると見通しがよくなります。関心のある方は是非 DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 を読んでいただけたらと思います。 4. 迷路に学ぶ、幅優先探索法 (BFS) 以下のような迷路で、スタート (S) からゴール (G) まで行きたいです。ただし茶色マスには入れません。いくつか考えられる行き方のうち、最短のものはどのように求められるでしょうか。 まず、スタートから 1 手で行ける場所に「１」と書きます。 続いて、「１」のマスから 1 手で行ける場所に「２」と書きます。これはスタートから 2 手で行ける場所でもあります。 続いて、「２」のマスから 1 手で行ける場所に「３」と書いて... これを繰り返していくと、G のマスは「１６」となりました。 ここまで来たら、あとは数字をさかのぼるようにして最短経路を復元できます: このように幅優先探索 (BFS) も、深さ優先探索 (DFS) と同様に基本的には力任せの全探索アルゴリズムですが、「なにかを達成するための 最小手順 を知りたい」という場面で活躍することが多いです。以下のような応用があります: ルービックキューブ の最小手数「神の数字」 必ず 20 手以内で揃えられることが最近完全解析された！( God's Number is 20 参照) 解析のベースは BFS を改良した IDA$^{*}$ だと思われます トポロジカルソート DFS の章でも応用例として挙げた makefile の仕組み DFS でもできますが、BFS でもできます 最短経路問題 カーナビ にも代表されるような最短経路問題は Dijkstra 法 が定番ですが、特殊な場合には BFS の方がより効果的に使えます そして幅優先探索 (BFS) も深さ優先探索 (DFS) と同様に、グラフ上の探索と考えると見通しがよくなります。関心のある方は是非 BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 を読んでいただけたらと思います。 5. 音声認識パターンマッチ問題に学ぶ、動的計画法 (DP) 動的計画法はとにかく実用的なアルゴリズムです！ スケジューリング問題 、 最短経路問題 、 ナップサック問題 から、 パターンマッチ問題 まで、実世界の極めて多くの現場で活躍するアルゴリズムです。DP の使われ方は多彩過ぎて紹介しきれないので、ここでは典型的応用例の 1 つである パターンマッチング問題 、特に 最小コスト弾性マッチング問題 を取り挙げます。 最小コスト弾性マッチング問題とは、下図のように 2 つの系列 $A = (a_0, a_1, \dots, a_{m-1})$, $B = (b_0, b_1, \dots, b_{n-1})$ が与えられて、それらがどの程度「似ているか」を測る問題です。類似度の測り方としては、ペア $(a_i, b_j)$ をマッチさせたときのコストは $c(i, j)$ で与えられて、左から順番に最適なマッチングを構成していきます。マッチングを最適化したときのコストの総和の最小値を「類似度」とします。 注意点として「 2. マッチング問題 」で挙げたマッチング問題との違いは、「左から順番に詰めるようにマッチングを構成しないといけなくて、ペア同士が交叉してはいけない」という制約があることです。 このフレームワークに類似した考え方が具体的に適用可能な場面として以下が考えられます: diff コマンド いわゆる編集距離 スペルチェッカー 直したい単語が、どの単語に近いかを推測 バイオインフォマティクス 今熱い応用例です、2 つの DNA の間の類似度を測ります 空間認識・画像認識 近年はディープラーニングが盛んだが DP マッチングも有効なケースも多いです (「 画像認識 」参照) 音声認識 未知の音声波形が何の単語を表しているかを推測 「 音声認識・画像認識に用いられる弾性マッチングのアルゴリズムって一体 」を参照 それでは具体的なアルゴリズムを記述していきます。少し理系寄りの話で難しくなります。高校数学で学ぶ「 漸化式 」に馴染みのある方であれば、無理なく理解できると思います。難しく感じた場合には、先に 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ を読んでいただけたらと思います。これを読んだ後であれば自然なものに思えると思います。 まず DP テーブルの定義を以下のようにします: ${\rm dp}[i][j]$ := $A$ のうち最初の $i$ 個までと、$B$ のうち最初の $j$ 個までについての弾性マッチングの最小コスト そして、${\rm dp}[i][j]$ を算出する漸化式を立てることを考えると、以下のようになります: ＜DP漸化式＞ $${\rm dp}[i][j] = \min({\rm dp}[i-1][j-1], {\rm dp}[i][j-1], {\rm dp}[i-1][j]) + c(i-1, j-1)$$ ＜DP初期条件＞ $${\rm dp}[0][0] = 0$$ ＜求める類似度＞ $${\rm dp}[m][n]$$ あとはこれに従って素直に実装すればよいです。実装など含めて DP を詳細に学びたい方は この記事 を読んでいただけたらと思います。 6. ディープラーニングに学ぶ、勾配降下法 今はどこへ行っても ディープラーニング の話題で溢れ返っています。圧倒的な AI ブームに沸き立つ中、「とりあえず AI という用語を入れた提案書は通りやすい」といった話も頻繁に耳にします。 「ディープラーニング」という言葉をよく耳にするが具体的なことがよくわからない方向けに、実際のビジネス現場で登場しやすい「画像処理」「自然言語処理」への応用を念頭においた入門スライド資料を執筆してみました。比較的最新に近い話題も盛り込んでいます。 ディープラーニング入門 ～ 画像処理・自然言語処理について ～ ディープラーニングが魔法のようなことをしているイメージのある方も多いかもしれませんが、多くの場合、手法自体はごく単純な「 勾配降下法 」です。勾配降下法はざっくりと言ってしまえば「関数の最小値を求める一般的なテク」とでも言うべきもので考え方は単純です。関数 $L(w)$ を最小化したいときに 初期値 $w_0$ を用意する 毎ステップ $t$ ごとに $w_{t+1} = w_{t} - \epsilon \frac{\partial L}{\partial w}$ に従って $w$ を更新していく とするだけです。 $$w_{t+1} = w_{t} - \epsilon \frac{\partial L}{\partial w}$$ の意味は単純明快で、$L$ が小さくなる方向に $w$ を動かす、というイメージです。どのくらい動かすのかを $\epsilon$ という値で調節していて 学習率 と呼びます。学習率のチューニングは学習の成否を大きく分ける重要な要素になります。 さて、勾配降下法において関数 $L$ を様々なものにすることで様々な学習を行うことができます。一般的な考え方としてはディープラーニングに限らず、関数 $L$ はなんらかの形式で「予測結果と正解とのズレの大きさ」を表すもので 損失関数 と呼ばれます。「複雑なニューラルネットワークモデルによって表された損失関数が小さくなるように勾配降下法を適用する」というのが、昨今耳にするディープラーニングの中身であることが多いです。ディープラーニングにおいて損失関数 $L$ を具体的にどのように設計するかについては、 上のスライド を見ていただけたらと思います。 7. アルゴリズムの何が難しいか: 計算量について ここまで様々な問題を見て来ましたが、多くの諸問題に対しては、 「 無尽蔵の計算実行時間さえかければ確実に答えが求まる 」ようなアルゴリズムを、とりあえず導くことは簡単！！！ です。「全探索」と呼ばれる種類の様々な探索技術を身につけると大抵の問題に対しては全探索アルゴリズムがパッと作れるようになります。応用情報技術者試験のアルゴリズムの設問でも全探索からの話題が極めて多いのは、やはり全探索がすべての基礎になるからです。難しいのは、単純な全探索から改良して 「 現実的な制限時間内に答えが求まる 」ようなアルゴリズムを、導くことは難しいことが多い！！！ です。将棋の必勝法を求めるアルゴリズム (「 ゲームを解く！！ 〜 将棋の必勝法を求めるアルゴリズム 〜 」を参照) も、計算にものすごく時間のかかる単純なアルゴリズムでよいなら、情報系のプログラミングに慣れた人なら比較的簡単に実装できるでしょう。ここで「ものすごく」というのは言葉の迫力が全然足りなくて、宇宙が誕生してから今までの時間を 5000 兆回繰り返しても終わらないような時間です。 似た例の動画: 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ (非常に話題になった動画です。科学未来館などでも展示されていました。YouTube にあ