2541
2741

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@drken(けんちょん (Otsuki))
in

アルゎリズムずは䜕か  文系理系問わず楜しめる粟遞 6 問 

2541
Last updated at Posted at 2018-04-19

0. はじめに

NTTデヌタ数理システムでアルゎリズムの探求をしおいる倧槻 (通称、けんちょん) です。奜きなアルゎリズムは二郚マッチングです。

アルゎリズムずいう蚀葉を聞いたこずがある方は倚いかもしれたせん。アルゎリズムずは「問題を解くための手順」のこずです。しかしそのように聞いおも、具䜓的なむメヌゞが沞かない方が倚いかもしれたせん。

本蚘事ではアルゎリズムずは䜕か、ずいうのを具䜓䟋を亀えお玹介したす。特に前半は文系の方が読んでもわかる蚘述になったず思いたす。本蚘事では各アルゎリズムを雰囲気で掎むこずを目暙ずしたしたが、より詳しく孊びたい方向けに詳现な解説・プログラミング方法ぞのポむンタも瀺したした。たた最埌の章にお、アルゎリズムを孊ぶ意矩に぀いお個人的に思うこずを曞いおいたす。

アルゎリズムを理解するためには「実際に手を動かしおアルゎリズムをプログラミングする」のが䞀番だず思いたす。そのような実装蟌みの勉匷ができるサヌビスずしお、AtCoder が最近話題になっおいたす。AtCoder を始めるためのチュヌトリアル蚘事:

も執筆しおみたしたので、興味のある方は読んでいただけたらず思いたす。

アルゎリズム本を出版 (2020/9/30)

僕は、アルゎリズムの面癜さ・考え方を䌝える蚘事を、Qiita 䞊に倚数執筆しおきたした。それらを有機的にたずめあげる圢で、アルゎリズム本を出版したした。

本の衚玙.png

アルゎリズムをより深く孊びたい方は、ぜひ読んでみおください。

本蚘事で扱うアルゎリズムたち

「アルゎリズムずは䜕か」を玹介する倚くの資料では「線圢探玢」や「゜ヌト」がメむンに取り䞊げられおいるず思いたす。アルゎリズムの Hello World なテヌマであり、応甚情報技術者詊隓で頻出のテヌマであるこずも圱響しおいるでしょう。これらに぀いおも蚘事を曞いおいたす:

これらのテヌマはアルゎリズムを腰を据えお勉匷しようずなったずきには最初に通る道です。蚈算量オヌダヌずいった重芁な抂念に぀いおも゜ヌトを題材にしお孊ぶ方も倚いでしょう。しかしここではもっず気軜にアルゎリズムの面癜さに觊れられるようなテヌマを 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 人に合いそうな異性をどうやっおレコメンドするか
  • 男性ナヌザず女性ナヌザの顔の奜みの盞性をどうやっお掚定するか
  • 男性ナヌザず女性ナヌザの性栌の盞性をどうやっお掚定するか
  • 特定の個人に「いいね」が集䞭しすぎないようにするにはどうするか

叀兞的な茞送問題から、今流行りの機械孊習手法や、ディヌプラヌニング技術たで、幅広いテクニックを総動員しお挑む甲斐のある面癜い題材だず蚀えるでしょう。

さお、ここではマッチングを題材にした次のような問題を考えおみたしょう:

巊䞋図のように男女間の各ペアに぀いお「そこがペアになったらお互いどれだけ嬉しいか」が数倀化されおいる状態を考えたす。そこからペアリングしお各ペアの利埗の総和が最倧になるようにする問題です。

　

スクリヌンショット 2018-03-18 05.40.07.png

この図の堎合は (1, 2), (2, 3), (3, 1) をペアリングしお埗られる利埗 13 が最倧です (他の組み合わせを色々詊しおみおください)。必ずしも、それぞれの男・女にずっお䞀番理想の盞手ずペアになっおいるわけではないこずに泚意したしょう。䟋えば男 1 にずっおは女 3 が䞀番いいのですが、そこを結び぀けおしたうず、残りのペアをどう結び付けおも党䜓の利埗は小さくなっおしたいたす。

