算法 一道算法题,大家讨论下。

ryan · 2013年09月12日 · 最后由 goinaction 回复于 2013年09月12日 · 3939 次阅读

更新 2 唉,今天对需求重新分析后发现,极大线性无关不可用。因为最终要的店铺并集,交集不需要,无法用减法来处理矩阵。只好另寻他路。现在重新定义问题:

现有 n 个向量,a1--an,向量的长度都为 m,向量的元素由 0 和 1 构成。 a1||a2||a3||....||an=[1,1,1,1,1,1.....1] ,求一组向量 k,以满足, size=count(k) 最小,且 k1||k2||......||k(size)=[1,1,1,1,1,.....,1] 。 有没有比较好的算法,而不是死算循环 C(n)(k) 次来得出结果呢?

#更新 还是把实际的需求场景也写下来吧。 现在有个爬虫项目是对淘宝上的店铺信息的进行收集。由于每个店铺都会在自己的 主营 列表里面填上自己的主营产品列表,什么女装啊,男装啊之类的。

假设现在已经完成了数据收集,并且已经把所有的 主营 列表中的关键字和对应的搜索结果进行了分类,比如女装的搜索结果有 10w 家店铺,男装的搜索结果有 20w 家店铺。同时,这俩关键字的搜索结果也是有重复的店铺的。

所以,现在要从这些关键字中找出一组组合,能够把将现有所有的搜索结果全部囊括进去,而组合中的关键字又尽量的少,但是对这组关键字的搜索结果重复度不做要求。求出这组关键字组合。

有这么 n 组数据(x1,y1),(x2,y2).....(xn,yn),其中 y1,y2,y3...yn 都是一个集合,y1=[z1,z2,z3.....],y2=[z3,z4,z5.....],y3=[z7,z1,z9......]........,可见,每个 y 集合都有重复数据和不重复数据,且,distinct(y1+y2+y3+....+yn)=U,也就是,y 的所有不重复数据之和为 U。

现在,要找出一组 k,,k=1,2,3...n,以保证这一组 k 所有对应的 x 集合,比如(x3,x10,x55),则k=3,10,55,其 yk 的不重复之和,即:distinct(R=y3+y10+y55),尽可能的等于 U 或者接近 U,比如,比例是 95% 或者 90%:distinct(y3+y20+y55)==95%*U

现在我想出两套算法: --1.利用机器学习的 k-means 做聚类 --2.利用加权无向图计算每个 x 对应 y 的差异来归类

然后我同学直接说: 动态规划。类似于矩阵连乘的最优组合。

再次讨论后的结果: 线性代数中的矩阵变换,求矩阵的秩。然后选取一组组合。

三种算法都尚未实现。只是这么想着,觉得都可用。大家有没有更好的思路。

如果题目描述不清,请指出,我马上做补充~~

奥 膜拜, 看不懂。。。

#1 楼 @tumayun 然后经过我和同学讨论,其实线性代数就可以解决了。用矩阵的线性变换。。我擦。

#2 楼 @Ryan 把解也写写吧..

怎么感觉这里面没 Xn 集合啥事呢,就是出来混淆下视线

#4 楼 @goinaction 就是求一组 xn 啦。

#3 楼 @blacktulip 嗯,明天验证下算法可行性就更新下。

#5 楼 @Ryan 我意思是就求一组 k,使 distinct(y3+y20+y55)==95%*U,好像也不妨碍理解。 不过这都是细枝末节的事了,lz 还是讲讲思路吧😄

#7 楼 @goinaction 暂时的想法是,建立一个矩阵,假如总店铺数 U=1w,总关键字数量为 1k,那么就可以建立一个 1w*1k 的矩阵,然后每一行就代表了一个关键字能够搜索出的店铺,用 0,1 表示的话,可以得到一个 0,1 矩阵,然后总这个矩阵当中,找出一组关键字,也就是一组行,令这一组行对应的值彼此的并集=U 就可以了。计算量略大,不过至少已经证明了,存在有限个组合 xk,囊括了所有的 U,而不在是 95%U 了。

极大线性无关组

#9 楼 @steven_yue 就是这个。我朋友也这么说,一语惊醒梦中人。。

大概了解了,不过感觉现在只是提出了一个数据结构,找有限个 Xk 组合的算法还没着落啊

#11 楼 @goinaction 9 楼其实已经给出来了啊。极大线性无关组啊。

#12 楼 @Ryan 刚刚去搜索看了一下,发现以前还经常做这种题呢,都忘得差不多了😓

#13 楼 @goinaction +1。典型的理论实际结合。

#14 楼 @Ryan 既学了新东西,又温习了老知识,不错😄

需要 登录 后方可回复, 如果你还没有账号请 注册新账号