优化具有仿射成本的笛卡尔请求

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）），这个请求来自用户。我的程序充当用户和服务器之间的中间人（外部服务器）。我每天会收到数万个此类请求。

从图形上看，我们可以将其视为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)是我不想请求的单元格数量（因为它们是无效的，并且请求无效的内容会增加额外的成本）。我甚至做梦也想不出一个快速的解决方案，但是...有人有想法吗？

- LeMiz

---

你有一个告诉你哪些（行，列）是免费的空位置的Oracle吗？ - Jonathan Graehl

你可以明确命名行和字段集，即不必在固定坐标系中指定连续的矩形（特定行和列置换）吗？ - Jonathan Graehl

关于我的第一个问题，答案是肯定的，如果我正确理解了“来自用户的请求”这一部分。 - Jonathan Graehl

对于你的第二个问题，我的回答也是肯定的。如果有一种行和列的排列方式可以使铺路更加紧密，那么通常情况下这是更好的选择（我没有理解你关于Artelius的评论，抱歉。我的限制是在行和列的排列置换上连续矩形）。 - LeMiz

Answer 1

选择子矩阵以覆盖请求的值是集合覆盖问题的一种形式，因此是NP完全问题。你的问题增加了成本不同的集合，已经是一个难解的问题。

允许排列行和列并不是一个大问题，因为可以考虑到不连通的子矩阵。第一行，第四到七列和第五行，第四到七列构成了一个有效的集合，因为可以只交换第二行和第五行，得到连接的子矩阵，即第一行，第四到第二行，第七列。当然，这会增加一些约束条件-并非所有集合在所有排列下都是有效的-但我认为这不是最大的问题。

维基百科文章给出了无法在多项式时间内用比 0.5 * log2(n)更好的因子解决该问题的近似结果，其中n是集合的数量。在你的情况下，2^(n * p)是集合数的（相当悲观的）上限，并且表明除了N = NP并忽略不同的成本外，你只能在多项式时间内找到高达0.5 * n * p的因子解（）。

一个忽略行和列排列的集合数量乐观下限为0.5 * n^2 * p^2，可得到更好的因子log2(n) + log2(p) - 0.5。因此，在最坏情况下n = 1000和p = 200，在乐观情况下，你只能期望找到一个解决方案的因子大约为17，在悲观情况下，该因子可达100,000（仍然忽略不同的成本）。

因此，你唯一能做的就是使用启发式算法（维基百科文章提到了一种几乎最优贪婪算法），并接受有些情况下算法表现不佳。或者你可以采取另一种方式，使用优化算法并尝试通过更多时间来寻找好的解决方案。在这种情况下，我建议尝试使用A*搜索。

- Daniel Brückner

---

感谢回复。我很清楚这个问题是NP难的，但我正在寻找一个在实践中能够很好解决的方案。此外，在仔细研究后，我认为集合覆盖公式并不是微不足道的，因为1）成本函数非常特殊2）约束条件也是如此。是时候开始悬赏了！ - LeMiz

Answer 2

我相信这方面肯定有一个非常好的算法，但是这里是我的直觉想法：

1. 矩形投掷法：

   • 根据a确定“大致最优”的矩形大小。
   • 将这些矩形（可能是随机的）放在所需的点上，直到所有点都被覆盖。
   • 现在尽可能缩小每个矩形，而不会“丢失”任何数据点。
   • 找到彼此靠近的矩形，并决定合并它们是否比保持分开更便宜。

2. 增长

   • 从每个点在自己的1x1矩形中开始。
   • 查找n行/列内的所有矩形（其中n可以基于a），看看是否可以免费（或负成本:D）将它们合并为一个矩形。
   • 重复。

3. 缩小

   • 从覆盖所有点的一个大矩形开始。
   • 查找与大矩形共享一对边但包含非常少点的子矩形。
   • 将其从大矩形中切出，产生两个较小的矩形。
   • 重复。

4. 四叉树

   • 将平面分成4个矩形。对于每个矩形，看看是否通过进一步递归或仅包含整个矩形可以获得更好的成本。
   • 现在取出你的矩形，看看是否可以以很少或没有成本合并它们。

另外请注意：有时候两个重叠的矩形比一个超级集合矩形更好。例如，当两个矩形仅在一个角落处重叠的情况。

- Artelius

