buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

最小頂点被覆の指数時間アルゴリズムの実装(その2,分岐限定法)

その2.

2018/05/19 : note : 後日アルゴリズム含め全て書き直す可能性があります.

最終目標

これをACする.

code-thanks-festival-2017-open.contest.atcoder.jp

知識

最小頂点被覆問題?

グラフG=(V,E)が与えられる.
頂点集合S⊆Vを考える.
全ての辺e∈Eが,Sに含まれる頂点に<u>1つ以上</u>接続している時,SはグラフGの頂点被覆と呼ぶ.

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

note

  • 頂点数N,辺の数M
  • 与えられたグラフは単純グラフである(多重辺,ループ辺は無い)
  • 辺は1本以上存在する
  • 頂点に割り当てられた重みは全て等しい(考慮しない).

と仮定します.

説明で使うグラフ構造体を示します.

struct Graph {
    size_t n;
    vector<vector<int>> vertex_to;

    Graph(size_t n = 1) :n(n), vertex_to(n) {}
    void connect(int from, int to) {
        vertex_to[(size_t)from].emplace_back(to);
        vertex_to[(size_t)to].emplace_back(from);
    }
    void resize(size_t _n) {
        n = _n;
        vertex_to.resize(_n);
    }
};

基礎

  • 再帰式で実装する.
  • 工夫する必要が無いのであれば,時間計算量 O((N+M)2N),空間計算量 O(N) の次のような実装が思いつく.
  • ただcoverを全探索しているだけ
int vertex_cover(const Graph& graph) {
    const int n = graph.n;

    // cover[i] = -1 : 未決定
    //             0 : 選択しない
    //             1 : 選択する

    function<bool(const Graph&, const vector<int>&)> iscover = [](const Graph& graph, const vector<int>& cover) {
        for (int j = 0; j < graph.n; ++j)
            if (cover[j] == 0)
                for (int to : graph.vertex_to[j])
                    if (!cover[to])
                        return false;
        return true;
    };

    int best = n;

    function<void(int, vector<int>)> dfs = [&](int idx, vector<int> cover) {
        if (idx == n) { // すべての頂点を決めた
            if (iscover(graph, cover)) {
                // 頂点被覆なら更新
                int cnt = 0;
                for (int e : cover) cnt += (e == 1);
                best = min(best, cnt);
            }
        }
        else {
            int r;
            cover[idx] = 0;
            dfs(idx + 1, cover);
            cover[idx] = 1;
            dfs(idx + 1, cover);
        }
    };
    dfs(0, vector<int>(n, -1));
    return best;
}

頑張る

暫定の結果を使う

  • 未稿
int vertex_cover(const Graph& graph) {
    const int n = graph.n;
    function<bool(const Graph&, const vector<int>&)> iscover;
    /* 略 */
    int best = n;

    function<void(int, vector<int>)> dfs = [&](int idx, vector<int> cover) {
        // 選択した頂点の数
        int cnt = 0;
        for (int e : cover) cnt += (e == 1);

        // これ以上選択する頂点を増やすと暫定の最良を超える
        if (best <= cnt) return;

        if (idx == n) {
            // すべての頂点を決めた
            if (iscover(graph, cover)) {
                // 頂点被覆なら更新
                best = min(best, cnt);
            }
        }
        else {
            int r;
            cover[idx] = 0;
            dfs(idx + 1, cover);
            cover[idx] = 1;
            dfs(idx + 1, cover);
        }
    };
    dfs(0, vector<int>(n, -1));
    return best;
}

頂点被覆の条件を使う

  • ある頂点vを選択しなかったとする.
  • vに隣接する頂点は全て選択しなければならない
int vertex_cover(const Graph& graph) {
    const int n = graph.n;
    function<bool(const Graph&, const vector<int>&)> iscover;
    /* 略 */
    int best = n;

    function<void(int, vector<int>)> dfs = [&](int idx, vector<int> cover) {
        // 選択した頂点の数
        int cnt = 0;
        for (int e : cover) cnt += (e == 1);

        // これ以上選択する頂点を増やすと暫定の最良を超える
        if (best <= cnt) return;

        if (idx == n) {
            // すべての頂点を決めた
            if (iscover(graph, cover)) {
                // 頂点被覆なら更新
                best = min(best, cnt);
            }
        }
        else if (cover[idx] != -1) {
            // 今見る頂点が既に定まっているのでスキップ
            dfs(idx + 1, cover);
        }
        else {
            int r;
            // 頂点idxを選択する
            cover[idx] = 1;
            dfs(idx + 1, cover);

            // 頂点idxを選択しない
            cover[idx] = 0;
            for (int ad : graph.vertex_to[idx])
                if (cover[ad] == 0) // 選択しないと決めた頂点に隣接するならば,それば出来ない.
                    return;
                else
                    cover[ad] = 1;
            dfs(idx + 1, cover);
        }
    };
    dfs(0, vector<int>(n, -1));
    return best;
}

