这是一个我正在访问的服务器:
- 请求记录(r1,...rn)和字段(f1,...fp) - 您只能请求笛卡尔积(r1,...rp)x(f1,...fp) - 与此类请求相关的成本(时间和金钱)与请求的大小成正比:T((r1,...,rn)x(f1,...,fp)= a + b * n * p。
不失一般性(仅通过规范化),我们可以假设b = 1,因此成本为:
T((r1,...,rn)x(f1,...,fp))= a + n * p 我只需要请求一对子集(r1,f(r1)),...(rk,f(rk)),这个请求来自用户。我的程序充当用户和服务器之间的中间人(外部服务器)。我每天会收到数万个此类请求。
从图形上看,我们可以将其视为n x p稀疏矩阵,其中我想用矩形子矩阵覆盖非零值:
r1 r2 r3 ... rp ------ ___ f1 |x x| |x| f2 |x | --- ------ f3 .. ______ fn |x x| ------
具有以下特点:
- 保持子矩阵数量合理,因为成本是恒定的 - 所有“x”必须位于子矩阵内 - 由于线性成本,覆盖的总面积不应太大
我将为我的问题命名g稀疏系数(所需对数与总可能对数的比率,g = k /(n * p))。我知道系数a。
还有一些明显的观察结果:
- 如果a很小,最好的解决方案是独立请求每个(记录、字段)对,总成本为:
k * (a + 1) = g * n * p * (a + 1)
- 如果a很大,最好的解决方案是请求整个笛卡尔积,总成本为:
a + n * p
- 只要
g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
,第二种解决方案就更好了。 - 当然,笛卡尔积中的顺序并不重要,所以我可以转置矩阵的行和列,使其更容易覆盖,例如:
f1 f2 f3 r1 x x r2 x r3 x x
可以重新排序为
f1 f3 f2 r1 x x r3 x x r2 x
有一个最优解,即请求(f1,f3) x (r1,r3) + (f2) x (r2)
- 尝试所有解并寻找较低成本不是一个选择,因为组合数会爆炸:
对于每个行排列:(n!) 对于每个列排列:(p!) 对于n x p矩阵的每种可能的覆盖方式:(时间未知,但很大...) 计算覆盖成本
因此,我正在寻找一个近似解决方案。我已经有了一种贪心算法,可以在给定矩阵的情况下找到覆盖(它从单位单元格开始,然后将它们合并,如果合并中空单元格的比例低于某个阈值)。
为了让人们有些数值上的概念,我的n在1到1000之间,我的p在1到200之间。覆盖模式真的很“块状”,因为记录按类别分组,所请求的字段相似。不幸的是,我无法访问记录的类别...
问题1:有人有主意、巧妙的简化或有用的论文参考吗?由于我有很多请求,因此我正在寻找一个在平均情况下表现良好的算法(但我不能承受它在某些极端情况下表现非常糟糕,例如当n和p很大,请求实际上相当稀疏时请求整个矩阵)。
< p > < em > 问题2 :事实上,这个问题更加复杂:成本实际上更像是这种形式:a + n * (p^b) + c * n' * p'
,其中b是一个常数 <1(一旦请求了字段的记录,请求其他字段就不会太昂贵),而n' * p' = n * p * (1 - g)
是我不想请求的单元格数量(因为它们是无效的,并且请求无效的内容会增加额外的成本)。我甚至做梦也想不出一个快速的解决方案,但是...有人有想法吗?