はじめに
頂点被覆バトルをしました(参加者
頂点被覆の説明は Wikipedia にお任せします． ざっくり言うと，無向グラフが与えられたときに，次を満たすようにいくつかの頂点を選択したものを頂点被覆と呼びます．
- 全ての辺について，どちらかの頂点が選択されている
参加者はソルバーとグラフを作成します．
ソルバーの目標は，グラフが与えられた時，なるべく少ない頂点を用いた被覆を出力することです．（最小の被覆を求めるのは NP 困難です．）
この時与えられるグラフは，別の参加者が作ったグラフです．すなわち，なるべく頂点被覆が求めにくいグラフを作成すると良いです．
具体的なルールは次の項で．
ルール
参加者は
また，参加者は solver を作成する．これは，グラフを入力とし，そのグラフの頂点被覆を出力とする．
参加者
方針
下の図のように，ベースとなるグラフ，被覆する頂点（図中青色）を先に決めます．その後に被覆している頂点を含むような辺を追加します．
この順にグラフを作成することで，最小の頂点被覆が既知であるグラフを作成することができます．
すぐ思いつく Solver として，隣接する被覆されていない頂点が多い頂点から貪欲に選ぶ，という手法が考えられます．
この貪欲法に加えて，隣接している被覆されていない頂点が1つである被覆されていない頂点が存在する場合，隣接している頂点を被覆する（下図の頂点
この手法（以下，貪欲と表記します）が優秀すぎるので，ベースとなるグラフを作り，それにランダムに辺を追加する場合，ほとんど最適解が得られてしまいます．
そこで，山登り法を用いて貪欲キラーとなるグラフを作成しました．
まず，ベースとなるグラフを用意します．下の図のような，リング状のグラフをベースとしました．
うっかり2部グラフを作ってしまわないように（最小被覆が
このグラフに，辺を追加していきます．
辺を追加する戦略として，次のような山登り法が考えられます．
- ランダムに辺を追加（辺の片側は被覆されている頂点）します．
- ランダムに辺を張り替え，もし貪欲を用いた際のスコアが下がらないなら採用
-
- を繰り返す
しかし，頂点数が多いので上手く探索が行えませんでした．
そこで，同じ構造を繰り返すグラフを作成することで，効率的に探索を行えるようにしました．
上図のような構造を作りました，黄色のかたまりの中の構造は共通です．
このかたまりの中の辺の張り方を山登り法で探索したところ，良い結果が得られました．
具体的には，
このグラフで挑みます．
他の参加者の solver が貪欲ベースなら刺さるのではないでしょうか．おそらく．
結果は次回．
補足
文中の貪欲について補足します．
隣接する被覆されていない頂点の数が同じ頂点が複数あるときの優先順位について考えなければなりません．例えば頂点番号の大小などを用いると，頂点番号をシャッフルされた時点で意味がなくなってしまいます．
そのため，貪欲を用いて評価する際には毎回優先度をランダムに割り当てています．ランダムに割り当てている影響で結果が多少大小します（複数回評価を行うことで影響を抑えてはいます）．なので山登り法と言いつつ，焼きなまし法のような効果が期待できます．
ソースコード
次のプログラムでグラフを生成します．
乱数には Xorshift を用いています．軽量で高速なので使い勝手が非常に良いです．
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#include <set>
struct Graph {
int numNodes;
std::vector<std::vector<int>> edges;
Graph() {}
Graph(int n) : numNodes(n), edges(n) {}
void addEdge(int u, int v) {
edges[u].push_back(v);
edges[v].push_back(u);
}
};
struct GraphWithSet {
int numNodes;
std::vector<std::set<int>> edges;
GraphWithSet(int n) : numNodes(n), edges(n) {}
bool addEdge(int u, int v) {
edges[u].insert(v);
return edges[v].insert(u).second;
}
void removeEdge(int u, int v) {
edges[u].erase(v);
edges[v].erase(u);
}
};
class Xorshift {
private:
uint64_t state;
public:
Xorshift(uint64_t seed) { state = seed; }
uint64_t next() {
state ^= state << 7;
state ^= state >> 9;
return state;
}
uint64_t nextInt(uint64_t n) { return next() % n; }
};
int solveGreedyRandom(const Graph &graph, Xorshift &randomEngine) {
std::priority_queue<std::tuple<int, uint64_t, int>>
uncoveredNeighborsQueue; // (隣接する被覆されていない頂点の数, 優先度,
// 頂点)
std::vector<int> uncoveredNeighbors(
graph.numNodes, 0); // 隣接する頂点のうち被覆されていない頂点の数
std::vector<int>
singleUncoveredNeighborVertices; // 隣接する被覆されていない頂点が
// 1 つの場合を記録
std::vector<bool> covered(graph.numNodes, false); // 被覆した頂点を記録
std::vector<uint64_t> priorityTable(graph.numNodes);
for (uint64_t &val : priorityTable) {
val = randomEngine.next();
}
for (int i = 0; i < graph.numNodes; i++) {
uncoveredNeighbors[i] = graph.edges[i].size();
uncoveredNeighborsQueue.emplace(uncoveredNeighbors[i], priorityTable[i],
i);
if (uncoveredNeighbors[i] == 1) {
singleUncoveredNeighborVertices.push_back(i);
}
}
while (!uncoveredNeighborsQueue.empty()) {
while (
!singleUncoveredNeighborVertices
.empty()) { // 隣接する被覆されていない頂点が 1
// つの頂点が存在する場合，その隣の頂点を採用する
int node = singleUncoveredNeighborVertices.back();
singleUncoveredNeighborVertices.pop_back();
if (uncoveredNeighbors[node] != 1 || covered[node]) {
continue;
}
for (int neighbor : graph.edges[node]) {
if (!covered[neighbor]) {
// neighbor を採用
covered[neighbor] = true;
for (int neighborOfNeighbor : graph.edges[neighbor]) {
if (!covered[neighborOfNeighbor]) {
uncoveredNeighbors[neighborOfNeighbor]--;
if (uncoveredNeighbors[neighborOfNeighbor] == 1) {
singleUncoveredNeighborVertices.push_back(
neighborOfNeighbor);
} else {
uncoveredNeighborsQueue.emplace(
uncoveredNeighbors[neighborOfNeighbor],
priorityTable[neighborOfNeighbor],
neighborOfNeighbor);
}
}
}
}
}
}
auto [uncoveredNeighborsCount, priority, node] =
uncoveredNeighborsQueue.top();
uncoveredNeighborsQueue.pop();
if (uncoveredNeighbors[node] != uncoveredNeighborsCount ||
uncoveredNeighborsCount == 0 || covered[node]) {
continue;
}
covered[node] = true;
for (int neighbor : graph.edges[node]) {
if (!covered[neighbor]) {
uncoveredNeighbors[neighbor]--;
if (uncoveredNeighbors[neighbor] == 1) {
singleUncoveredNeighborVertices.push_back(neighbor);
} else {
uncoveredNeighborsQueue.emplace(
uncoveredNeighbors[neighbor], priorityTable[neighbor],
neighbor);
}
}
}
}
int count = 0;
for (bool b : covered) {
count += b;
}
return count;
}
int main(int argc, char **argv) {
Xorshift randomEngine(12345678);
const int numMaxEdges = 10000;
const int numRepeats = 99;
const int nodesPerRepeat = 72;
const int numNodes = nodesPerRepeat * numRepeats + 1;
const int evalRepeats = 10;
int bestScore = 0;
GraphWithSet graphRepeated(nodesPerRepeat);
int randomEdgesSize = (numMaxEdges - numNodes) / numRepeats;
std::vector<std::pair<int, int>> randomEdges(randomEdgesSize);
std::vector<std::pair<int, int>> bestRandomEdges;
int coveredVerticesSize = (numNodes + 1) / 2;
for (int i = 0; i < nodesPerRepeat - 1; i++) {
graphRepeated.addEdge(i, i + 1);
}
for (int i = 0; i < nodesPerRepeat; i++) {
graphRepeated.addEdge(i, i); // 自己ループ
}
for (auto &[u, v] : randomEdges) {
do {
u = randomEngine.nextInt(nodesPerRepeat / 2) *
2; // 偶数番目（被覆頂点）
v = randomEngine.nextInt(nodesPerRepeat);
} while (!graphRepeated.addEdge(u, v)); // 多重辺と自己ループを弾く
}
// 変則的な山登り法を行う
for (int i = 0; i < 100000; i++) {
Graph graph(numNodes);
for (int j = 0; j < numNodes - 1; j++) {
graph.addEdge(j, j + 1);
}
graph.addEdge(numNodes - 1, 0);
for (auto [u, v] : randomEdges) {
for (int j = 0; j < numRepeats; j++) {
graph.addEdge(u + nodesPerRepeat * j, v + nodesPerRepeat * j);
}
}
int prevScore = 0;
for (int j = 0; j < evalRepeats; j++) {
prevScore += solveGreedyRandom(graph, randomEngine);
}
if (i % 100 == 0) {
std::cout << i << " "
<< (double)prevScore / evalRepeats - coveredVerticesSize
<< "\n";
}
int nextCandidate = randomEngine.nextInt(randomEdgesSize);
auto [prevU, prevV] = randomEdges[nextCandidate];
auto &[nextU, nextV] = randomEdges[nextCandidate];
graphRepeated.removeEdge(prevU, prevV);
do {
nextU = randomEngine.nextInt(nodesPerRepeat / 2) *
2; // 偶数番目（被覆頂点）
nextV = randomEngine.nextInt(nodesPerRepeat);
} while (!graphRepeated.addEdge(nextU, nextV));
Graph nextGraph(numNodes);
for (int j = 0; j < numNodes - 1; j++) {
nextGraph.addEdge(j, j + 1);
}
nextGraph.addEdge(numNodes - 1, 0);
for (auto [u, v] : randomEdges) {
for (int j = 0; j < numRepeats; j++) {
nextGraph.addEdge(u + nodesPerRepeat * j,
v + nodesPerRepeat * j);
}
}
int nextScore = 0;
for (int j = 0; j < evalRepeats; j++) {
nextScore += solveGreedyRandom(nextGraph, randomEngine);
}
if (prevScore > nextScore) {
graphRepeated.removeEdge(nextU, nextV);
graphRepeated.addEdge(prevU, prevV);
randomEdges[nextCandidate] = std::make_pair(prevU, prevV);
}
if (bestScore < nextScore) {
bestRandomEdges = randomEdges;
bestScore = nextScore;
}
}
std::cout << "Score : "
<< (double)bestScore / evalRepeats - coveredVerticesSize
<< std::endl;
// 出力パート
std::vector<int> order(numNodes); // 頂点シャッフルもどき
std::vector<int> coveredVertices;
for (int i = 0; i < numNodes; i++) {
order[i] = i;
}
for (int i = 0; i < numNodes; i++) {
std::swap(order[i], order[randomEngine.nextInt(numNodes)]);
}
for (int i = 0; i < numNodes; i++) {
if (i % 2 == 0) {
coveredVertices.push_back(order[i]);
}
}
Graph graphShuffled(numNodes);
for (int i = 0; i < numNodes; i++) {
graphShuffled.addEdge(order[i], order[(i + 1) % numNodes]);
}
for (auto [u, v] : bestRandomEdges) {
for (int j = 0; j < numRepeats; j++) {
graphShuffled.addEdge(order[u + nodesPerRepeat * j],
order[v + nodesPerRepeat * j]);
}
}
std::ofstream graphOut(argv[1]);
int edgeCount = 0;
for (std::vector<int> edges : graphShuffled.edges) {
edgeCount += edges.size();
}
edgeCount /= 2;
graphOut << graphShuffled.numNodes << ' ' << edgeCount << '\n';
for (int i = 0; i < graphShuffled.numNodes; i++) {
for (int e : graphShuffled.edges[i]) {
if (i < e) {
graphOut << i << ' ' << e << '\n';
}
}
}
std::ofstream coverOut(argv[2]);
coverOut << coveredVerticesSize << '\n';
for (int i = 0; i < coveredVerticesSize; i++) {
coverOut << coveredVertices[i];
if (i != coveredVerticesSize - 1) {
coverOut << ' ';
}
}
coverOut << '\n';
}
Discussion