次数が0の頂点は選択しない

  • 途中でグラフの次数が増えることは無いので,初期値として組み込んでおく.
int vertex_cover(const Graph& graph) {
    /* 略 */

    vector<int> ini(n, -1);
    for (int j = 0; j < graph.n; ++j) {
        // 次数が0の頂点は選択しない
        if (graph.vertex_to[j].empty())
            ini[j] = 0;
    }
    dfs(0, ini);
    return best;
}

頂点被覆の条件を使う2

  • ある頂点vに隣接する辺がすべて被覆されていたとする
    • 言い換えると,vに隣接する頂点がすべて選択済みになっているとする
  • このとき,頂点vは選択する必要が無い.
int vertex_cover(const Graph& graph) {
    /* 略 */
    function<void(int, vector<int>, int)> dfs = [&](int idx, vector<int> cover, int cnt) {
        /* 略 */
        if (best <= cnt) return;

        if (idx == n) {
            /* 略 */
        }
        else if (cover[idx] != -1) {
            /* 略 */
        }
        else {
            bool unnecessary = true;
            for (int ad : graph.vertex_to[idx])
                if (cover[ad] == 0) {
                    // 選択しないと決めた頂点に隣接するならば,
                    // 「頂点idxを選択しない」は出来ない.頂点idxを選択する.
                    cover[idx] = 1;
                    dfs(idx + 1, cover, cnt + 1);
                    return;
                }
                else
                    unnecessary &= cover[ad] == 1;

            if (unnecessary) {
                // 隣接する辺がすべて被覆されているならば,選択する必要は無い.
                cover[idx] = 0;
                dfs(idx + 1, cover, cnt);
                return;
            }

            // 頂点idxを選択して再帰を続ける.
            cover[idx] = 1;
            dfs(idx + 1, cover, cnt + 1);

            // 頂点idxを選択せず再帰を続ける.
            cover[idx] = 0;
            for (int ad : graph.vertex_to[idx])
                cnt += (cover[ad] != 1), // 選択しない頂点の隣接は
                cover[ad] = 1;           // 必ず選択される
            dfs(idx + 1, cover, cnt);
        }
    };
    /* 略 */
}

ヒューリスティックスの導入

成果物

//
int vertex_cover(const Graph& graph) {
    const int n = graph.n;

    // cover[i] = -1 : 未決定
    //             0 : 選択しない
    //             1 : 選択する

    function<bool(const Graph&, const vector<int>&)> iscover = [](const Graph& graph, const vector<int>& cover) {
        for (int j = 0; j < graph.n; ++j)
            if (cover[j] == 0)
                for (int to : graph.vertex_to[j])
                    if (!cover[to])
                        return false;
        return true;
    };

    int best = n;

    function<void(int, vector<int>, int)> dfs = [&](int idx, vector<int> cover, int cnt) {
        // 選択した頂点の数
        //int cnt = 0;
        //for (int e : cover) cnt += (e == 1);

        // これ以上選択する頂点を増やすと暫定の最良を超える
        if (best <= cnt) return;

        if (idx == n) {
            // すべての頂点を決めた
            if (iscover(graph, cover)) {
                // 頂点被覆なら更新
                best = min(best, cnt);
            }
        }
        else if (cover[idx] != -1) {
            // 今見る頂点が既に定まっているのでスキップ
            dfs(idx + 1, cover, cnt);
        }
        else {
            bool unnecessary = true;
            for (int ad : graph.vertex_to[idx])
                if (cover[ad] == 0) {
                    // 選択しないと決めた頂点に隣接するならば,
                    // 「頂点idxを選択しない」は出来ない.頂点idxを選択する.
                    cover[idx] = 1;
                    dfs(idx + 1, cover, cnt + 1);
                    return;
                }
                else
                    unnecessary &= cover[ad] == 1;

            if (unnecessary) {
                // 隣接する辺がすべて被覆されているならば,選択する必要は無い.
                cover[idx] = 0;
                dfs(idx + 1, cover, cnt);
                return;
            }

            // 頂点idxを選択して再帰を続ける.
            cover[idx] = 1;
            dfs(idx + 1, cover, cnt + 1);

            // 頂点idxを選択せず再帰を続ける.
            cover[idx] = 0;
            for (int ad : graph.vertex_to[idx])
                cnt += (cover[ad] != 1), // 選択しない頂点の隣接は
                cover[ad] = 1;           // 必ず選択される
            dfs(idx + 1, cover, cnt);
        }
    };

    vector<int> ini(n, -1);
    for (int j = 0; j < graph.n; ++j) {
        // 次数が0の頂点は選択しない
        if (graph.vertex_to[j].empty())
            ini[j] = 0;
    }

    dfs(0, ini, 0);
    return best;
}

計算量評価

  • 未稿