読書: アルゴリズム設計マニュアル 下

タイトル通りアルゴリズム設計マニュアルの日本語版の下巻を読み終えた。

ヒッチハイカーのためのアルゴリズム案内と謳って色々な問題を列挙している。 問題定義と有名なアルゴリズムを紹介している。 また類似問題について検討するべき項目や関連問題へのリンクも書かれてた。

たまに読み返したい。紹介されていた実装などへのリンクは古かったけど載せておく。 公式が丁寧にwebで情報提供してくれているのでそれを当たるのが良い。

あとは実装(AtCoder, LeetCode, Project Euler)して 振り返って説明するのを繰り返さないと力にならない。

資料

19章 アルゴリズム資源 として参考資料や定番の実装について紹介してた。 C,C++,Fortranが多いのは納得だけど、そこにCPANが含まれつつ他の言語は含まれてなかったりと偏りというか不完全さを感じる。Perlに限らず使っている言語のパッケージリポジトリやパッケージインデックスは漁るのは基本ってだけ。 科学計算のライブラリはPython,Julia,C,Fortranが充実しているのでそこで探すのが大事だと思った。

実装

LEDAはAlgorithm Solutions Softwareが提供するライブラリ。質が高いらしい。 CGALは計算幾何の定番ライブラリらしい。 The Boost Graph Libraryは名前の通りBoostのグラフライブラリ。 GOBLINはグラフアルゴリズムのライブラリだけど2009年で更新が止まっていた。著者のサイトからはリンク切れなので改めてググり直さないとたどり着けない。

Netlibは数学ソフトウェアのリポジトリでレビューが少しある。 探索しづらいのでSearch GAMSから探すと少しだけマシ。

データ資源

TSPLIBは巡回セールスマン問題の典型データが手に入るとのこと。 他にはStanford GraphBase,DIMACSが紹介されていた。DIMACSのChallengesはアーカイブ化されてた。