おもしろい。実に面白い
ビンパッキング問題、カッティングストック問題。
定尺長さの材料にほしい部材長さのものを割り付けて、歩留率を最大にする問題。
割り付けられる部材の本数は2.8本など実数ではなく整数値をとる。つまり、継ぐことは禁止。
線形計画問題ではなく整数計画問題となる。
前者は解法がある。
後者は解法があるが、最適解は規模が少しでも大きくなると、
生きている時間内にとても計算できない。
NP困難問題 。よくわからんが、ぱっとした計算が存在しないことが証明されているっぽい。
暫定解は一瞬にして求められるのも問題の特徴。
ま、これで我慢しようか。と。
総当たりが確実に最適解を求められるが、
無理なので、分子限定法なるアルゴリズムがある。
暫定解よりスコアが悪くなると、
その枝を切って組み合わせを少なくして計算量を減らす解法っぽい。
暫定解の精度と速度が求められるっぽい。
ソルバーと呼ばれる数学のすごい集団が作ったソフトの機能説明を見ると、
この分子限定法でやっている。
割と原始的でそれを知ったとき、びっくりした。もう
それに工夫を凝らしていかに良い枝を見つけて他をスキップする方法で実装されているっぽい。
割と数学ではなくいわゆるヒューリスティック。かわいい。
そこに惚れました。