Zenn
🦁

【C#アルゴリズム】全探索_ビット探索

2024/11/27に公開
C#
アルゴリズム
全探索
tech

はじめに

paiza　でビット探索にまつわる問題が出てきたのでビット探索についてまとめました。

ビット探索とは

ビット探索は、ビット演算を利用して部分集合や特定の条件に一致する組み合わせを全探索する手法です。特に、2進数で数値を表現した際の各ビットが「その要素を選ぶかどうか」を表す方法として用いられます。

基本的な考え方

  1. 2進数と部分集合:

    • 例えば、配列 {a, b, c} の部分集合を考える場合、2進数の各桁を要素の選択状態に対応させます。
      • 0: 選ばない
      • 1: 選ぶ
    • 配列の長さが n の場合、全ての部分集合の数は 2^n 通りになります。
      • n = 3 の場合の例:
        • 000: 空集合 {}
        • 001: 要素 c を選ぶ {'c'}
        • 010: 要素 b を選ぶ {'b'}
        • 111: 全部選ぶ {a, b, c}

  2. ビット演算での全探索:

    • 数値 0 から 2^n - 1 までをカウントし、それを2進数表記で解釈して部分集合を生成します。

ビット探索の実装例 (C#)

ビット探索の具体例: 和が目標値に等しい部分集合を探す

ここでは、ビット探索を使って「配列の要素の一部を選んだとき、その和が目標値 S に等しい部分集合を探す」という問題を解きます。

例題

整数の配列 {3, 1, 4, 2} があります。この配列からいくつかの要素を選び、その和が目標値 S = 6 になる部分集合をすべて列挙してください。

解法の説明

  1. 配列を用意:
    配列の要素 n 個に対して部分集合の数は 2^n 通りです。

    • 配列 {3, 1, 4, 2} の場合、4要素なので部分集合は 2^4 = 16 通り。

  2. ビット探索を使用:

    • それぞれの部分集合を、ビットの0・1で選択状態を表します。
      • 例: 1010 → 1番目と3番目の要素を選ぶ {3, 4}。

  3. 条件をチェック:

    • ビット探索で生成した各部分集合について、その和を計算し、目標値 S と一致するか確認します。

C#のコード 

using System;

class Program
{
    static void Main()
    {
        // 配列と目標値
        int[] numbers = { 3, 1, 4, 2 };
        int targetSum = 6;

        // 配列の長さ
        int n = numbers.Length;

        // 全探索 (2^n 通り)
        for (int bit = 0; bit < (1 << n); bit++)
        {
            int sum = 0;
            Console.Write("{ ");
            for (int i = 0; i < n; i++)
            {
                // ビットが立っている場合、その要素を選ぶ
                if ((bit & (1 << i)) != 0)
                {
                    Console.Write(numbers[i] + " ");
                    sum += numbers[i];
                }
            }

            // 和が目標値と一致する場合
            if (sum == targetSum)
            {
                Console.WriteLine("YES");
            }
        }
    }
}

結果

目標値 S = 6 を満たす部分集合は:

  1. {3, 1, 2}
  2. {4, 2}

ビット探索のポイント

  1. 計算量:

    • 配列の長さが n の場合、全探索にかかる計算量は O(2^n) です。長さが増えると急激に計算量が増加するため、小さめの n に向いています。

  2. ビット演算の使い方:

    • (1 << i): i ビット目が立っている値を生成。
    • (bit & (1 << i)): i ビット目が立っているかどうかを判定。

  3. 活用例:

    • 部分集合の列挙
    • 特定条件を満たす組み合わせの探索
    • ナップサック問題、旅行セールスマン問題などの簡易解法（ナップサック問題は動的計画法を用いるほうが良い）

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion