[未完待续] PostgreSQL NP完全问题求近似解 例子, 最低成本集合

背景

1、如何用最少的商家覆盖最多的用户（用户最终要求去重）？

比如总共有1亿用户，有100万家店铺，每个店铺有对应的用户群体。如何选择最少的商家，得到最大的用户群体。

2、如何用最少的商家覆盖最大的消费能力群体（消费者最终要求去重）？

3、如何圈定最少的明星，获得最多的粉丝（粉丝集计算最终要求去重）？

比如每个明星都有一些粉丝，他们之间可能有重叠的粉丝。如何选择最少的明星，可以拿到最多的粉丝。（比如你要进行总统选举，想拉票，怎么办？也许找明星代言是不错的选择，那就涉及NP完全问题了）

以上三个问题，都是NP完全问题。（可参考《图解算法》这本书。）

使用PostgreSQL 数组存储全量用户ID，使用数组存储每个商家对应的用户集。

解决这个NP完全问题，怎么做呢？

每次选择与剩余用户集相交最多的。

循环。

例子：

create table tbl(  
  tmall_id int,   -- 商铺ID  
  uid int8[]      -- 店铺会员、用户等  
);  
  
create table users(  
  uid int8[]   -- 全体用户集合  
);  
  
create table tmp_tbl(  
  tmall_id int,  -- 被选出的tmall_id  
  uid int8[]     -- 被选出的tmall_id.uid  
);  
  
select tmall_id,uid from tbl   
  where tmall_id not in (select tmall_id from tmp_tbl)  -- 过滤已选店铺  
  order by uid <-> users.uid - array_agg(tmp_tbl.uid)   -- 过滤已选店铺的用户群体，求重叠度最高的  
  limit 1;  
  
将tmall_id,uid结果放入tmp_tbl，循环。  

以上order by可以用到smlar插件，从索引中快速求最高重叠度的。

其他:

因为可能没有一个全集（即所有商家的用户的集合，小于总的用户数），或者要覆盖全部用户，需要的计算量过大，所以可以设置截止点，例如覆盖到n%用户时，就结束计算。

小结

参考

https://www.postgresql.org/docs/devel/static/locking-indexes.html

digoal’s 大量PostgreSQL文章入口