補足
各コードに対するスコアはseed = 0 の結果です。
目的
なるべく少ないターン数で、10台のロボットを有効活用して全てのマスを塗る（訪れる）ことです。
まずはロボット0のみを動かす
ロボット0 のみを動かして貪欲的にDFS (Eulerツアー) で全ての未到達マスへ到達できるようにします。 Eulerツアーで探索する際はU,D,L,R (上、下、右、左) の順に次の移動先のマスを見るようにします。
ボタンの割り当ては以下です。
button 0: robot 0 が U
button 1: robot 0 が D
button 2: robot 0 が L
button 3: robot 0 が Rスコアは 907 です。
Euler ツアーを使う理由
現在地点のマスからの探索ができない (進める候補がすべて壁だったりすでに訪問済み) 場合に来た道を1マスずつ戻る必要があります。戻っている最中の分岐点で探索できるマス (まだ壁がなく未訪問のマス) があればそこへ進むようにします。
ロボット0以外にも動かしてみる
ロボット0のEulerツアーはそのままに、他のロボットも動かすようにします。 ロボット0と同じようにEulerツアーで探索しようとすると計算量が大きくなってしまうので探索はせずに、かつ解の多様性を増やすためにロボット0のEulerツアーで得られた経路を基に移動先を決定する変換器を導入します。
変換器
変換器は全部で8種類用意します。
各ロボットに付与される変換器は、ロボット番号 j の j % 8 で決まります。
例えば基準方向(ロボット0の移動方位)が R のとき、あるロボットは D に進み、別のロボットは R に進み、さらに別のロボットは L に進む、ということができます。
これにより、全ロボットに同じボタン列を流しても実際には各ロボットが異なる方向へ移動できます。
なお、各ロボットの移動先が壁や盤面外なら移動せずその場に留まります。
変換0 (j%8 == 0) : 恒等変換
U -> U
D -> D
L -> L
R -> R
変換1 (j%8 == 1) : 時計回り90度回転
U -> R
R -> D
D -> L
L -> U
変換2 (j%8 == 2) : 180度回転
U -> D
D -> U
L -> R
R -> L
変換3 (j%8 == 3) : 反時計回り90度回転
U -> L
L -> D
D -> R
R -> U
変換4 (j%8 == 4) : 上下反転
U -> D
D -> U
L -> L
R -> R
変換5 (j%8 == 5) : 左右反転
U -> U
D -> D
L -> R
R -> L
変換6 (j%8 == 6) : 主対角線反転
U -> L
L -> U
D -> R
R -> D
変換7 (j%8 == 7) : 副対角線反転
U -> R
R -> U
D -> L
L -> D
表にすると以下です。
変換器 | U D L R
--------+------------
0 | U D L R
1 | R L U D
2 | D U R L
3 | L R D U
4 | D U L R
5 | U D R L
6 | L R U D
7 | R L D Uスコアは2122です。
基準経路をロボット0固定ではなく最良の経路を作れるロボットに変更する、焼きなまし法の導入
今までロボット0を使ってEulerツアーで探索していましたがこれを全てのロボットでEulerツアーをし、 その中で最も良い経路 (ターン数が最も少ない) を作れたロボットの経路を採用する方針に変更しました。 (これを焼きなまし法の初期解とします)
焼きなまし法はまずは簡易的 (試行回数300回) に導入してみます。
近傍操作は下記の１種類です。
１つのロボットをランダムに選んでそのロボットの変換器を別のタイプにする評価関数については T:操作回数, R:未到達マス数とすると
(全マス到達できた場合) = 1e6 - T
(全マス到達できなかった場合) = N^2 - R評価関数の設計背景
問題文の公式得点は以下です。
R = 0 の場合: 3N^2 - T
R > 0 の場合: N^2 - R
ここで N = 30 なので、
N^2 = 900 3N^2 = 2700
公式得点は以下になります。
全塗りできた場合: 2700 - T
塗り残しがある場合: 900 - R
例えば最大手数 T = 1800 で全塗りした場合、
公式得点 = 2700 - 1800 = 900
1マス未塗りの場合、
公式得点 = 900 - 1 = 899
つまり公式得点上は、
ギリギリ全塗り: 900 1マス未塗り: 899
となり差が1しかありません。
この差は焼きなましの内部評価としては小さいです。 そこで全塗り解を未完了解より圧倒的に高く評価するために 1e6 - T を使います。
例えば、最大手数 T = 1800 で全塗りした場合でも、
内部評価値 = 1,000,000 - 1800 = 998,200
1マス未塗りの場合、未完了時の評価値は塗れたマス数なので
内部評価値 = 899
その差は
998,200 - 899 = 997,301
となり、全塗り解と未完了解の間に明確な差を作れます。
スコアは2362です。
解法
10台のうち、任意の1台のロボットの初期位置を基準として DFS 経路（Euler ツアー）を作ります。
Euler ツアーを使う理由は、DFS の「訪問順」だけではロボットが実際に歩ける移動列にならないためです。 あるマスから進める候補がすべて壁だったり、すでに DFS 上で訪問済みだったりした場合、来た道を1マスずつ戻る必要があります。そして戻った途中の分岐点で、まだ壁が なく未訪問のマスがあれば、そこへ進みます。
つまり、基準経路には「未訪問マスへ進む移動」だけでなく、「探索を終えて親のマスへ戻る移動」も含めます。これにより、基準ロボットが実際に歩ける U/D/L/R の移
動列を作れます。
今回の移動方法は、上下左右隣のマスへの移動 U, D, L, R です。
DFS では、現在のマスから次に進む方向の優先順位を決めます。例えば U -> D -> R -> L なら、まず上を検討し、上が壁または訪問済みなら下、次に右、最後に左を検討
します。
この方向優先順は U, D, L, R の並べ替えなので、合計 4! = 24 通りあります。実装ではこの24通りをすべて前計算します。
変換器
10台のロボットを同時に動かすため、ロボットごとに方向変換器を持たせます。
基準経路は1本だけですが、各ロボットはその基準方向を自分の変換器で変換して解釈します。
例えば基準方向が R のとき、あるロボットは D に進み、別のロボットは R に進み、さらに別のロボットは L に進む、ということができます。
これにより、全ロボットに同じボタン列を流しても、実際には各ロボットが異なる方向へ移動できます。
変換器の種類は下記の8種です。
変換0: 恒等変換
U -> U
D -> D
L -> L
R -> R
変換1: 時計回り90度回転
U -> R
R -> D
D -> L
L -> U
変換2: 180度回転
U -> D
D -> U
L -> R
R -> L
変換3: 反時計回り90度回転
U -> L
L -> D
D -> R
R -> U
変換4: 上下反転
U -> D
D -> U
L -> L
R -> R
変換5: 左右反転
U -> U
D -> D
L -> R
R -> L
変換6: 主対角線反転
U -> L
L -> U
D -> R
R -> D
変換7: 副対角線反転
U -> R
R -> U
D -> L
L -> D
表にすると以下です。
変換器 | U D L R
--------+------------
0 | U D L R
1 | R L U D
2 | D U R L
3 | L R D U
4 | D U L R
5 | U D R L
6 | L R U D
7 | R L D U前計算
全10台それぞれの初期位置と、24通りの方向優先順を組み合わせて、合計240本の基準経路候補を前計算します。
10台の初期位置 × 24方向順 = 240本初期解
paths[r][oid] は、ロボット r の初期位置から、方向優先順 oid で DFS/Euler ツアーした移動列です。
初期解の構築では、初期 変換器 = j % 8 を固定したまま、この240本を総当たりします。
各候補経路を共通ボタン列として全ロボットに流し、全塗りできる中で最短のものを 最良解(bestRoot / bestOrd / bestPress) として保存します。
ロボットは実行時は全台同時操作ですが、経路生成時は1台の初期位置だけを基準にします。 その基準経路を U/D/L/R の共通ボタン列として使い、各ロボットは自分の変換器に従って実際の移動方向を決めます。
初期状態の変換器の付与は j % 8 で固定しています。 つまり robot0 から robot9 には以下のように割り当てます。
robot0 -> 変換器 0 robot1 -> 変換器 1 robot2 -> 変換器 2 robot3 -> 変換器 3 robot4 -> 変換器 4 robot5 -> 変換器 5 robot6 -> 変換器 6 robot7 -> 変換器 7 robot8 -> 変換器 0 robot9 -> 変換器 1
この初期 変換器 を固定したまま、まず240本の基準経路候補を総当たりして初期解を作ります。
焼きなまし
その後の焼きなましでは、近傍操作によって root、ord、各ロボットの 変換器 を変更します。
近傍操作は以下の4種類です。
近傍0: 1台の変換器を変更する。 例: robot3 の 変換器 を 2 から 5 に変更する。
近傍1: 2台の変換器を交換する。 例: robot1 と robot7 の 変換器 を交換する。
近傍2: DFS の方向優先順を変更する。 例: R -> U -> D -> L から D -> L -> R -> U に変更する。
近傍3: 基準経路の始点を変更する。 例: robot3 の初期位置を基準にした経路から、robot8 の初期位置を基準にした経路へ変更する。
評価関数
実装では、焼きなまし用の内部評価関数として以下を使っています。
double eval(size_t T, int cov) const {
if (cov == prob.N * prob.N) return 1e6 - (double)T;
return cov;
}ここで、
T: 操作回数
cov: 塗れたマス数
です。
全マス塗れなかった場合は cov、つまり塗れたマス数をそのまま評価値にします。
これは、未塗りマス数を R とすると、
cov = N^2 - R
なので、問題文の未完了時スコア N^2 - R と同じです。
一方、全マス塗れた場合は、公式得点 3N^2 - T ではなく、内部評価値として 1e6 - T を使います。
問題文の公式得点は以下です。
R = 0 の場合: 3N^2 - T
R > 0 の場合: N^2 - R
ここで N = 30 なので、
N^2 = 900 3N^2 = 2700
公式得点は以下になります。
全塗りできた場合: 2700 - T
塗り残しがある場合: 900 - R
例えば最大手数 T = 1800 で全塗りした場合、
公式得点 = 2700 - 1800 = 900
1マス未塗りの場合、
公式得点 = 900 - 1 = 899
つまり公式得点上は、
ギリギリ全塗り: 900 1マス未塗り: 899
となり、差が1しかありません。
この差は、焼きなましの内部評価としては小さいです。 そこで、全塗り解を未完了解より圧倒的に高く評価するために 1e6 - T を使います。
例えば、最大手数 T = 1800 で全塗りした場合でも、
内部評価値 = 1,000,000 - 1800 = 998,200
1マス未塗りの場合、未完了時の評価値は塗れたマス数なので、
内部評価値 = 899
差は、
998,200 - 899 = 997,301
となり、全塗り解と未完了解の間に明確な差を作れます。
ただし、これは提出スコアそのものではありません。 あくまで焼きなまし中に解を比較するための内部評価値です。
この評価関数により、探索の優先順位は以下になります。
- まず全マスを塗れる解を優先する
- 全マスを塗れる解同士では、操作回数 T が短いものを優先する
- 全マスを塗れない解同士では、より多くのマスを塗れたものを優先する
近傍操作をさらに増やしてみる、焼きなましを回数ではなく時間で動かすようにする
焼きなましを固定 500 iteration から、約 1950ms の時間制限ループへ変更しました。
近傍操作
下記の3種類の近傍操作を新たに追加しました
2つのロボットをランダムに選んでそれらのロボットの変換器を交換する
Eulerツアーでの次の探索先の方位優先度順をランダムに選んでその優先度順に探索してみる
DFS root の変更スコア
Score = 2499
再構築焼きなましを導入
さらなる最良解を求めるために再構築焼きなましを導入しました。 再構築焼きなましの近傍操作は以下の2種類です
・複数ロボットの 変換器 をまとめてランダム再割当
・複数ロボットの 変換器 をブロック内でシャッフルスコア
Score = 2495 (seed = 0では僅かに悪化しましたが再構築焼きなましにより黄パフォを達成できました)
