億単位の解を生成するのに、rand()では力不足すぎる。というわけで、メルセンヌツイスタ(MT)を導入することにした。 MTをサポートするライブラリはいくつかあるが、初心者は最も使われているものを使え、ということで、boost::randomに含まれているものを使…

というわけで、評価関数をc++で書くことにした。適当に書いて100000回計算させて360ms。xyzzy上での344倍の速度である。ここまで差があると、xyzzy上で走らせるのはもったいない・・・。 しかし、探索アルゴリズムをlispで試したい。そこで、c++でdllを作っ…

２次割り当て問題(QAP)は巡回セールスマン問題と似たようなNP困難な問題である。QAPで検索すれば出てくるけど、大雑把にいうと、物資の移動量(流量)×距離がシステム全体で最小になる配置を探す問題だ。答えが分かっている問題例はQAPLIB Home Pageで得られる…

第1種スターリング数とパスカルの三角形も第2種スターリング数と同様に書ける。この形式ではパスカルの三角形が最も基本的な形になるだろう。 (defun stirling-1st-kind-line (&optional lst) (do ((1-n (- 1 (length lst))) (b lst (cdr b)) (x 0 (car b)) …

第2種スターリング数S(n,k)は、n個の区別できる要素をk個の集合(区別できない箱)にまとめる場合の組合せの数を表す。主な注意点は以下の通り。 n=0のとき、0組に分ける場合が1通りで、それ以外が0通りになる。 n>0のとき、0組に分けられないので、k=0では0通…

第2種スターリング数を求める関数を書いていた。 ;n<20程度にする (defun stirling-2nd-kind (n k) (cond ((= n k) 1) ((zerop k) 0) ((< n k) 0) (t (+ (stirling (1- n) (1- k)) (* k (stirling (1- n) k)))))) これだと，多重再帰となって非常に計算が遅…