9

我有一个成本优化请求，我不知道是否有相关文献。这有点难以解释，所以我提前为问题的长度道歉。

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

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

  • 我只需要请求 pair 的一个子集(r1, f(r1)), ... (rk, f(rk))，一个来自用户的请求。我的程序充当用户和服务器（外部）之间的中间人。我有很多这样的请求（每天数万个）。

从图形上看，我们可以将其视为一个 nxp 稀疏矩阵，为此我想用一个矩形子矩阵覆盖非零值：

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

有：

  • 由于成本不变，子矩阵的数量保持合理
  • 所有的 'x' 必须位于子矩阵内
  • 由于线性成本，覆盖的总面积不能太大

我将 g 命名为我的问题的稀疏系数（所需对的数量超过可能的对总数，g = k / (n * p)。我知道系数a。

有一些明显的观察结果：

  • 如果 a 很小，最好的解决方案是独立请求每个 (record, field) 对，总成本为：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 xx
r2 x
r3 xx

可以重新排序为

   f1 f3 f2
r1 xx
r3 xx
r2 x

并且有一个最佳的解决方案是要求(f1,f3) x (r1,r3) + (f2) x (r2)

  • 尝试所有解决方案并寻找更低的成本不是一种选择，因为组合学爆炸了：
对于行上的每个排列：（n！）
   对于列上的每个排列：（p！）
       对于 nxp 矩阵的每个可能覆盖：（时间未知，但很大......）
           计算覆盖成本

所以我正在寻找一个近似的解决方案。我已经有某种贪心算法，可以在给定矩阵的情况下找到覆盖（它从单一单元格开始，如果合并中空单元格的比例低于某个阈值，则合并它们）。

记住一些数字，我的 n 介于 1 和 1000 之间，而我的 p 介于 1 和 200 之间。覆盖模式真的是“块状”，因为记录来自所要求的字段相似的类。不幸的是，我无法访问记录类...

问题 1：有人有什么想法、一个巧妙的简化或可能有用的论文参考吗？由于我有很多请求，因此我正在寻找一种平均运行良好的算法（但我无法承受它在某些极端情况下运行不佳，例如当 n 和 p 很大时请求整个矩阵，并且请求确实非常稀疏）。

问题2：其实问题更复杂：cost其实更像是这样的形式：a + n * (p^b) + c * n' * p'，其中b是一个常数<1（一个记录一旦求一个字段，再求其他也不算太贵字段）并且n' * p' = n * p * (1 - g)是我不想请求的单元格的数量（因为它们是无效的，并且请求无效的东西需要额外的费用）。我什至无法想到一个快速解决这个问题的方法，但仍然......任何人的想法？

4

6 回答 6

5

选择子矩阵来覆盖请求的值是集合覆盖问题的一种形式，因此是 NP 完备的。你的问题增加了这个已经很困难的问题，即套装的成本不同。

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

Wikipedia 文章给出了不可近似性结果，即问题不能在多项式时间内更好地解决，而不是使用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下最多可达约 1 倍，p = 200在悲观的情况下可达约 1 倍（仍然忽略不同的成本）。17100.000

因此，您能做的最好的事情是使用启发式算法（维基百科文章提到了一种几乎最优的贪心算法）并接受算法执行（非常）糟糕的情况。或者你走另一条路，使用优化算法并尝试找到一个好的解决方案，使用更多的时间。在这种情况下，我建议尝试使用A* search。

于 2009-09-10T15:57:34.913 回答
1

我敢肯定在某处有一个非常好的算法，但这是我自己的直观想法：

  1. 折腾一些矩形方法：

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

  2. 生长

    • 从它自己的 1x1 矩形中的每个点开始。
    • 定位 n 行/列内的所有矩形（其中 n 可能基于a）；看看您是否可以免费将它们组合成一个矩形（或负成本：D）。
    • 重复。

  3. 收缩

    • 从一个覆盖所有点的大矩形开始。
    • 寻找一个子矩形，它与大的有一对边，但包含的点很少。
    • 把它从大的切下来，产生两个较小的矩形。
    • 重复。

  4. 四边形

    • 将平面分成 4 个矩形。对于其中的每一个，看看是否通过进一步递归或仅包括整个矩形来获得更好的成本。
    • 现在拿你的矩形，看看你是否可以用很少/没有成本合并它们中的任何一个。\

另外：请记住，有时两个重叠的矩形比一个大矩形更好，后者是它们的超集。例如，两个矩形仅在一个角重叠的情况。

于 2009-09-10T08:36:54.717 回答
1

好的，我对这个问题的理解发生了变化。新主意：

  • 将每一行存储为一个长位串。AND 对位串在一起，试图找到最大化 1 位数量的对。将这些对分成更大的组（排序并尝试将真正大的组相互匹配）。然后构造一个请求，该请求将命中最大的组，然后忘记所有这些位。重复直到一切完成。有时可能会从行切换到列。

  • 查找其中包含零或很少点的所有行/列。暂时“删除”它们。现在，您正在查看将它们排除在外的请求所涵盖的内容。现在也许应用其他技术之一，然后处理被忽略的行/列。另一种思考方式是：先处理较密集的点，然后再处理较稀疏的点。

于 2009-09-10T10:55:10.643 回答
0

我会将用户请求集中提到的 n 个记录（行）和 p 个字段（列）视为 p 维空间（{0,1}^p）中的 n 个点，如果它有一个 X，则第 i 个坐标为 1 ，并确定集群的层次结构，其中最粗的集群位于根部，包括所有 X。对于集群层次结构中的每个节点，考虑覆盖所有所需列的乘积（这是行（任何子节点）x cols（任何子节点） ））。然后，自下而上决定是合并子覆盖物（为整个覆盖物付费），还是将它们作为单独的请求保留。（覆盖不是连续的列，但正是需要的列；即考虑一个位向量）

我同意 Artelius 的观点，即重叠的产品请求可能更便宜；我的分层方法需要改进才能合并。

于 2009-09-10T08:37:57.860 回答
0

由于您的值是稀疏的，是否有很多用户要求类似的值？在您的应用程序中缓存是一种选择吗？请求可以由作为 (x,y) 位置函数的哈希索引，以便您可以轻松识别位于网格正确区域内的缓存集。例如，将缓存集存储在树中可以让您快速找到覆盖请求范围的最小缓存子集。然后，您可以对很小的子集进行线性查找。

于 2009-09-10T08:42:04.020 回答
0

我已经做了一些工作，这是一个明显的 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 required}) 对于所有需要的记录]
成本 = [请求中请求的成本（请求）]

完成 = 假

虽然未完成：# 可能会有所收获
    最大增益 = 0
    完成=真
    this_step_merge = 空

    # 循环到所有请求对
    对于 (requests x request) 中的所有 (request1, request2)，例如 request1 != request2：
        合并请求 = 合并（请求 1，请求 2）
        增益 = 成本（请求 1）+ 成本（请求 2）- 成本（合并请求）

        如果增益 > 最大增益：
            最大增益 = 增益
            this_step_merge =（request1，request2，merged_request）

    # 如果我们发现至少要合并的东西，我们应该继续
    如果maximum_gain > 0：
        # 所以更新请求列表...
        request1，request2，merged_request = this_step_merge
        从请求中删除 request1
        从请求中删除 request2
        # ... 我们还没有完成
        将合并请求插入请求
        完成 = 假

输出请求

这是 O(n3 * p) 因为：

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

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

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

提前致谢 ！

于 2009-09-20T10:23:51.413 回答