どうも、tomboです。初めてブログを書きます。
この記事では、焼きなまし初心者が、AtCoderのアルゴやヒューリスティックの問題に焼きなましを適用して解いてみた、ということを書きます。厳密なことはよく分からないので、焼きなましの知識が全くない初心者に、直感的に伝えるみたいなことが目標になっています。それではどうぞ（？）
焼きなましとは
焼きなましとは、ある状態Xに少しの変化を加えてX'（近傍）にして、評価値を計算し、評価値と温度からその近傍を採用するかしないかを決める、ということを繰り返して、大域最適解に近づいていくという感じのアルゴリズムです。これは、山登りと呼ばれるアルゴリズムの拡張です。山登りは、近傍を取りながら、改善したときだけ採用します。それに対して、焼きなましは悪化してもある程度の確率で採用します。採用する確率は、改善した幅（負の場合も含めて）が大きいほど高くなり、スコアの変化が0以上のとき100%採用します。（スコアを最大化したいとき）
ここから評価関数を山にたとえますが、高いとは評価値がいいことを意味するとします。
まず、悪い解を採用するメリットですが、山登りが評価関数の今いる山の頂上で止まる（局所最適解）としたら、あえてそこから脱出することで、大域最適解に辿り着きやすいということです。そうして評価関数上を移動しながら、たまたま大域最適解を含む山に来たとき、遷移確率関数から、山の頂上が高いほど、その山から脱出しにくくなり、少しずつ正解の山の頂上に登っていきます。遷移確率関数は、有名なものがあるのであとで紹介します。その関数には便利な性質があり、自分も初めて見たときはすごいなーと思いました（？）
また、温度は温度関数によって決まり、線形 (1次関数) や非線形 (線形でない関数) のものがあります。これもあとから紹介します。
AHCの問題では、インタラクティブとノンインタラクティブがありますが、焼きなましは主にノンインタラクティブの、盤面を自由に動かせるようなときに使います。理由としては、インタラクティブは操作回数が制限されていて、焼きなましのポイントである大量の試行回数を稼げないためです。それに対して、毎回入力を受け取って何かを出力するようなインタラクティブでは、貪欲やビームサーチ、モンテカルロなどが採用されます。
今回扱う問題
ヒューリスティック
- AHC024 A - Topological Map
実際に解いてみる
この記事では、言語はC++を使います。
EDPC D - Knapsack 1
みなさんおなじみ、ナップサックDPです。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]+v[i]);
という遷移で解けます。（詳細略）
実際の提出（DP）
https://atcoder.jp/contests/dp/submissions/52731892
これを焼きなましで通します。問題を理解していない場合は、一度読んでみてください。まず近傍を考えます。袋に1個追加する近傍と、袋から1個削除する近傍がよさそうです。今回は、袋の重さ上限を超えないようにしています。ギリギリまで詰まっているときには、一回袋から取り出してから別のものを追加しないといけないので、入れ替える近傍もあった方がよさそうです。実際に、addとremoveに加えて、swapをすることでやっと通りました。
実際の提出（焼きなまし） https://atcoder.jp/contests/dp/submissions/47296658
- add近傍
// 20%の確率で操作を行う if (rd<20){ // 採用するindexを乱択する ll i = next_idx_add(); // 袋に入るかどうか if (add_ok(i)){ // 遷移確率を取得する double p = prob(value+v[not_having[i]], value, temp)*100; // 採用するとき if (p>rand(0, 100)){ // スコアを更新する value += v[not_having[i]]; // 答えを更新する ans = max(ans, value); // コストを更新する cost += w[not_having[i]]; // 状態を更新する having.push_back(not_having[i]); //// 後ろに回してからpopするとO(1) swap(not_having[i], not_having.back()); not_having.pop_back(); } } }
最初に、乱数を取得して、20%の確率でaddをしています。採用するインデックスは乱択しています（next_idx_add）。次に、袋にその荷物が入るかを判定しています（add_ok）。そして遷移確率を取得します（prob）。遷移する場合は、実際に答えと状態を更新します。今回は答えの更新がO(1)でできるので毎回行っていますが、状態のコピーにコストが大きくかかるとき、毎回コピーするとボトルネックになるので、差分更新をO(1)で行って、最後の状態をそのまま答えにすると思います。removeやswapもaddと同様に行っています。
- 遷移確率関数
これには有名なものがあります。
例えば、温度temp=3のとき、以下のグラフになります。
xはnewScore-preScoreということで、スコアの増加分になります（最小化するときはpreScore-newScoreになります）。tempをいろいろ変えてみると、温度が高いときx=0に近づいて、低いとき遠ざかることが分かります。また、newScore>=preScoreのとき、prob>=1になり、遷移確率が100%以上になります。つまり、この関数は「評価値が改善するか同じとき、遷移確率が必ず1以上になり、そうでないとき、温度が高いほど遷移確率が上がる（1未満）」という関数になります。
double prob(ll new_score, ll pre_score, double temp){ double e = 2.7; double p = pow(e, (new_score-pre_score)/temp); return p; }
- 温度関数
線形と非線形があります。
線形の例
double temp_init = 500; double temp_finish = 10; int time_limit = 1980; double temp = temp_init-(temp_init-temp_finish)*(now-start)/time_limit;
startは開始時の時間計測、nowは現在の時間計測で、now-startで経過時間を表しています。この式は、
とすると、
となり、初期温度から時間経過に応じて冷やしていく、というのが分かると思います。
非線形の例
double temp_init = 300; double temp = temp_init; double temp_finish = 5; double max_iter = 3e5; double change_rate = pow((temp_finish/temp_init), 1/max_iter); for (i=0; i<max_iter; i++){ // 処理 temp *= change_rate; }
これは、
というように、初期温度にdecreaseRateをmaxIter回かけて、最終的にtempFinishになってほしい、という式を変形して、1回当たり何倍すればよいのかを求めたものです。
競技プログラミングの鉄則 B23 - Traveling Salesman Problem
以降は問題についてのみ言及していきます。
この問題は、巡回セールスマン問題（Traveling Salesman Problem）で有名です。TSPといえばILS（Iterated Local Search、反復局所探索法、山登り+kick）ですね。（文脈を知らない人向け→ https://twitter.com/tombo_choco/status/1707402075540431138）（ほとんどの人が知らないと思います）（はい）
1msでfastestなので、うれしかったです。（bitDPで十分）
というのは置いておいて、まぁとにかくbitDPなわけですが、焼きなましをします（？）
実際の提出（bitDP）
https://atcoder.jp/contests/tessoku-book/submissions/50409603
実際の提出（焼きなまし）
https://atcoder.jp/contests/tessoku-book/submissions/46032854
実際の提出（ILS）（1ms）
https://atcoder.jp/contests/tessoku-book/submissions/46014747
- 近傍
ランダムに隣り合うインデックスを選んで、順番を入れ替えています。
（参考：2-opt法によるTSP | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】）
このような2-optをしたかったのですが、これがそうなっているのかよく分かっていません（そんな）
とにかく、これで通りました。
vector<ll> next_state_rand(vector<ll> v){ if (N<=3){ return v; } ll r = rand(v.size()-3)+1; ll tmp = v[r]; v[r] = v[r+1]; v[r+1] = tmp; return v; }
double temp_init = 1e4; double temp = temp_init; double ans = inf; const ll max_iter = 1e6; ll c = 0; while (c<=max_iter){ c++; // 2-optで焼きなまし vector<ll> next = next_state_rand(state); double new_score = calc(next); ans = min(ans, new_score); double p = prob(new_score, score, temp)*100; // prob()の確率で遷移する if (p>rand(100)){ state = next; score = new_score; } // 温度関数を更新する temp *= 0.999995; }
今回は、temp *= 0.999995としました。
AHC024 A - Topological Map
これはヒューリスティックコンテストなので、最適解ではないですが、延長戦順位表で1849パフォが取れているので、そこそこ参考になると思います。
この解法には、山登りの前処理が含まれていて、それについても簡単に説明します。
- 問題の概要
色の連結関係をキープし、色ごとに連結成分を1個に保ちながら、なるべく面積を小さくするというものです。
- アプローチ
- 行列削除山登り
- 隣接侵食焼きなまし
（この2つの語感すき）
まず、行と列で消しても問題ない箇所があるので、それを山登りで削除します。貪欲みたいな感じですね（？）そこから焼きなましに移行します。隣り合うマスに色をコピーします。白いところを塗るのが悪化する遷移、白いマスを増やすのが改善する遷移です。制約を守るのがめんどうですが、3x3マスの中心1マスに向けて色をコピーすることを考えると、結構分かりやすくなります。詳しいことを聞きたかったら、コメントやXなどで質問してもらえれば答えます、自分に答えられる範囲で（）
ビジュアライザ
- 近傍
（山登りは省略）
// その方向から色を移せるか判定する bool move_ok(ll i, ll j, string dir_from){ // 変化前の9マスの中心 ll pre_col = c[i][j]; // 同じ色に移すときfalse if (dir_from=="U" && c[i-1][j]==pre_col || dir_from=="D" && c[i+1][j]==pre_col || dir_from=="L" && c[i][j-1]==pre_col || dir_from=="R" && c[i][j+1]==pre_col){ return false; } // その色がなくなるときfalse if (cnt_color[c[i][j]]<=1) return false; // 3x3マスをコピーする vector new_c(3, vector(3, ll(0))); rep(p, 0, 3){ rep(q, 0, 3){ new_c[p][q] = c[i+p-1][j+q-1]; } } // 実際に色を移す ll new_i = 1; ll new_j = 1; if (dir_from=="U") new_c[new_i][new_j] = new_c[new_i-1][new_j]; if (dir_from=="D") new_c[new_i][new_j] = new_c[new_i+1][new_j]; if (dir_from=="L") new_c[new_i][new_j] = new_c[new_i][new_j-1]; if (dir_from=="R") new_c[new_i][new_j] = new_c[new_i][new_j+1]; // 変化後の9マスの中心 ll new_col = new_c[new_i][new_j]; // 色間の連結保持判定 map<ll, set<ll>> pre_color, new_color; rep(p, 0, 3){ rep(q, 0, 3){ ll a = i+p-1; ll b = j+q-1; // 変化前の連結関係 if (a-1>=i-1){ pre_color[c[a][b]].insert(c[a-1][b]); pre_color[c[a-1][b]].insert(c[a][b]); } if (a+1<=i+1){ pre_color[c[a][b]].insert(c[a+1][b]); pre_color[c[a+1][b]].insert(c[a][b]); } if (b-1>=j-1){ pre_color[c[a][b]].insert(c[a][b-1]); pre_color[c[a][b-1]].insert(c[a][b]); } if (b+1<=j+1){ pre_color[c[a][b]].insert(c[a][b+1]); pre_color[c[a][b+1]].insert(c[a][b]); } // 変化後の連結関係 if (p-1>=0){ new_color[new_c[p][q]].insert(new_c[p-1][q]); new_color[new_c[p-1][q]].insert(new_c[p][q]); } if (p+1<3){ new_color[new_c[p][q]].insert(new_c[p+1][q]); new_color[new_c[p+1][q]].insert(new_c[p][q]); } if (q-1>=0){ new_color[new_c[p][q]].insert(new_c[p][q-1]); new_color[new_c[p][q-1]].insert(new_c[p][q]); } if (q+1<3){ new_color[new_c[p][q]].insert(new_c[p][q+1]); new_color[new_c[p][q+1]].insert(new_c[p][q]); } } } // 色の連結性が違ったらfalse if (pre_color!=new_color) return false; // 同一色の連結保持判定 // 変化後の色ごとの連結成分の個数が2以上でfalse used.clear(); rep(p, 0, 3){ rep(q, 0, 3) seen[p][q] = false; } rep(p, 0, 3){ rep(q, 0, 3) if (used.count(new_c[p][q])==0) dfs(p, q, new_c); } rep(p, 0, 3){ rep(q, 0, 3) if (seen[p][q]==false) return false; } // 色を移すことができる return true; }
近傍というか、遷移できるかどうかの判定になっています。近傍は座標を乱択しています。
// 同一色の連結保持判定 // 9マスの中で色ごとに連結成分の個数を数える void dfs(ll p, ll q, vector<vector<ll>> new_c){ seen[p][q] = true; used.insert(new_c[p][q]); if (p-1>=0 && new_c[p-1][q]==new_c[p][q] && !seen[p-1][q]){ dfs(p-1, q, new_c); } if (p+1<3 && new_c[p+1][q]==new_c[p][q] && !seen[p+1][q]){ dfs(p+1, q, new_c); } if (q-1>=0 && new_c[p][q-1]==new_c[p][q] && !seen[p][q-1]){ dfs(p, q-1, new_c); } if (q+1<3 && new_c[p][q+1]==new_c[p][q] && !seen[p][q+1]){ dfs(p, q+1, new_c); } }
同じく、遷移できるかどうかの判定です。条件としては、色の連結関係が変わらないか、連結成分が1個であるかの2つがあるので、近傍を乱択してから判定してOKだったら遷移しています。
double temp = temp_init-(temp_init-temp_finish)*(now-start)/time_limit;
温度関数は線形ですね。遷移確率関数は上と同じです。ちなみに、乱数生成器はmt19937（メルセンヌ・ツイスタ）を使っています。
mt19937 mt(now()); ll rand(ll a, ll b) { if (b<=a){ cerr << "RandRangeError" << " a:" << a << " b:" << b << endl; return -1; } return mt()%(b-a)+a; }
実際の提出 https://atcoder.jp/contests/ahc024/submissions/49364292
以上で3つの問題への、焼きなましを使ったアプローチの説明を終わります。自分は、焼きなましには圧倒的なパワーがあると思っていて、GA（遺伝的アルゴリズム）のように時間がかからず、ビームサーチより汎用性が高い気がして、すごく便利だと思っています。雑に殴ればいいじゃんてきな？いや、分からないですが、楽しいのでぜひぜひって感じです。
おまけ
- 動きが悪かったら評価値の変化が小さいかもなので100倍とかしてみてください、動きがある程度大きい方がよく解空間を探索できてうれしいです。初期温度も高くしてみてください。
- 温度は自分は線形のものを使っています。
- アルゴがACできると楽しいです、特にDPは割といけると思います、EDPCとか。
まとめ
いかがでしたか？（言いたいだけ）
いろいろガバかったらすみません、これはあくまで自分の感想を共有するみたいなノリで軽く眺めてほしくて、本格的に焼きなましをやりたかったらrhooさんの記事（p/tech/.md at main · rhoo19937/p · GitHub）とかも参考になると思います。C++の実装が読みにくかったり、質問があったり、間違いの指摘などがあったらどんどん言ってもらえれば、自分に対応できる範囲でいろいろやります。これからもなにか思いついたら書いていくかもなので、またよろしくお願いします（？）
