読書: アルゴリズム実装練習

プライベートで色々あったものの、合間をぬってアルゴリズムの勉強をちょいちょいやっていた。 プライベートでの色々は感情的にも状況的にも思考的にも大きく揺り動かされることが多かったのでいずれ時間を作って振り返りたい。 そんな言い訳もあるけど、ようやくアルゴリズム設計マニュアル (S.S.スキーナ)での気になっていたアルゴリズムを実装し終えた。

関連して計算理論の基礎、オンラインアルゴリズムとストリームアルゴリズム、純粋関数型データ構造も読んた。

やったこと

以下のアルゴリズムをGoで実装した。実装はここに残した。

• データ構造
  • キュー
  • デック
  • RB木
  • Union-Find
• 文字列検索
  • Aho-Corasick
  • DP(Levenshtein)
  • Rabin-Karp
• 最小スパニング木
  • Prim
  • Kruskal
• 最短経路問題
  • A*
  • Dijkstra
  • Viterbi
• 素数
  • Eratostheres
• マッチング
  • 2部マッチング
  • Gale-Shapley
• 最大流
  • Edmonds-Karp
• 連結点(articulation)
  • DFS,lowlink

振り返り

綺麗にとかまったく考えず、とにかく動かすのを目指した。(テストもままならない) 一回書いてみると慣れて心理的な抵抗が軽減される。また問題を考えるのが楽になった。 これは頻繁に利用する基本的なアイディアが身についてきたということだと思う。あと必要に応じて書けるという自信がついたのも大きい。 ここからは、テストと同じで類題を解いたり自分で整理して体系化したり丁寧に仕上げてみるとか効果が大きい気がする。

書いている時に感じたのだが、特にグラフアルゴリズムでは中間的に利用するデータ構造をまとめてると楽になる。 これは問題の入力に対応するグラフと別にする。すごい当たり前のことなんだけどアルゴリズムで利用する中間データに専用の型を与える。 そしてGoではサブルーチンをレシーバ関数にする。

アルゴリズム設計マニュアルで学んだ基本的なアプローチを列挙する。

• 貪欲法
• ランダム化で最悪時間計算量を改善する
• データ構造で基本操作を高速化
• 逐次処理(解をデータ構造に埋め込む)
• 分割統治(問題を分割する)
• 動的プログラミング(DP)
• ヒューリスティックス
  • ランダムサンプリング
  • 局所探索
  • シミュレーテッドアニーリング
• 組み合わせ探索: バックトラック
  • 対称性
  • 先読み
• 正しさを証明する
  • 反例
    • 小さく考える
    • 網羅する
    • 極端なケース
    • 同点ケース
  • 数学的帰納法

概要は押さえられたので「アルゴリズム設計マニュアル 上/下」を中心に置いた勉強はこれで止める。 いままでの基礎練習と読書を踏まえ、理論方面の勉強について3つの方向を広げるつもりでいる。

• 計算困難問題の取り扱い(ヒューリスティックス・近似アルゴリズム)
• ViterbiからHMM(隠れマルコフモデル)や機械学習
• 代数の復習

とりあえず計算困難問題に対するアルゴリズム理論を読み始めた。 また近似アルゴリズムを買ったので続いて読む。純粋関数型データ構造も合間を見て読み返す。代数は楽しいけど後回しにする。(正直、まぁ基礎は組んでるし必要に応じて調べ直せばまぁ対処できるよねって感覚がある)

実装方面ではAtCoderの過去問も再開する。またElixirで何かライブラリを作ってみようかと考えている。 これはElixirはアルゴリズム系ライブラリが貧弱なので隙間が多いということと、業務で使っているため。

以上。