更好的替代分而治之算法

首先讓我解釋一下我試圖解決的問題。我正在將我的代碼與第三方庫進行整合，這個庫做的很複雜的財務預測。爲了這個問題的目的，我們只是說我有一個黑盒子，當我傳入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

更好的替代分而治之算法

回答

相關問題