0

首先让我解释一下我要解决的问题。我正在将我的代码与 3rd 方库集成，该库可以进行相当复杂的财务预测。就这个问题而言，假设我有一个黑盒，当我传入 x 时它会返回 y。现在，我需要做的是为给定的输出 (y) 找到输入 (x)。因为我知道最低和最高可能的输入值，所以我编写了以下算法：

  1. 定义起始输入范围（最小输入值到最大输入值）
  2. 将范围分成两个相等的部分并找到中间值的输出
  3. 找出哪一半输出落入
  4. 重复步骤 2 和 3，直到范围太小而无法进一步划分

这个算法很好地完成了这项工作，我认为它没有任何问题。但是，有没有更快的方法来解决这个问题？

4

1 回答 1

1

这听起来像x并且y是高度相关的（即随着x增加，所以也会增加y），否则您的分而治之算法将无法工作。

假设是这种情况，并且您可以计算出一个相关因子，那么您可以将中点乘以相关因子，以更快地磨练预期值。

请注意，我根本没有测试过这个想法，但这是值得考虑的事情。可能的改进是将correlationFactor 设为移动平均线，或者根据例如xLow 和xHigh 之间的十分位数预先计算它。

此外，这假设呼叫f(x)相对便宜。如果它很昂贵，那么增加的调用次数f(x)将使任何节省都相形见绌。事实上 - 我开始认为这是一个愚蠢的想法......

希望下面的伪代码能说明我的意思：

DivideAndConquer(xLow, xHigh, correlationFactor, expectedValue)
    xMid = (xHigh - xLow) * correlationFactor
    // Add some range checks to make sure that xMid is within xLow and xHigh!!
    y = f(xMid)
    if (y == expectedValue)
        return expectedValue
    elseif (y < expectedValue) 
        correlationFactor = (xMid - xLow) / (f(xMid) - f(xLow))
        return DivideAndConquer(xLow, xMid, correlationFactor, expectedValue)
    else
        correlationFactor = (xHigh - xMid) / (f(xHigh) - f(xMid))
        return DivideAndConquer(xMid, xHigh, correlationFactor, expectedValue)
于 2013-03-27T15:00:07.197 回答