代码之家 › 专栏 › 技术社区 › LeMiz

用仿射代价优化笛卡尔请求

cost-based-optimizer combinatorics optimization language-agnostic algorithm

LeMiz · 技术社区 · 16 年前

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

我正在访问的服务器工作方式如下:

对记录(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)

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

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之间,p在1到200之间。覆盖模式实际上是“块状的”,因为记录是以类的形式出现的,对于这些类,请求的字段是相似的。很遗憾,我无法访问记录的类…

问题1 :有人有什么想法,有没有巧妙的简化,或者有没有一篇论文的参考资料?因为我有很多请求,一个运行良好的算法 平均而言 是我正在寻找的(但在某些极端情况下,我不能承受工作非常差的代价,例如,当n和p很大时,请求整个矩阵,而请求确实非常稀疏)。

问题2 :事实上,问题更加复杂:成本实际上更像形式: a + n * (p^b) + c * n' * p' ,其中b是一个常量<1(一旦一个记录被请求一个字段,请求其他字段的成本就不会太高),并且 n' * p' = n * p * (1 - g) 是我不想请求的单元格数(因为这些单元格无效,请求无效的内容需要额外的成本)。我甚至梦想不到能迅速解决这个问题,但是…有什么想法吗?

6 回复 | 直到 16 年前

Daniel Brückner 16 年前

选择子矩阵以覆盖请求的值是 set covering problem 因此NP完全。你的问题又增加了一个已经很难解决的问题,那就是套的成本不同。

允许对行和列进行排列并不是什么大问题,因为您可以只考虑断开连接的子矩阵。第1行、第4列到第7列和第5行、第4列和第2列是有效的集合,因为您只需交换第2行和第5行并获得连接的子矩阵第1行、第4列到第2行、第7列。当然,这会增加一些约束——并非所有集合在所有排列下都有效——但我不认为这是最大的问题。

维基百科的文章给出了一个不可估计的结果,即该问题在多项式时间内不能比用一个因子更好地解决。 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* search .

Artelius 16 年前

我确信有一个很好的算法可以解决这个问题,但我有自己的直觉:

抛开一些矩形的方法:
- 根据以下公式确定“大致最佳”矩形大小: 一 .
- 把这些矩形(可能是随机的)放在你需要的点上,直到所有点都被覆盖。
- 现在取下每个矩形并尽可能地缩小它,而不会“丢失”任何数据点。
- 找到彼此靠近的矩形,然后决定组合它们是否比将它们分开便宜。
成长
- 从它自己的1x1矩形中的每个点开始。
- 在n行/列内定位所有矩形(其中n可以基于一 );看看是否可以将它们组合成一个矩形而不需要成本(或负成本:d)。
- 重复。
收缩
- 从一个覆盖所有点的大矩形开始。
- 寻找一个与大矩形共享一对边,但包含很少点的子矩形。
- 把它从一个大的切下来,形成两个小的矩形。
- 重复。
方庭
- 将平面分成4个矩形。对于其中的每一个,通过进一步递归,或者仅仅包含整个矩形,看看您是否获得了更好的成本。
- 现在,拿着你的矩形,看看你能不能把它们合并成一个小的或免费的。\

也: 牢记有时候最好有两个重叠矩形多于一个大矩形,它是它们的超集。例如,当两个矩形仅在一个角重叠时。

Artelius 16 年前

好吧,我对这个问题的理解已经改变了。新理念:

将每一行存储为长位字符串。以及成对的位串,试图找到最大化1位的对。将这些配对扩大到更大的组中(分类并尝试将真正大的组相互匹配)。然后构造一个请求,该请求将命中最大的组,然后忽略所有这些位。重复,直到一切完成。有时可以从行切换到列。
查找其中包含零个或少个点的所有行/列。”删除“它们。现在,您将看到将它们排除在外的请求所涵盖的内容。现在,也许可以应用其他技术之一,然后处理被忽略的行/列。另一种思考方法是:先处理更密集的点,然后再转移到更稀疏的点上。

ire_and_curses 16 年前

由于您的值是稀疏的,可能是许多用户要求相似的值吗?在应用程序中缓存是一个选项吗?请求可以通过(x,y)位置的函数散列进行索引,这样您就可以轻松地识别位于网格正确区域内的缓存集。例如,将缓存集存储在树中可以让您很快找到覆盖请求范围的最小缓存子集。然后可以对子集进行线性查找,这是很小的。

Jonathan Graehl 16 年前

我将考虑用户请求中提到的n个记录(行)和p字段(cols),设置为p维空间(0,1^p)中的n个点,i坐标为1,如果它有x,并且 identify a hierarchy of clusters ,其中最粗的集群位于根目录,包括所有X。对于集群层次结构中的每个节点,考虑覆盖所有所需列(这是行(任何子节点)x列(任何子节点))的产品。然后,自下而上决定是合并儿童覆盖物(支付整个覆盖物的费用),还是作为单独的请求保留它们。(覆盖层不是连续的列,而是所需的列;也就是说,考虑一个位向量)

我同意Artelius的观点,重叠的产品请求可能会更便宜;我的分层方法需要改进以将其纳入其中。

LeMiz 16 年前

我已经做了一些工作,这里有一个明显的O(n^3)贪婪的对称破坏算法(记录和字段分别处理),类似于python的伪代码。

这个想法很简单:我们首先尝试每个记录一个请求,然后进行最有价值的合并,直到没有任何东西值得合并为止。这个算法有明显的缺点,即它不允许重叠的请求,但我希望它在实际情况下(使用+ n * (p^b) + c * n * p * (1 - g) 成本函数):

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

这是O(N3*P),因为:

初始化之后,我们从 n 请求
这个 while 循环在每次迭代时只从池中删除一个请求。
内部 for 循环迭代( ni^2 - ni )/两个不同的请求对,在最坏的情况下,ni从n变为1(当我们将所有内容合并为一个大请求时)。
1. 有人能帮我指出算法中非常糟糕的情况吗?用这个听起来合理吗?
2. 它是O(n^3),这对于大输入来说太昂贵了。有优化的想法吗?

事先谢谢!