福岡でデータ基盤エンジニアしている荒木です!
日々の業務の中でクエリを書いていると、SQLでbit全探索 が書きたいなーと思うことってありますよね?僕は一度もないです。
BigQueryの関数とWith句を使うとbit全探索が意外と簡単に書けたのでご紹介したいと思います。
例題として、価値と重さが設定された20個品物を一定の重さ以下で価値を最大化する問題(いわゆる ナップザック問題)を考えてみたいと思います。
(前提知識として通常のプログラミング言語でbit全探索を理解している方を対象としています = bit全探索についての説明はしません。)
bit.sql
WITH nimotu AS (
-- テストケース
SELECT 0 AS id, 2 AS value, 9 AS weight UNION ALL
SELECT 1 AS id, 5 AS value, 5 AS weight UNION ALL
SELECT 2 AS id, 4 AS value, 1 AS weight UNION ALL
SELECT 3 AS id, 1 AS value, 5 AS weight UNION ALL
SELECT 4 AS id, 3 AS value, 5 AS weight UNION ALL
SELECT 5 AS id, 100 AS value, 20 AS weight UNION ALL
SELECT 6 AS id, 2 AS value, 9 AS weight UNION ALL
SELECT 7 AS id, 5 AS value, 5 AS weight UNION ALL
SELECT 8 AS id, 4 AS value, 1 AS weight UNION ALL
SELECT 9 AS id, 1 AS value, 2 AS weight UNION ALL
SELECT 10 AS id, 3 AS value, 5 AS weight UNION ALL
SELECT 11 AS id, 100 AS value, 20 AS weight UNION ALL
SELECT 12 AS id, 2 AS value, 9 AS weight UNION ALL
SELECT 13 AS id, 5 AS value, 5 AS weight UNION ALL
SELECT 14 AS id, 4 AS value, 1 AS weight UNION ALL
SELECT 15 AS id, 1 AS value, 2 AS weight UNION ALL
SELECT 16 AS id, 3 AS value, 5 AS weight UNION ALL
SELECT 17 AS id, 100 AS value, 20 AS weight UNION ALL
SELECT 18 AS id, 2 AS value, 9 AS weight UNION ALL
SELECT 19 AS id, 5 AS value, 5 AS weight
), solve AS(
SELECT
SUM(
-- bitが0の商品は加算
CASE WHEN bit & (1 << id) = 0
THEN nimotu.value
ELSE 0
END
) AS value,
SUM(
-- bitが0の商品は加算
CASE WHEN bit & (1 << id) = 0
THEN nimotu.weight
ELSE 0
END
) AS weight
-- 商品idと選び方をcross joinして1レコードがある選び方のときのある商品の状態を示すテーブルを作成
FROM
-- 商品idの列挙
UNNEST(GENERATE_ARRAY(0, 19)) AS id
CROSS JOIN
-- bitで選び方を列挙
UNNEST(GENERATE_ARRAY(0, 1<<19)) AS bit
LEFT JOIN
nimotu
ON
id = nimotu.id
GROUP BY
-- 選び方でグループ分けして1レコードがある選び方を示すテーブルに変換
bit
)
SELECT
MAX(value)
FROM
solve
WHERE
-- 重量は50以下の設定にする
weight <= 50
GENERATE_ARRAYで商品idの連番テーブルと選び方のbit列の連番テーブル作ってCROSS JOINします。するとある商品がある選び方のときにの状態を示すテーブルができます。なのでbitでグループ分けして、bit & ( 1 << id )が0の商品を合計すると全ての選び方を全列挙することができました。