以仿射成本优化笛卡尔请求

Question

我有一个成本优化请求,我不知道如何有文献.这有点难以解释,所以我提前为问题的长度道歉.

我正在访问的服务器以这种方式工作:

• 对记录(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)),一个来自用户的请求.我的程序充当用户和服务器(外部)之间的中间人.我有很多这样的要求(每天数万).

在图形上,我们可以将其视为一个nxp稀疏矩阵,我想用矩形子矩阵覆盖非零值:

   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)

• 尝试所有解决方案并寻找更低的成本不是一种选择,因为组合学爆炸:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

所以我正在寻找一个近似的解决方案.我已经有了某种贪婪算法,它找到了给定矩阵的覆盖(它以单元格开始,如果合并中空单元格的比例低于某个阈值,则合并它们).

为了记住一些数字,我的n介于1到1000之间,而我的介于1到200之间.覆盖模式实际上是"块状的",因为记录来自于所要求的字段类似的类.不幸的是我无法访问记录类......

问题1:有人有想法,聪明的简化,还是对可能有用的论文的参考？由于我有很多请求,平均运行良好的算法是我正在寻找的(但我无法承受它在某些极端情况下工作得很差,例如在n和p很大时请求整个矩阵,请求确实非常稀少).

问题2:实际上,问题更复杂:实际上成本更像是形式:a + n * (p^b) + c * n' * p'其中b是常数<1(一旦记录被要求一个字段,要求其他字段的成本不会太高)字段)并且n' * p' = n * p * (1 - g)是我不想请求的单元格数(因为它们无效,并且在请求无效事物时需要额外的费用).我甚至不能梦想快速解决这个问题,但仍然......任何人的想法？

Answer 1

选择子矩阵以覆盖所请求的值是集合覆盖问题的一种形式,因此NP完成.您的问题增加了这个已经很难解决的问题,即集合的成本不同.

您允许排列行和列不是一个大问题,因为您可以只考虑断开连接的子矩阵.第一行,第四列到第七行,第五列,第四列,第二列是有效集,因为您可以只交换第二行和第五行并获得连接的子矩阵行一,第四列到第二行,第七列.当然这会增加一些限制 - 并非所有集合在所有排列下都是有效的 - 但我不认为这是最大的问题.

维基百科的文章给出了不可近似性的结果,即在多项式时间内不能更好地解决问题,0.5 * log2(n)其中因子n是集合的数量.在你的情况下,2^(n * p)对于集合和收益的数量是一个(非常悲观的)上限,你只能0.5 * n * p在多项式时间内找到一个解决方案(除了N = NP并忽略不同的成本).

忽略行和列排列的集合数的乐观下界正在0.5 * n^2 * p^2产生更好的因子log2(n) + log2(p) - 0.5.其结果是,你只能期望找到在你的最坏情况下的解决方案n = 1000和p = 200最高的一个因素约17在乐观的情况下,和多达约一个因素100.000在悲观的情况下(仍忽略了不同的费用).

因此,您可以做的最好的事情是使用启发式算法(维基百科文章提到几乎最优的贪婪算法)并接受算法执行(非常)坏的情况.或者你走另一条路并使用优化算法,并尝试找到一个好的解决方案,使用更多的时间.在这种情况下,我建议尝试使用A*搜索.