0

まず、私が解決しようとしている問題を説明させてください。非常に複雑な財務予測を行うサードパーティのライブラリとコードを統合しています。この質問の目的のために、x を渡すと y を返すブラックボックスがあるとしましょう。今、私がする必要があるのは、特定の出力 (y) に対する入力 (x) を見つけることです。可能な限り低い入力値と最も高い入力値を知っているので、次のアルゴリズムを書きました。

  1. 開始入力範囲の定義 (最小入力値から最大入力値)
  2. 範囲を 2 つの等しい部分に分割し、中間値の出力を見つけます
  3. どの半分の出力が当てはまるかを見つけます
  4. 範囲が小さすぎてそれ以上分割できないまで、手順 2 と 3 を繰り返します。

このアルゴリズムはうまく機能します。問題はありません。しかし、この問題を解決するためのより速い方法はありますか?

4

1 に答える 1

1

そうしないと、分割統治アルゴリズムが機能しないため、強く相関しているように聞こえます（つまり、xが増加すると、 も増加します）。yxy

これが事実であり、相関係数を計算できると仮定すると、中間点に相関係数を掛けて、期待値をより迅速に調整できる可能性があります。

私はこのアイデアをまったくテストしていないことに注意してください。可能な改善は、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 に答える