c++ - 通过使用任何有效算法最小化 Blackbox 调用数量来减少 2D 网格

Question

我有一个 100 × 100 点的 2D 网格(总计:10000 点)。 X 从 0 到 99 变化，Y 变化从 0 到 99。我将每个 (x,y) 发送到 BlackBox 模块，并返回 2 个值 p 和 q。黑盒子本质上是从基于 (x,y) 的可用函数集中选择一个函数并应用它on (x,y) 然后返回成本及其使用的函数索引。

因此，这个二维空间中的每个点都与 2 个值 (p,q) 相关联。第一个值'p'表示 Blackbox 使用哪个函数，第二个值'q'是成本。 Blackbox 对每个 (x,y) 使用的函数可能有所不同，并假设 Blackbox**(V = ~60) 可以使用最大 V 函数。还假设 **成本在 X 和 Y 维度上都是单调非递减的。

请注意，我们还可以使用三个参数 (x,y,k) 调用 Blackbox，这使其在 (x,y) 上执行函数 k 并返回一些 (k,q)。

我想要实现的就是这个。 Blackbox 选择了非常多的功能。 我想通过稍微增加积分成本来减少这种情况。

我想要做的是减少网格中使用的函数数量。假设 Blackbox 在该领域的某些地方使用了全部 60 个功能。我想找到一组最小的函数，用于评估点 (x,y) 不会使该点 (x,y) 的成本增加超过一个因子 s'。

例如:假设因子 's' = 20%。假设我从 (99,99) 开始并检查它的 p。假设 p = 5(第 5 个函数)在该点，q = 3000。假设在点 (99,98)，(p,q) = (8, 2600)。我调用 Blackbox (99,98,5)这使得黑盒在 (99,98) 点执行函数 5 并让我说 (8,2800) 作为返回值(value)。虽然 2800 > 2600，但 2800 - 2600 在 2600 的 20% 以内，所以因为我可以使用函数 5(99,99) 在 (99,98) 处我也可以忽略函数 8 至少对于点 (99,98)。

同样，我想减少该空间中使用的函数数量，以降低值(value)，而无需任何点的成本增加超过's'。通过调用 Blackbox 最小次数来实现此目的的最佳方法是什么？

暴力方式:选择使用的每个不同函数并在整个空间中对其进行评估，并基于此决定哪个函数是覆盖空间中满足“s”阈值的所有点的最小函数集。

我知道这个问题确实很难读，但我已尽力询问我的准确地提问。

Answer 1

只有当使用三个参数调用黑匣子的成本非常昂贵时，才有可能进行优化，例如黑匣子只能通过网络连接访问，因此本地计算机可以在从黑匣子获得一个答案的时间内执行数千次操作。

在这种情况下，我看到的优化是，您可以使用函数的单调性属性来推断给定点上每个函数的值。这允许您在网格中的分散位置调用函数，然后按原样“填空”。

例如，假设我在位置 {0,0} {0,4} {4,0} {4,4} 处计算函数 5 并得到以下结果

 7 ? ? ? 9
 ? ? ? ? ?
 ? ? ? ? ?
 ? ? ? ? ?
 3 ? ? ? 5

然后我可以推断函数 5 最坏情况的值为

 7 9 9 9 9
 7 9 9 9 9
 7 9 9 9 9
 7 9 9 9 9
 3 5 5 5 5

我可以推断函数 5 的最佳情况值为

 7 7 7 7 9
 3 3 3 3 5 
 3 3 3 3 5
 3 3 3 3 5 
 3 3 3 3 5

将此技术发挥到极致，您可以使用 x 和 y 值 0、50 和 99 来评估每个函数。这会将整个空间分为 4 个区域，收集到的信息可用于开始剔除列表的有用功能。例如，如果区域 1 中函数 33 的最坏情况值为 100，区域 1 中函数 45 的最佳情况值为 150，则函数 45 可以是从区域 1 的考虑中删除。

剔除有用函数列表后，通过评估中点的剩余函数将每个区域划分为四个子区域。根据需要继续 segmentation 。最终，要么单个函数将主导整个区域，要么该区域将缩减为单个点，剩下的候选函数数量有限。

您还可以通过使用两个参数 (x,y) 调用黑匣子来咨询黑匣子，以获取每个点的最佳可能值。然后应用模糊因子“s”来查找网格中每个点的绝对最大值。当您 segmentation 网格时，您可以消除最佳情况值大于绝对最大值的函数。例如，如果在点 {20,22} 处的绝对最大值为 200，并且函数 5 在点 {20,22} 处的最佳情况值为 210，则可以在点 {20,22} 处不考虑函数 5 .