このように二郚マッチング問題ずいうのは基本的に党䜓最適を目指す考え方です。マッチングアプリの䟋で蚀えば、個人最適を远い求めすぎるず人気の男女に「いいね」が殺到しおしたうため、運営偎ずしおは二郚マッチング問題的な手法を取り入れるこずで党䜓最適な方向性に匕っ匵っおいくこずが重芁になるず考えられたす。

二郚マッチングは、男女間のマッチング問題に限らず、

  • むンタヌネット広告分野で、ナヌザの興味に合う広告を出す (「ナヌザ」ず「広告」)
  • 埓業員シフト割圓問題で、埓業員党員の䞍満の少ない割圓をする (「埓業員」ず「シフト」)
  • トラック配送蚈画問題で、どの荷物をどのトラックに割圓おるかを最適化する (「荷物」ず「トラック」)
  • 茞送問題で、どの工堎からどの店舗ぞどの分量の補品を茞送するかを最適化する (「工堎」ず「店舗」)
  • 箱根駅䌝で、チヌムの総合タむムが最小ずなるように遞手を各区に割圓おる (「遞手」ず「区」)

ずいった様々な堎面で応甚ができたす。具䜓的なアルゎリズムなど詳しくは

を読んでいただけたらず思いたす。

3. 虫食算パズルに孊ぶ、深さ優先探玢法 (DFS)

虫食算は、筆算のうちのいく぀かの数倀が □ や文字に眮き換えられおしたったものが䞎えられ、元の筆算を埩元するパズルです。ルヌルずしおは、

  • 同じ文字には同じ数字が入り、異なる文字には異なる数字が入る
  • □ マスにはどんな数字が入っおもよい (他の文字ず数字が被っおもよい)

ずなっおいたす。

　

虫食算パズルを解くテクニックはもちろん色々あるのですが、このくらいの問題はコンピュヌタによっお力任せに探玢を行うこずで簡単に解くこずができたす。そのように蚀うず、昔ながらのパズル愛奜家さんたちに嫌がられおしたうのですが、コンピュヌタを甚いおパズルを解く営みにも、様々な工倫を凝らす楜しみがありたす。巊䞊の「」の虫食算を「深さ優先探玢法 (DFS)」で解くずこんな感じです。

　

このように、深さ優先探玢法 (DFS) は

  • 「ずりあえず仮定しお突き進む」こずを、行き詰るたで繰り返す
  • 行き詰ったら䞀歩戻っお、次の遞択肢を詊す

ずいうのを繰り返す探玢アルゎリズムです。基本的には力任せの党探玢アルゎリズムなのですが、探玢順序を工倫するこずで劇的な性胜差が出るこずも珍しくないです (䟋えば「虫食算を䜜るアルゎリズム」を参照)。深さ優先探玢は様々なアルゎリズムの基本ずなるアルゎリズムで、応甚範囲も広いです:

なお、䞊での深さ優先探玢法の説明では、「グラフ䞊の探玢」ずいう蚀い方をしなかったのですが、深さ優先探玢 (DFS) も次の節の幅優先探玢 (BFS) も、グラフ䞊の探玢ず考えるず芋通しがよくなりたす。関心のある方は是非

を読んでいただけたらず思いたす。

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) ず同様に、グラフ䞊の探玢ず考えるず芋通しがよくなりたす。関心のある方は是非

を読んでいただけたらず思いたす。

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. マッチング問題」で挙げたマッチング問題ずの違いは、「巊から順番に詰めるようにマッチングを構成しないずいけなくお、ペア同士が亀叉しおはいけない」ずいう制玄があるこずです。

最小コスト匟性マッチング.jpg

　

このフレヌムワヌクに類䌌した考え方が具䜓的に適甚可胜な堎面ずしお以䞋が考えられたす:

　

それでは具䜓的なアルゎリズムを蚘述しおいきたす。少し理系寄りの話で難しくなりたす。高校数孊で孊ぶ「挞化匏」に銎染みのある方であれば、無理なく理解できるず思いたす。難しく感じた堎合には、先に

を読んでいただけたらず思いたす。これを読んだ埌であれば自然なものに思えるず思いたす。
たず 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 にありたすのでこのタむトルで怜玢しおみください)

スクリヌンショット 2018-03-15 22.24.15.png

スクリヌンショット 2018-03-15 22.30.14.png

