最小頂点被覆問題(minmum Vertex Cover)の近似アルゴリズムの実装

最小頂点被覆問題(minmum Vertex Cover)の近似アルゴリズムの実装をしますよ.

この記事はゆるふわです.不可解な点があれば鵜呑みにせず,信用できる資料に当たってください.
例えば,論文はもちろん,英wikipedia,大学の講義資料などがあります.

2017/06/16 追記 多項式時間で計算できる最小頂点被覆問題についてを書きました.



問題

英Wikipediaを参照.

辺集合$E$,頂点集合$V$から成るグラフ$G$が与えられる.
頂点集合$S\subseteq V$を考える.
全ての辺$e \in E$が,$S$に含まれる頂点に接続している時,$S$はグラフ$G$の頂点被覆と呼ぶ.

集合の大きさが最小であるようなグラフ$G$の頂点被覆$S$を求めてください.

分類

NP困難.なので,近似アルゴリズムについて,多くの研究成果がある.

『$|S|$が$k$以下になるような解が存在するか?』という判定問題はNP完全.




コード全体

いきなりですが,実装コード置いておきます.C++14です.

https://gist.github.com/buyoh/389e7d8254584529b8d09a0a7e573167




近似アルゴリズム1

古典的な近似アルゴリズムがいくつか知られています.次にそのアルゴリズムを示します.

  • $E $ 頂点集合
  • $V $ 辺集合
  • $G $ グラフ$(E,V)$
  • $C $ 頂点被覆集合(結果)
  • 記号 $\leftarrow$ は代入を表現する
  • $\deg(v) $ は頂点 $v$ の次数
1. $P \leftarrow $ 要素数 $|V|$ の配列
2. $i \leftarrow 1..|V|$ について
    1. $P_i \leftarrow \deg(V_i) $
3. $C \leftarrow \emptyset$
4. それぞれの $e \leftarrow E$ について,
    1.辺 $e$ に接続している頂点 $u,v$ のどちらも $C$ に含まれていないなら
        1. $t \leftarrow \min(P_u,P_v)$
        2. $P_u \leftarrow P_u - t$
        3. $P_v \leftarrow P_v - t$
        4. $P_u = 0$ ならば $C \leftarrow C \cup \{P_u\}$
        5. $P_v = 0$ ならば $C \leftarrow C \cup \{P_v\}$

時間計算量は $O(|V|+|E|)$ ですね.
この近似アルゴリズムは最適解の2倍以内で抑えられることが証明されています.
帰納法で証明できます.

実際のコードは144行目あたりにあります.




近似アルゴリズム2

とりあえずの解を求めておきたいならば,上のアルゴリズムで十分ですが,精度はあまり良くないです.
そこで,次のような状況を考えます.

制限時間が設けられており,時間内になるべく最適解に近い近似解を求めたい.

このようなアルゴリズムの代表例として焼きなまし法などがありますが,ぱっと適用できなかったので本記事ではやりません.

実際のコードはここにあります

以下では雑なアルゴリズムを示します.本当はもっとマシな事をやっています.
より具体的な内容は実際のコードを見てください.

  • $BestSet$ スコアが最も良かった集合を保持する.
0. $C \leftarrow $近似アルゴリズム1の結果
1. $BestSet \leftarrow C$
2. 制限時間内であれば以下を繰り返す
    1. $v \leftarrow (C の中からランダムに1個)$
    2. $C \leftarrow C - {v}$
    3. $C$は頂点被覆を満たさない間次を繰り返す
        1. $v$に隣接する頂点を $C$ に加える
    4. $|BestSet| \gt |C|$ ならば
        1. $BestSet \leftarrow C$
    5. 長い期間 $BestSet$ が変化していないならば
        1. $C \leftarrow BestSet$

TODO: 加筆




参考

  1. https://en.wikipedia.org/wiki/Vertex_cover
  2. https://ja.wikipedia.org/wiki/%E9%A0%82%E7%82%B9%E8%A2%AB%E8%A6%86
  3. 講義資料

webページについては,2017/01/21に閲覧.

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1139位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
191位
アクセスランキングを見る>>