优化笛卡尔的请求仿射费用

StackOverflow https://stackoverflow.com/questions/1403933

题

我有一个优化成本的请求，我不知道如何如果有的文献。这是一个有点难解释，因此我提前道歉的长度的问题。

有一个服务器我访问，工作方式：

  • 请求在记录(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)), 一个请求来自用户。我的程序作为一个中间人和用户之间的服务器(这是外部)。我有一个很大的要求，这样，在(数以万计的一天)。

图形的方式，我们可以把它作为一个x n p稀疏的矩阵，为此，我想盖的零值矩子矩阵:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

具有：

  • 数子矩阵正在保持合理的，因为不断的成本
  • 所有的'x'必须躺在子矩阵
  • 总复盖的区域不能太大，因为直线的费用

我将名g的稀疏系数是我的问题(数目的需要对超过总的可能对， g = k / (n * p).我知道系数 a.

有一些明显的意见：

  • 如果一个小，最好的解决办法是要求每一(记录，段)对独立，总成本： k * (a + 1) = g * n * p * (a + 1)
  • 如果是大型的最好的解决办法是要求整个笛卡尔的产品，而总的费用是： 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) 是细胞的数量我不想请求(因为它们是无效的，并且有是一个额外的费用要求的无效)。我甚至不能梦想的迅速解决这个问题，但是仍然...一个想法的人吗？

有帮助吗？

解决方案

选择子矩阵，以复盖所要求的价值观是一个形式 设定复盖的问题 因此NP完成。你的问题增加了本已经困难的问题，这些费用的组有所不同。

你允许permutate的行列是不是这样的一个大问题，因为你可以考虑子矩阵连接断开.行之一，列四到七和行五、列四个两七是一种有效设置，因为你可以交换行两个并行五和获得子矩阵连接行之一，列四个行两、列七个。当然，这将增加某些限制，并不是所有设置都是有效的下所有排列-但我不认为这是最大的问题。

维基百科文提供的inapproximability结果，这个问题不能解决在时间多项式更好地然后用一个因素 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*搜索.

其他提示

我敢肯定有一个很好的算法为这个外面的某个地方，但这里是我自己的直觉的想法：

  1. 折腾了一些长方形的方法：

    • 确定一个"大约最佳的"矩形大小的基础上 一个.
    • 把这些长方形(也许是随机)你需要点，直至所有各点。
    • 现在每个矩形，并缩小它尽可能多的没有"失去"任何数据点。
    • 找到矩形彼此接近并决定是否将它们结合起来将更加便宜于让他们独立的。

  2. 成长

    • 开始了与各点在其自己的1×1矩形。
    • 找到所有形内n行/列(其中，n可能基于 一个);看看你是否可以将它们合并为一个矩形没有成本(或负成本：D)。
    • 重复。

  3. 收缩

    • 开始有一个很大的矩形，涵盖所有要点。
    • 寻找一个子矩形其股份的一对双方有一个大的，但含有非常几点。
    • 削减它的大的一个，生产两个较小的矩形。
    • 重复。

  4. 四

    • 除飞机进入4矩形。对于每个这些，看看你是否获得更好的成本通过递归访问进一步，或只包括整个矩形。
    • 现在把你的矩形，看看你是否可以合并的任何他们很少/不需任何费用。\

也： 请记住 有时它会是最好有两个 重叠 矩形比一个大型的矩形，这是一个超集他们。E.g。这种情况下，当两个矩形只是重叠在一个角落。

Ok，我的理解的问题已经改变。新的想法：

  • 储存的每一行作为一个长点-串。和对位串在一起，试图找到对于最大数量的1位。成长这些对进入较大的群体(排序，并尝试相匹配的很大部分与每一个其他)。然后修建一个请求，将打击最大的群体，然后忘记关于所有这些位。重复，直到所做的一切工作。也许开关从行列的时候。

  • 看看所有行/列为零或几点。"删除"它们是暂时的。现在你正在看什么会所涵盖的请求，使他们了。现在也许适用其他技术，并处理被忽略的行/cols之后。另一种方式思考这是：处理密集的第一点，然后移动到稀疏的人。

因为你的价值观是稀疏，它可能是许多用户要求提供类似的价值观？是缓存应用程序内的一个选择吗？该请求可能是索引的通过散列函数(x,y)的位置，这样就可以很容易地识别缓存的集落在正确的领域。储存的缓存的集在一棵树，例如，将允许你找到的最低缓存的子集，涵盖所请求的范围非常迅速。你可以再做一个的线查找关于该子集，这是很小的。

我会考虑的n记录(行)和p领域(cols)中提到的用户要求设置为n点在p-维空间({0,1}^p)与第i个坐标是1森林论它有一个X， 确定一个层次结构的集群,有最粗糙的集群的根源，包括所有的X。每个节点在集群层次结构，考虑产品，涵盖所有需要的列(这是可行的(任何子节点)x列的(任何子节点)).然后，决定从下往上是否合并的儿童的复盖物(支付全复盖)，或者保留它们作为单独的请求。(复盖不是连续列，但确切的需要；即认为一位矢量)

我同意Artelius重叠产品的请求可能是更便宜;我的分层做法将需要改善，以纳入。

我工作了一点，这是一个显而易见，O(n^3)贪婪，打破对称算法(记录和田地都是分开处理)在蟒蛇喜欢伪码。

这个想法是微不足道的：我们开始尝试一请求每个记录，我们做的最有价值的合并直没有得到合并。这个算法具有明显的缺点，即它不允许重叠的申请，但我期望它的工作相当良好，在现实生活情况(a+ 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)/2的不同对请求，与ni从n一个在最糟糕的情况下(当我们合并的一切成一个大的请求)。

    1. 有人可以帮助我指的非常糟糕的情况下的算法。它不会听reasonnable使用这个吗？
    2. 这是O(n^3)这种方法成本太高对大型的投入。任何想法，以优化它?

在此先感谢！

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top