浅葱色の計算用紙

数学(広義)を扱っています。移転後サイトです。

ビンゴ行列の行列式の最大値

この記事は、以下の記事に対する第三者によるさらに深い考察です。

corollary2525.hatenablog.com

私は、ビンゴ行列の行列式の最大値を、遺伝的アルゴリズムで求めてみました。

 

条件は以下のようにしました。

・世代数: 100

・個体数: 500

・次世代の選択方法: 上位20個体(*)はキープ、残り180個体は全世代からキープされた20個体から変異させて作る

・変異方法: 各成分に対し、20%の確率で別の値に置き換える(このとき、置き換える前と同じ値に置き換わることはないようにした)

・初期個体: ランダム

(*): なぜか上位が同じ個体で固まるため、10世代ごとにキープする個体数を1ずつ増やした。それに伴い、変異により作られる個体の数は減少する。

 

また、プログラミング言語にはRubyを使用しました。何回かプログラムを実行した結果、次のような行列が得られました(私のPCでは1回の実行当たり10秒程度かかりました)。

 

Matrix[[14, 28, 43, 59, 0], [0, 29, 42, 58, 75], [15, 30, 0, 54, 72], [12, 27, 45, 0, 73], [13, 0, 44, 60, 74]](行列式は28645603)

Matrix[[13, 0, 41, 58, 75], [14, 30, 44, 0, 72], [12, 28, 0, 60, 74], [0, 29, 45, 59, 73], [15, 27, 43, 57, 0]](行列式は287684196)

Matrix[[0, 29, 43, 59, 72], [13, 27, 42, 0, 73], [12, 28, 0, 60, 74], [15, 30, 45, 57, 0], [14, 0, 44, 58, 75]](行列式は287780688)

Matrix[[14, 28, 43, 60, 0], [12, 0, 42, 59, 73], [15, 30, 0, 58, 74], [0, 29, 45, 57, 72], [13, 27, 44, 0, 75]](行列式は287905806)

Matrix[[15, 0, 43, 58, 75], [13, 29, 45, 0, 74], [12, 30, 0, 59, 73], [0, 28, 44, 60, 72], [14, 27, 42, 57, 0]](行列式は289713264)

 

結果をよく見ると、各列の数字が「0と各列で可能な数が大きい方から4個」の並べ替え(1列目は0,12,13,14,15, 2列目は0,27,28,29,30, etc.)となっていることが多いことに気が付きます。そこで、このような行列を全探索することにしました。

しかし、このままでは120^5=24,883,200,000通りあって、全探索するには多すぎます。せめて1億通り以下には減らしたいものです。

そこで、改めて行列をよく見ると、0は各行、各列に2度現れないように位置していることがわかります。この場合、0の位置を最初に決めてから残りの数字の位置を決めることで、探索する行列は24*24^5=191,102,976個(∵3列目の0は必ず3行目)にまで減らせます。まだ少し多い気がしますが、これで全探索してしまいましょう。

 

...といってもこれが結構長いので、最初の20分ほど探索して得られた結果を示します。

 

Matrix[[0, 30, 42, 60, 72], [12, 0, 45, 57, 75], [15, 27, 0, 59, 73], [13, 29, 43, 0, 74], [14, 28, 44, 58, 0]](行列式は291970008)