2

私は現在、木を使っていくつかの計算を行っています。各ノードには、計算しようとしている5つの値と、これらの値の計算方法を決定するタイプがあります。一部の計算は、かなり複雑なアルゴリズムになる可能性があります。ノード内のすべての計算は、その子ノードの値のみに依存するため、下から上に計算を行っています。ノードタイプごとに、値は子ノードのさまざまな値によって異なります。私は主にルートノードの5つの値に興味があります。これらは、cの他のすべてのノードのすべての値に依存します。これはすべて正常に機能しています。ノードは1つまたは2つの子ノードしか持つことができず、ツリーは通常5レベルより深くはありません。

一部のノードタイプには、許容範囲があります。いくつかの値は重要ではないことを意味します。この写真を参照してください。私はそれらにXXのマークを付けました。場合によっては、C = XX * Aのように、いくつかの値が関係していることもあります。現在、これらの値はいくつかのデフォルト値に設定されています。開始値によっては、ニュートン法のようなアルゴリズムの複数の可能な解のように、複雑な関係が存在する場合もあります。

描画スキルが悪いのでごめんなさい

これで、ルートノードの値に適用できる評価があります。ツリーの奥深くにあるXX値を調整して、この評価を最適化したいと思います。各ノード内の計算は多くの可能な式の範囲であり、許容誤差は多くの可能なパターンの1つである可能性があるため、式を理解することはできませんが、非常に柔軟なアルゴリズムが必要になります。私はそのようなアルゴリズムを知りません。誰かアイデアがありますか？

/編集：明確にするために、ツリー内のいくつの値が解放されるかは不明です。XXは1つだけではなく、いくつでも存在する可能性があるため（最大10と思います）、最初のステップはこれらの値を特定することです。また、時間枠内に生成された多くのツリーでこれを実行するので、速度も重要ではありません。ありがとう：）

4

2 に答える 2

1

3つの入力値XX、YY、およびZZがある場合、3次元空間を検索しています。あなたがしようとしているのは、最適化アルゴリズム、またはヒューリスティックアルゴリズムを適用することです。アルゴリズムの選択が重要であり、時間とコンピューターの時間の間のコスト面でのメリットがあります。一度だけやりたいと思います。

どの方法を使用する場合でも、問題を理解する必要があります。つまり、さまざまな入力値でアルゴリズムがどのように変化するかを理解する必要があります。一部のソリューションには、見つけやすい非常に優れた最小値があり（たとえば、ニュートン法を使用）、そうでないものもあります。

簡単に始めることをお勧めします。最も基本的なものの1つは、反復検索を実行することです。遅いですが、動作します。いくつかのスイートスポットを見逃さないように、反復ステップが大きすぎないことを確認する必要があります。

For XX = XXmin to XXmax
  For YY = YYmin to YYmax
    For ZZ = ZZmin to ZZmax

      result = GetRootNodeValue(XX, YY, ZZ)

      If result < best_result then
        print result, XX, YY, ZZ
        best_result = result
      End if

    End For
  End For
End For

以下は別の方法です。これは確率的最適化方法であり（ランダムな点を使用して最良の解に収束します）、その結果はほとんどの条件で妥当です。私はこれをうまく使用しました、そしてそれは最小値に収束するのが得意です。これは、明確なグローバル最小値がない場合に使用すると便利です。問題のパラメータを設定する必要があります。

' How long to search for, a larger value will result in long search time
max_depth = 20000

' Initial values
x0 = initial XX value
y0 = initial YY value
z0 = initial ZZ value

' These are the delta values, how far should the default values range
dx = 5
dy = 5
dz = 5

' Set this at a large value (assuming the best result is a small number)
best_result = inf

' Loop for a long time
For i = 1 To max_depth

    ' New random values near the best result
    xx = x0 + dx * (Rnd() - 0.5) * (Rnd() - 0.5)
    yy = y0 + dy * (Rnd() - 0.5) * (Rnd() - 0.5)
    zz = y0 + dy * (Rnd() - 0.5) * (Rnd() - 0.5)

    ' Do the test
    result = GetRootNodeValue(xx, yy, zz)

    ' We have found the best solution so far
    If result < best_result Then
        x0 = xx
        y0 = yy
        z0 = zz
        best_result = result
    End If

    Print progress
Next i

選択できる最適化アルゴリズムはたくさんあります。上記は非常に単純なものですが、問題に最適ではない場合があります。

于 2012-08-24T12:15:03.533 に答える
1

別の答えが指摘しているように、これは最適化問題のように見えます。遺伝的アルゴリズムの使用を検討してください。基本的に、あなたは異なる特性（あなたの場合は葉の値）を持つ異なる個体（あなたの場合は木）を「交配」することによって進化プロセスを模倣し、目的関数（あなたの場合はあなたが何をするか）に基づいてそれらを生き残らせようとしますルートノードで取得）。アルゴリズムは、（自然の進化のように）母集団に突然変異を追加することで改善できます。

于 2012-08-24T14:22:17.263 に答える