---

你不仅限于矩形。 - Jonathan Graehl

@wrang-wrang：是的，我是。 @Artelius，是的，这是真的，可能有重叠的矩形比严格不重叠的更好。我目前正在测试您“Grow”解决方案的修改版本。我从1x1矩形开始，然后合并两个成本较低（稀疏性方面）的矩形并重复此过程。它给出了一个聚类的线性列表，在该列表中我选择最小成本。但真正的问题不在于此，而在于我可以对行和列进行的转置，这就是组合爆炸的原因（n！* p！，不考虑对称性）。 - LeMiz

啊，所以 r1，...，rn 不必连续吗？我想我的头要爆炸了。 - Artelius

Answer 3

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

• 将每一行存储为一个长的位串。将两个位串进行AND运算，尝试找到最大化1位数的对。将这些对扩展成更大的组（排序并尝试将真正大的组彼此匹配）。然后构造一个请求，以命中最大的组，然后忘记所有这些位。重复直到完成所有操作。有时可以从行切换到列。

• 查找所有具有零或少量点的行/列。暂时“删除”它们。现在你正在寻找那些被排除在外的请求所覆盖的内容。现在也许可以应用其他技术，并在之后处理被忽略的行/列。另一种思考方式是：先处理密集点，然后再处理稀疏点。

- Artelius

Answer 4

我会把用户请求中提到的n行p列的n条记录和p个字段视为p维空间中的n个点（{0,1}^p），其中第i个坐标为1，如果它有一个X，并使用识别出一组集群的层次结构，根节点包括所有的X。对于聚类层次结构中的每个节点，请考虑覆盖所需的所有列的乘积（这是行（任何子节点）×列（任何子节点））。然后，从下往上决定是否合并子覆盖范围（支付整个覆盖范围的费用），或将它们保留为单独的请求。（覆盖范围不是连续的列，而是仅需要的列；即将其视为位向量）

我同意Artelius的看法，重叠的产品请求可能更便宜；我的分层方法需要改进以纳入这一点。

- Jonathan Graehl

Answer 5

由于您的值是稀疏的，可能有许多用户正在请求类似的值。在您的应用程序中使用缓存是一个选择吗？请求可以通过对（x，y）位置的哈希函数进行索引，这样您就可以轻松地识别出落在正确网格区域内的缓存集合。例如，将缓存集合存储在树中将允许您非常快速地找到覆盖请求范围的最小缓存子集。然后，您可以对该子集进行线性查找，因为它很小。

- ire_and_curses

---

你好，我们已经缓存了结果。真正的问题是我们不知道如何使请求过期。因此，对于业务关键目的，请求系统可以选择绕过某些值的缓存（这实际上是请求稀疏性的原因之一）。 - LeMiz

Answer 6

我已经在这方面做了一些工作，这里是一个明显的、O(n^3)贪心、对称性破坏算法（记录和字段分别处理）的Python伪代码。

思路很简单：我们从每个记录尝试一个请求开始，然后进行最有价值的合并，直到没有值得合并的东西为止。这个算法的明显缺点是它不允许重叠的请求，但我希望它在实际情况下能够很好地工作（使用a + n * (p^b) + c * n * p * (1 - g)成本函数）：

# 给定
# 一个成本请求函数 -> 正实数
# 一个合并函数，它接受两个集对（f1，r1）和（f2，r2）
# 并返回（（f1 U f2），（r1 U r2））
# 用每个记录的请求初始化
requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]
finished = False

while not finished: # 可能有所收获
    maximum_gain = 0
    finished = True
    this_step_merge = empty
# 循环所有请求对
    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 maximum_gain > 0:
        # 所以更新请求列表...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ...我们还没有完成
        insert merged_request into requests
        finished = False

output requests

这是O(n3 * p)，因为：

• 初始化后，我们从n个请求开始
• while循环在每次迭代中从池中精确地删除一个请求。

• for循环在(ni^2 - ni) / 2个不同的请求对上进行迭代，其中ni在最坏情况下从n到1（当我们将所有内容合并为一个大请求时）。

  1. 有人能帮我指出算法的非常糟糕的情况吗？使用这个算法听起来合理吗？
  2. 它是O(n^3)，对于大输入来说成本太高了。有什么优化的想法吗？

提前感谢！

- LeMiz