NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「動的計画法が好きな人」と呼ばれています。今回は動的計画法を用いて得られた最適解を復元するための汎用的な方法について紹介します。 0. はじめに 動的計画法を用いて効率的に解くことのできる最適化問題は数多くあります。パッと思いつくだけでも ナップサック問題 迷路などの最短路問題 区間スケジューリング問題 音声認識パターンマッチング問題 レーベンシュタイン距離 発電計画問題 分かち書き 隠れマルコフモデル ... などなど、多種多様な分野の問題を動的計画法によって効率よく解くことができます。このように、分野横断的な活用をできることが、動的計画法をはじめとした数理工学的手法の特長であり醍醐味であると常々感じています。今回は動的計画法によって得ら