頂点被覆バトル 後編（対戦編）

はじめに

この記事は前編の続きです．前編ではグラフの作成方法について書いています．
https://zenn.dev/suikinkutsu/articles/81b0c702e76513

頂点被覆バトルをしました(参加者 $3$ 人）．

頂点被覆の説明は Wikipedia にお任せします．
https://ja.wikipedia.org/wiki/頂点被覆
ざっくり言うと，無向グラフが与えられたときに，次を満たすようにいくつかの頂点を選択したものを頂点被覆と呼びます．

• 全ての辺について，どちらかの頂点が選択されている

参加者はソルバーとグラフを作成します．
ソルバーの目標は，グラフが与えられた時，なるべく少ない頂点を用いた被覆を出力することです．（最小の被覆を求めるのは NP 困難です．）

この時与えられるグラフは，別の参加者が作ったグラフです．すなわち，なるべく頂点被覆が求めにくいグラフを作成すると良いです．

具体的なルールは次の項で．

ルール

参加者は $10000$ 頂点以下 $10000$ 辺以下のグラフを 1 つ作成する．また，そのグラフの頂点被覆の模範解答を作成する（模範解答が最小である必要はない）．
また，参加者は solver を作成する．これは，グラフを入力とし，そのグラフの頂点被覆を出力とする．solver の実行時間は $20$ 秒以内．
参加者 $i$ のスコアは以下の式で求められる．スコアは高いほど良い．
$\sum_{j\neq i}{\left\{\left|\mathrm{solver}_j(グラフ_i)\right|-\left|模範解答_i\right|-\left(\left|\mathrm{solver}_i(グラフ_j)\right|-\left|模範解答_j\right|\right)\right\}}$
$solver_x(グラフ_y)$ は参加者 $x$ の solver が参加者 $y$ の作成したグラフを解いた時の被覆を表します．$\left|被覆\right|$ は被覆の頂点数を表します．

戦略

駒上（筆者）

実験をしたりした結果，隣接する被覆されていない頂点が多い頂点から貪欲に選ぶ手法が有効であることがわかりました．

グラフ作成

貪欲法がなるべく通用しにくいようなグラフを山登り法で作成しました．具体的なグラフの作成手法については前回を参照してください．
https://zenn.dev/suikinkutsu/articles/81b0c702e76513

ソルバー

solver は貪欲法とヒューリスティクスを組み合わせた手法を用いました．組み合わせ方については，他の記事にまとめたので，こちらを参照してください．
https://zenn.dev/komagami/articles/ecd348f04c2342

参加者 A

グラフ作成

$20$ 頂点程度のグラフであれば，全探索で最小頂点被覆を求めることが可能です．最小頂点被覆を求めた $20$ 頂点のグラフをたくさん用意し，被覆されていない頂点同士が結ばれないようにそれらをくっつけたらしいです．

ソルバー

グラフの極大マッチングを作成し，極大マッチングに用いた辺の両端点を選択すると，頂点被覆となります．
極大マッチングを作るために見ていく辺の順序を山登り法で調べたらしいです．

参加者 B

貪欲が有効であることは彼も気が付いていたらしいです．

グラフ作成

貪欲に頂点を選ぶと被覆として選択する頂点数が嵩む構造を手動で作成し，その構造を繰り返したらしいです．

ソルバー

貪欲戦術のみでヒューリスティクスは用いなかったらしいです．

結果

駒上（筆者），参加者 A ，参加者 B の $3$ 人で対戦を行いました．

結果は下の表のようになりました．

	模範解答	駒上	参加者 A	参加者 B
駒上	3565		4568(+1003)	4409(+844)
参加者 A	3500	3500(+0)		3500(+0)
参加者 B	3125	3129(+4)	4670(+1545)

最終的なスコアは以下のようになりました．

名前	スコア
駒上	1843
参加者 B	705
参加者 A	-2548

優勝しました．やったぜ．

おわりに

頂点被覆バトルをしました．
方針として貪欲が強いことに気づけるか，と言うところが大きかったように感じます．実際，筆者が作ったグラフに対して，参加者 B のソルバーはただの貪欲ですが，参加者 A のソルバーより良い結果を出しています．筆者のグラフは貪欲のスコアをなるべく悪くしようしているのにも関わらず，です．
今後もこんな感じのプログラミングで競技をやる...かも？