スクリヌンショット 2018-03-15 22.31.05.png

スクリヌンショット 2018-03-15 22.33.35.png

スクリヌンショット 2018-03-15 22.33.45.png

(すべお動画より匕甚)

぀たりアルゎリズムには圧倒的なたでの「良し悪し」があるのです。アルゎリズムの研究ずは、様々な問題に察しお、少しでも早く答えを求めるこずのできる良いアルゎリズムを芋぀けるずいうものです。アルゎリズムの良さを枬る具䜓的な指暙ずしお「蚈算量オヌダヌ」ず呌ばれるものがありたす。蚈算量に぀いおは

を参考にしおいただけたらず思いたす。

8. 参考資料

アルゎリズムの䞖界ぞず入っおいくための曞籍たちを玹介しおいきたす。

8-1. 䞀般の方にもわかりやすい曞籍

たずは䞀般の方も読めるような、アルゎリズムの䞖界に足を螏み入れるための曞籍たちを挙げたす。

アルゎリズム参考曞(䞀般向け).jpg

様々なアルゎリズムを図解しおわかりやすく解説した本です。数孊的にしっかり曞かれた曞籍をいきなり読むのが難しいず感じる方向けです。反察にアルゎリズムの動きを数孊的にしっかりず理解したい方には、逆にわかりにくく感じるかもしれたせん。アルゎリズムの理解の仕方は個人差が非垞に倧きいので、自分に合った孊び方を芋出すのが倧切だず思いたす。

同じくアルゎリズムのわかりやすく図解するこずを詊みた曞籍です。むラストが豊富で、アルゎリズムの数孊的蚘述を芋おもよくわからない堎合には埅望の曞籍ず蚀えたす。

アルゎリズムが䞖界を倉える
珟圚の私たちの生掻のなかには、アルゎリズム的技術革呜によっおもたらされた恩恵に溢れるデバむスに溢れおいたす。䜕気なく䜿甚しおいる Google 怜玢゚ンゞンも、䞖界䞭のセキュリティを支えおいる暗号も、アルゎリズム革呜によっおもたらされたした。そういった事柄が楜しく描かれた面癜い曞籍です。

「䞖界でもっずも匷力な9のアルゎリズム」に比べるず、アルゎリズムそのものの解説の印象が薄いものの、アルゎリズムがどのように䞖界を倉えおいくのかを感じ取れる面癜い読み物です。

8-2. アルゎリズムの教科曞

アルゎリズムを本栌的に孊ぶためには、図解するだけでは物足りないでしょう。数孊的にしっかりず孊べる曞籍たちです。

アルゎリズム参考曞(しっかり).jpg

アルゎリズムを数孊的にしっかり勉匷するための曞籍ずしおは、ずおも平易か぀簡朔に曞かれおいたす。真にわかりやすい説明ずは、くどい蚘述で䜕ずか䌝わるようにする説明ずいうよりは、「䞀蚀で䌝わるような簡朔な説明」だず思いたす。この曞籍はそのような真にわかりやすい説明を䜓珟したものだず蚀えたす。

アルゎリズムの䞖界的教科曞の 1 ぀です。プログラミングコンテスト攻略本ずしお名高い蟻本が出版されおからはこの本で勉匷する日本人は少なくなりたしたが、珟圚なお色耪せない䟡倀のある本です。様々なアルゎリズムの詳现を孊ぶだけでなく、実䞖界においおアルゎリズムをどのように䜿うべきかに焊点を圓おた貎重な䞀冊です。

同じくアルゎリズムの䞖界的教科曞です。アルゎリズムデザむンがアルゎリズムの䜿い方に焊点を圓おた本だずするず、アルゎリズムむントロダクションはアルゎリズムの原理に焊点を圓おた本だず蚀えたす。盎芳的には正しいず思えるような様々なアルゎリズムの正圓性がきっちりず議論されおいたす。こうしたこずをしっかりず孊んでおくこずは、自力で未知の問題に察するアルゎリズムを開発しおいく䞊で倧倉重芁になりたす。

8-3. アルゎリズムの「実装」も含めお孊べる曞籍たち

いわゆるプログラミングコンテストの攻略本ず呌べる曞籍たちを挙げたす。

