ナップサック問題でマラソンマッチ入門
マラソンマッチって？
競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。
例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。
マラソンでよく使われるアルゴリズム
マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。
この記事ではナップサック問題を例にしてこの２つのアルゴリズムを解説します。
もちろん、この２つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。
ビームサーチ
まずは順番にナップサックに入るだけ入れるコードを書いてみます。
#include <iostream> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 重さ・価値 int w[N], v[N]; for (int i = 0; i < N; ++i) cin >> w[i] >> v[i]; // 今までに入れた物の重さの総和 int s = 0; // 今までに入れた物の価値の総和 long long t = 0; // 入るだけ入れる for (int i = 0; i < N; ++i) { if (s + w[i] <= W) { s += w[i]; t += v[i]; } } // 結果 cout << t << endl; }
これをビームサーチに書き換えるとこうなります。
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // ビーム幅 const int BEAM = 100; // 重さ・価値 int w[N], v[N]; for (int i = 0; i < N; ++i) cin >> w[i] >> v[i]; // 現在の状態（価値・重さ） vector<pair<long long, int>> curr; curr.emplace_back(0, 0); // ビームサーチ for (int i = 0; i < N; ++i) { // 次の状態（価値・重さ） vector<pair<long long, int>> next; for (const auto& s : curr) { next.emplace_back(s); if (s.second + w[i] <= W) { next.emplace_back(s.first + v[i], s.second + w[i]); } } // 価値が大きい順に並び替え sort(next.rbegin(), next.rend()); // 状態をビーム幅に減らす if (next.size() > BEAM) next.resize(BEAM); curr = move(next); } // 結果 cout << curr[0].first << endl; }
それぞれの状態について物を入れるか入れないかの遷移を行って、スコアの良い上位１００個の状態を残しています。
この１００個のことをビーム幅と呼び、基本的にはこれが大きければ大きいほど良いので、ビームサーチを使うときは高速化が効果的である場合が多いです。
どれくらい改善するかを試した所、以下のようになりました。
| アルゴリズム | スコア |
|---|---|
| 愚直 | 829374 |
| ビームサーチ | 3252218 |
| 厳密解 | 26383646 |
実験に使った入力はこれです。
愚直解に比べるとだいぶ改善していますが、厳密解はかなり遠いです。
これは、問題の性質を上手く使えていないのが原因です（最後に書きます）。
焼きなまし
今度はまだナップサックに入れていない荷物を選んで、選んだ荷物が入るように入っている荷物をランダムに捨てるとしてスコアが改善するなら実際に荷物を入れる、という方法を考えます。
#include <algorithm> #include <iostream> using namespace std; // 乱数生成器 inline uint32_t rnd(void) { static uint32_t y = 2463534242; y = y ^ (y << 13); y = y ^ (y >> 17); return y = y ^ (y << 5); } int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // ループ回数 const int T = 1000000; // 重さ・価値 int w[N], v[N]; for (int i = 0; i < N; ++i) cin >> w[i] >> v[i]; // 今までに入れた物の重さの総和 int s = 0; // 今までに入れた物の価値の総和 long long t = 0; // 今までに入れた物・入れていない物 vector<int> used, unused(N); // はじめは全て使っていない iota(unused.begin(), unused.end(), 0); for (int i = 0; i < T; ++i) { // 次に入れる物をランダムに選ぶ int k = rnd() % unused.size(); // ナップサックに収まるようにランダムに捨てる int ss = 0; long long tt = 0; vector<int> del; while (tt < v[k] && s + w[unused[k]] - ss > W) { int kk = rnd() % used.size(); if (find(del.begin(), del.end(), kk) != del.end()) continue; ss += w[used[kk]]; tt += v[used[kk]]; del.emplace_back(kk); } // 価値が大きくなるなら更新 if (tt < v[k] && s + w[unused[k]] - ss <= W) { s += w[k] - ss; t += v[k] - tt; unused[k] = unused.back(); unused.pop_back(); used.emplace_back(k); sort(del.rbegin(), del.rend()); for (int kk : del) { used[kk] = used.back(); used.pop_back(); unused.emplace_back(kk); } } } // 結果 cout << t << endl; }
これを焼きなまし法に書き換えるとこうなります。
#include <algorithm> #include <iostream> using namespace std; // 乱数生成器 inline uint32_t rnd(void) { static uint32_t y = 2463534242; y = y ^ (y << 13); y = y ^ (y >> 17); return y = y ^ (y << 5); } bool next(long long b, int t) { if (b > 0) return true; return exp(b / 10000.0 / pow(0.999999, t)) > double(rnd()) / numeric_limits<uint32_t>::max(); } int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // ループ回数 const int T = 1000000; // 重さ・価値 int w[N], v[N]; for (int i = 0; i < N; ++i) cin >> w[i] >> v[i]; // 今までに入れた物の重さの総和 int s = 0; // 今までに入れた物の価値の総和 long long t = 0; // 今までに入れた物・入れていない物 vector<int> used, unused(N); // はじめは全て使っていない iota(unused.begin(), unused.end(), 0); for (int i = 0; i < T; ++i) { // 次に入れる物をランダムに選ぶ int k = rnd() % unused.size(); // ナップサックに収まるようにランダムに捨てる int ss = 0; long long tt = 0; vector<int> del; while (tt < v[k] + 10000 && s + w[unused[k]] - ss > W) { int kk = rnd() % used.size(); if (find(del.begin(), del.end(), kk) != del.end()) continue; ss += w[used[kk]]; tt += v[used[kk]]; del.emplace_back(kk); } // 焼きなまし if (next(v[k] - tt, i) && s + w[unused[k]] - ss <= W) { s += w[k] - ss; t += v[k] - tt; unused[k] = unused.back(); unused.pop_back(); used.emplace_back(k); sort(del.rbegin(), del.rend()); for (int kk : del) { used[kk] = used.back(); used.pop_back(); unused.emplace_back(kk); } } } // 結果 cout << t << endl; }
スコアが改善しない時も、選んだ荷物をたまには使うようにします。
選んだ荷物を使う確率は、スコアの下落幅が小さい・ループの始めのほうで大きくなるようにします。
ループの後半になるに従って荷物を使う確率を下げていきますが、これに用いるパラメータを温度と呼びます。
このような温度管理によって局所解に陥ることをある程度回避することができます。
スコアは以下のようになりました。
| アルゴリズム | スコア |
|---|---|
| 愚直 | 18241125 |
| 焼きなまし法 | 21275856 |
| 厳密解 | 26383646 |
終わりに
ビームサーチと焼きなまし法を紹介しましたが、これを使えばマラソンマッチで簡単に勝てるかというとそんなことはありません。
一番大事なのは問題の性質を理解することです。
例えば今回の問題の場合、価値÷重さでソートした後に順番に詰めていくだけでかなり良いスコアが出ます。
#include <algorithm> #include <iostream> using namespace std; struct Item { int w, v; bool operator>(const Item& i) const {return (double)v / w > (double)i.v / i.w;} }; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 荷物 Item item[N]; for (int i = 0; i < N; ++i) cin >> item[i].w >> item[i].v; sort(item, item + N, greater<Item>()); // 今までに入れた物の重さの総和 int s = 0; // 今までに入れた物の価値の総和 long long t = 0; // 入るだけ入れる for (int i = 0; i < N; ++i) { if (s + item[i].w <= W) { s += item[i].w; t += item[i].v; } } // 結果 cout << t << endl; }
| アルゴリズム | スコア |
|---|---|
| ビームサーチ | 3252218 |
| 焼きなまし法 | 21275856 |
| ソート | 26382284 |
| 厳密解 | 26383646 |
この解法を元にしてビームサーチや焼きなまし法をすることはできますが、そのようなアルゴリズムの知識よりも問題の考察が重要になることが多いです。
この辺りの話はtakaptさんの記事によくまとまっています。
もちろん、知識は多いほど有利になるのは間違いありません。
ぜひマラソンマッチに参加して経験を詰んだり他の参加者から知識を吸収したりして下さい。
そう言えば今日、Chokudai Contest 001ってのがAtCoderで開催されるらしいので参加してみてはどうでしょうか（ステマ）。
