DynamicProgramming - kzono/study_haskell GitHub Wiki

ことのおこり

アルゴリズムの初歩はsort法各種だが、その次のステップとして動的計画法というものがあることを知った。ナップサック問題や最短経路問題、スケジュール作成問題など、実用性のあるアルゴリズムらしい。

Haskell にはリスト内包表記があり、離散的な多変数の組合せから評価関数を満たす組合せの集合を簡単に取り出せる。ピタゴラス数が良い例で、実にスッキリと書ける。

「宣言的プログラミング」というらしいが、実現手段ではなく問題(求めたい物、与えられた条件と制約)を記述するだけで答えが出る。 そのことから、Haskellならば動的計画法をスッキリと書けるのではないか、と考えた。

動的計画法は競技プログラミングで頻出するらしい。競技プログラミングではC++が実装言語に選び方ことが多いらしい。恐らく、Haskell と比べるとC++ の方がコード量は多くてその代わり高速且つ省メモリで動くということになると思われる。

できれば実際に同じ問題を複数の言語で実装し、比較してみたい。(Haskell,C++,Rust,Scara,typescript,Elixer,Python)

参考URL

切り出し・詰め込み問題

ナップサック問題

Haskell の文法

Haskell で配列を扱う

Prelude> import Data.Array
Prelude Data.Array> let a = array (1,5)[(i,i^2) | i <-[1..5]]
Prelude Data.Array> print a
array (1,5) [(1,1),(2,4),(3,9),(4,16),(5,25)]
Prelude Data.Array> print $ a ! 3
9

STUArray

ビンパッキング問題

スケジューリング問題

勤務スケジューリング問題

実用性・必要性が高いがゆえに、ライブラリや専用ソフトウェア（solver)が存在する。製品もあるらしい。

python にはこの問題専用のライブラリがあるらしい。(from ortoolpy import shift_scheduling)

ジョブショップ問題

経路問題

巡回セールスマン問題

運搬経路問題

グラフ・ネットワーク問題

最短経路問題