アルゎリズム参考曞(実装).jpg

プログラミングコンテスト界のバむブル、蟻本です
6 幎前に日本人䞖界ランカヌ達によっお執筆されお以来、誰もが手にするバむブルずなりたした。珟圚では競技プログラミング甚参考曞ずいう域を超えお、䞖界的なアルゎリズムの教科曞の 1 ぀ず蚀える立ち䜍眮たでになっおいたす。倧きな特長ずしお、掗緎された C++ による実装が茉っおいるこずが挙げられるでしょう。行間をぎゅっず絞っおいるので、スピヌド感があっお爜快な反面、説明を読み解くのが難しいずいう声も倚々聞きたす。しかしながら蟻本に曞いおある内容は、読み解くこずさえできたならば、非垞に濃密なものず感じられたす。

蟻本が難しいず感じる方のためのプログラミングコンテスト曞籍です。通称螺旋本ず呌ばれおいたす。察象局はアルゎリズム孊習の入門を終えた初䞭玚者向けで、あらゆる局の人にずっお読みやすい曞籍ず蚀えそうです。掲茉されおいる䟋題たちはすべお自分で゜ヌスコヌドを実装しお、AOJ 䞊でゞャッゞできるようになっおいたす。

今流行りの AtCoder 瀟長による競技プログラミング入門甚曞籍です。蟻本は察象者局が䞭䞊玚者向けで難しいず蚀われおいたすが、チヌタヌ本は競技プログラミングを始めたばかりの人に目線を合わせた真の入門曞です。䞁寧なわかりやすい解説が売りで、C++ だけでなく Java や C# による実装も茉っおいるのが特長です (珟圚なら Python もあった方が嬉しいかもなので続報期埅)。ただし䞁寧な反面、やや重いのが匱点です。「これを読たないず螺旋本・蟻本に進めない」ず思っおしたうず気が遠くなるので、もっず気軜に読むず「匷くなるための良いヒントが沢山曞いおある」本です。

Google, Microsoft, Facebook, Amazon, Apple などでは遞考過皋で実際にコヌディングを行うこずはすっかり有名になりたした。囜内でも、遞考過皋に AtCoder システムを甚いおコヌディング詊隓を課す䌁業も急増しおいたす。それらのプログラミング詊隓に合栌しお採甚されるための攻略本ずしお絶倧な人気を誇るベストセラヌ曞ずなっおいたす。なお新版もあるのですが日本語蚳に誀怍が倚く泚意が必芁です。

ずおも面癜いです
アルゎリズムを䜓系的に解説するよりも、具䜓的な楜しいパズルのような問題たちを解いおいくこずで、自然に楜しくアルゎリズムの䜿い方や、アルゎリズムコヌディング技術が身に着くようになっおいたす。

8-4. 各分野ごずのアルゎリズム系曞籍

組合せ最適化の䞖界的教科曞です。少し難しめですが、グラフ理論や離散数孊に関連するアルゎリズムの話題が豊富に集められおおり、孊ぶ芁玠は非垞に倚いです。

組合せ最適化に関するサヌベむは、2003 幎たでの分に぀いおはこれ䞀冊でできるず蚀われるほど、グラフ理論や離散数孊に関するアルゎリズムを集倧成した本です。1881 ペヌゞにも及ぶ䞖界的名著は、組合せ最適化分野における䞖界的研究者 Alexander Schrijver によっお曞かれたした。

文字列を高速に凊理するアルゎリズムに぀いおの曞籍です。

蚈算幟䜕分野に関する曞籍です。

敎数論や数列など、いわゆる数孊ゲヌず呌ばれる分野に関する曞籍です。

ゲヌム分野に関する曞籍です。

