在BigQuery中实现寻找覆盖全部PC的最少路由器方案

给定一张包含Site、Router、PC三列的表，每个站点下有多台路由器，每台路由器连接若干PC。需要为每个站点筛选出最少数量的路由器，使得这些路由器的PC集合能覆盖该站点的所有PC。

原始数据 #

with pop as (
select 'X' as site,'AAA' as router, 1 as pc union all
select 'X' as site,'AAA' as router, 2 as pc union all
select 'X' as site,'AAA' as router, 3 as pc union all
select 'X' as site,'AAA' as router, 4 as pc union all
select 'X' as site,'AAA' as router, 5 as pc union all
select 'X' as site,'BBB' as router, 4 as pc union all
select 'X' as site,'BBB' as router, 6 as pc union all
select 'X' as site,'BBB' as router, 7 as pc union all
select 'X' as site,'CCC' as router, 2 as pc union all
select 'X' as site,'CCC' as router, 4 as pc union all
select 'X' as site,'CCC' as router, 7 as pc union all
select 'X' as site,'DDD' as router, 1 as pc union all
select 'X' as site,'DDD' as router, 8 as pc union all
select 'X' as site,'DDD' as router, 9 as pc union all
select 'X' as site,'EEE' as router, 5 as pc union all
select 'X' as site,'EEE' as router, 6 as pc union all
select 'Y' as site,'FFF' as router, 1 as pc union all
select 'Y' as site,'GGG' as router, 2 as pc union all
select 'Y' as site,'HHH' as router, 1 as pc union all
select 'Y' as site,'HHH' as router, 2 as pc union all
select 'Y' as site,'HHH' as router, 3 as pc 
)
select * from pop

解决方案SQL #

WITH pop AS (
  -- 原始数据
  select 'X' as site,'AAA' as router, 1 as pc union all
  select 'X' as site,'AAA' as router, 2 as pc union all
  select 'X' as site,'AAA' as router, 3 as pc union all
  select 'X' as site,'AAA' as router, 4 as pc union all
  select 'X' as site,'AAA' as router, 5 as pc union all
  select 'X' as site,'BBB' as router, 4 as pc union all
  select 'X' as site,'BBB' as router, 6 as pc union all
  select 'X' as site,'BBB' as router, 7 as pc union all
  select 'X' as site,'CCC' as router, 2 as pc union all
  select 'X' as site,'CCC' as router, 4 as pc union all
  select 'X' as site,'CCC' as router, 7 as pc union all
  select 'X' as site,'DDD' as router, 1 as pc union all
  select 'X' as site,'DDD' as router, 8 as pc union all
  select 'X' as site,'DDD' as router, 9 as pc union all
  select 'X' as site,'EEE' as router, 5 as pc union all
  select 'X' as site,'EEE' as router, 6 as pc union all
  select 'Y' as site,'FFF' as router, 1 as pc union all
  select 'Y' as site,'GGG' as router, 2 as pc union all
  select 'Y' as site,'HHH' as router, 1 as pc union all
  select 'Y' as site,'HHH' as router, 2 as pc union all
  select 'Y' as site,'HHH' as router, 3 as pc 
),
-- 按站点聚合路由器PC集合、站点总PC集合
site_router_pcs AS (
  SELECT
    site,
    router,
    ARRAY_AGG(DISTINCT pc) AS router_pcs,
    ARRAY_AGG(DISTINCT pc) OVER (PARTITION BY site) AS total_pcs
  FROM pop
  GROUP BY site, router
),
-- 递归贪心选择路由器：每次选覆盖最多未覆盖PC的路由器
recursive_selection AS (
  SELECT
    site,
    [router] AS selected_routers,
    ARRAY(SELECT DISTINCT pc FROM UNNEST(router_pcs)) AS covered_pcs,
    total_pcs
  FROM site_router_pcs
  -- 初始选每个站点覆盖PC最多的路由器
  QUALIFY ROW_NUMBER() OVER (PARTITION BY site ORDER BY ARRAY_LENGTH(router_pcs) DESC) = 1

  UNION ALL

  SELECT
    rs.site,
    ARRAY_CONCAT(rs.selected_routers, [srp.router]) AS selected_routers,
    ARRAY(SELECT DISTINCT pc FROM UNNEST(ARRAY_CONCAT(rs.covered_pcs, srp.router_pcs))) AS covered_pcs,
    rs.total_pcs
  FROM recursive_selection rs
  JOIN site_router_pcs srp
    ON rs.site = srp.site
    AND srp.router NOT IN UNNEST(rs.selected_routers)
  -- 跳过已覆盖全部PC的分支
  WHERE ARRAY_LENGTH(rs.covered_pcs) < ARRAY_LENGTH(rs.total_pcs)
  -- 选当前能覆盖最多剩余PC的路由器
  QUALIFY ROW_NUMBER() OVER (PARTITION BY rs.site ORDER BY ARRAY_LENGTH(ARRAY(SELECT pc FROM UNNEST(srp.router_pcs) WHERE pc NOT IN UNNEST(rs.covered_pcs))) DESC) = 1
),
-- 筛选每个站点最少路由器的全覆盖集合
final_results AS (
  SELECT
    site,
    selected_routers,
    ARRAY_LENGTH(selected_routers) AS router_count
  FROM recursive_selection
  WHERE ARRAY_LENGTH(covered_pcs) = ARRAY_LENGTH(total_pcs)
  QUALIFY ROW_NUMBER() OVER (PARTITION BY site ORDER BY router_count ASC) = 1
)
SELECT site, selected_routers FROM final_results

执行结果 #

思路说明 #

1. 数据预处理：site_router_pcs 按站点和路由器分组，生成每个路由器的PC列表、站点的全部PC列表。
2. 贪心递归选择：从每个站点覆盖PC最多的路由器开始，每次迭代选择能覆盖最多未覆盖PC的路由器，直到覆盖所有PC。
3. 最优结果筛选：从所有完成全覆盖的路由器集合中，选出每个站点路由器数量最少的集合。

内容的提问来源于stack exchange，提问作者Eithan