更好的替代分而治之算法

首先让我解释一下我试图解决的问题。我正在将我的代码与第三方库进行整合，这个库做的很复杂的财务预测。为了这个问题的目的，我们只是说我有一个黑盒子，当我传入x时返回y。现在，我需要做的是找到给定输出（y）的输入（x）。因为我知道最低和最高的可能输入值我写下面的算法：更好的替代分而治之算法

定义开始输入范围（最小输入值到最大输入值）
分的范围分成两个相等的部分，并找到一个中间输出值
发现其中一半产量下降到
重复步骤2和3，直到范围太小划分进一步

这种算法不工作很好，我没有看到任何p与它一起讨论。但是，解决这个问题有更快的方法吗？

来源

2013-03-27 Vytas

你没有告诉太多的数学特性复杂的财务预测算法。因此很难说。 – 2013-03-27 14:48:27

@Vytas这听起来像'x'和'y'是强关联的（即''x'增加，'y'也是如此），否则你的分而治之算法将不起作用。你能证实这是事实吗？ – 2013-03-27 14:50:47

Ondrej，RB - 问题是我不知道这个预测算法的内部运作。我唯一知道的是输入和输出之间有很强的相关性，即随着x的增加，y也增加。但是，x和y之间的关系不是线性的。 – Vytas 2013-03-27 14:58:30

这听起来像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-27 15:00:07

更好的替代分而治之算法

回答

相关问题