得点:300,558 暫定順位:36位
得点:12,548,350 順位:34位
コンピュータの移動を指示する配列(以降配列と表記)を作成し、下記の処理を時間いっぱい実行
配列の要素数は基本90 × Kとし、配列の要素には「移動させるコンピュータ」、「移動する方向(上下左右 or なにもしない)」の二種類の情報を記録する。
- 配列の要素をランダムで一つ選択し下記の操作のどちらかを実行
- 動かすコンピュータをランダムに変更する
- 動かす方向(上下左右・なにもしない)をランダムに変更する
- 配列の指示に従い、コンピュータを移動する(範囲外に移動してしまう or 別のコンピュータがあり動けない場合は指示を無視する)
- コンピュータの種類ごとに左上から接続できるなら接続していく(別の種類のコンピュータには接続しない)
- 得られる得点を計算し、焼きなまし法(評価関数には得点をそのまま使用)を用いて配列の変更を破棄するか決める
- 1に戻る
上記の方法を使って最大ケースで90,000回程度のループを回せました。
-
◎ 処理の高速化
初期のバージョンではループの回数は30,000回程度でした。 下記のグラフの通り、ループ回数を増やすほど点数が上がるので、可能な限り処理を軽くしました。
-
○ 空きスペースが少ない入力において配列のサイズを増やす
Nが小さく、Kが大きいケース(seed=7のN=24,K=5のケースなど)では配列の指示の大半が実行不可となり移動回数が少なくなっていたので、空きスペースが100以下の場合は移動可能回数の2倍の配列を確保しました。
-
△ 多点スタート
得点のばらつきは少なくなりましたが、ループ回数の減少により得点の平均値が下がってしまいました。
-
× 別の種類のコンピュータをクラスタに接続
うまいこと書けば得点が上がりそうでしたが、自分が試した範囲ではほとんど効果がありませんでした。
-
× 点数が著しく変化した操作を変更しないようにロック
効率よく探索するために試しましたが、点数に変化はありませんでした。(前の操作が後ろの操作に影響を及ぼすから?)
上記の試したこと以外にも色々な方法を試しましたが、単純な処理を高速化して探索回数を増やすことが一番効果がありました・・・