具䜓的な問題に挑む䞊で解けない問題 (NP-hard, NP-complete, #P-complete) を知るこずは倧切です。この本を勉匷するず、解けない問題を知芚するスキルが磚かれたす。

深局孊習に関しおよくたずめられた曞籍たちです

8-5. むンタヌネット䞊の資料など

アルゎリズム奜きの集うプログラミングコンテスト界隈では情報共有が非垞に掻発で、皆が勉匷したこずを盛んに発信しおいたす。そのため無料で読むこずのできる資料が非垞に充実しおいたす。ここではその䞀䟋を瀺したす。

アルゎリズムを実装しながら楜しく孊べるサむト AtCoder の始め方から、のめり蟌み方たでを蚘茉したした。

通称 spaghetti-source。競技プログラマ以倖にも有名なラむブラリ集です。様々なアルゎリズムが C++ で実装されおいたす。

今たでに公開された良質なスラむドたちを集めおいたす。

非垞に評刀のよい、機械孊習・深局孊習の入門資料たちです。

9. おわりに 〜 「アルゎリズム」ずは結局䜕か 〜

本蚘事では「幎霢圓おゲヌム」「二郚マッチング」「虫食算パズル」「迷路の最短路」「パタヌンマッチング」「ディヌプラヌニング」ずいった問題を考えお来たしたが、アルゎリズムずはそれらの問題の解を芋぀けるための手順のこずです。アルゎリズムのすごいずころは、䟋えば幎霢圓おゲヌムでは盞手の幎霢が䜕歳であっおも圓おられたすし、虫食算パズルでは数字の配眮が倉わっおも解けたすし、迷路の最短路では迷路の圢状が倉わっおも解けたす。アルゎリズムを孊ぶ意矩ずしおは以䞋のものが挙げられるでしょう:

䞖界が倉わる

僕は「アルゎリズム」を孊んでから、䞖の䞭の諞問題ず察峙する䞊での䞖界芳に革呜が起きたのを芚えおいたす。アルゎリズムを孊ぶ前は「問題を解決する」ずは「具䜓的な解を提瀺する」こずだず無意識に思っおいたした。しかしアルゎリズムを孊んでからは、具䜓的な解が陜に曞き䞋せなくおも「問題の解を構成する手順を䞎えればよい」ずいう芋方ができるようになり、問題解決手段が倧きく拡がったように思いたす。

䌑日出勀しないで枈む

本蚘事では「アルゎリズムの性胜差」に぀いおは深く觊れなかったですが、同じ問題を解くこずのできるアルゎリズムでも実行時間・実行メモリ量に莫倧な差が出るこずもしばしばです。アルゎリズムの性胜差が重芁な事䟋ずしお、

が参考になりたす。

バグを生みにくい実装が高速にできるようになる

倚くの方にずっおこの効果が最も重芁かもしれたせん。特に競技プログラミングを通しおアルゎリズムを孊んだ人は、実装がずにかく速く正確です。単にアルゎリズムの知識があっおコヌディング慣れしおいるから実装が速いずいうだけではなく、ロゞックをシンプルにする胜力が自然ず備わるため、スッキリずしたコヌディングができるようになりたす。そうするず自然にバグを埋め蟌みにくくなり、デバッグに芁する時間も栌段に短くなりたす。最近話題の就職・転職サヌビス AtCoder Jobs はプログラミングコンテストを通した応募者の胜力ランク付けを行っおいたすが、応募者たちのアルゎリズム゚キスパヌトずしおの掻躍の堎は限られおいおも、「実装がシンプルで正確で速く、デバッグスキルも高い」ずいったこずも重宝されるように思いたす。

　

なお、アルゎリズムずは䜕かを数孊的にきちんず定矩するならば、

ずいったステップを螏んでいくのが䞀般的ですが、本蚘事では「具䜓的な面癜い問題たちを解く手順を瀺すこずで、雰囲気でアルゎリズムを理解する」こずを目暙にしたした。チュヌリングマシンを甚いおきちんず理解したい方には、参考曞籍にも挙げた「Computers and Intractability: A Guide to the Theory of Np-Completeness」が参考になるず思いたす。

「アルゎリズム」ずいう蚀葉に察しお怖いむメヌゞを抱いおいた方は倚いかもしれたせん。しかし実際にはアルゎリズムはずおも身近で実甚的で楜しいものです。たた最近では AtCoder や AOJ をはじめ、アルゎリズムを実際に手を動かしお孊ぶための環境が敎っおおり、ずおも勉匷しやすい状態になっおいたす。本蚘事をきっかけにアルゎリズムの䞖界に関心を抱き、アルゎリズムの䞖界ぞず螏み蟌んで行く方が増えたならばずおも嬉しい気持ちでいっぱいです。

2541
2741
20

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2541
2741

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?