2

我目前正在用树做一些计算。每个节点都有我要计算的 5 个值和决定如何计算这些值的类型。一些计算可能是相当复杂的算法。节点内的所有计算仅取决于其子节点的值，因此我从下到上进行计算。对于每个节点类型，一个值取决于子节点的不同值。我主要对根节点中的 5 个值感兴趣，这取决于所有其他节点中的所有值。所有这一切都很好。一个节点只能有 1 或 2 个子节点，树通常不超过 5 层。

对于某些节点类型，存在容差；意思是有些值没有关系，看这张图，我用XX标记了。有时，某些值甚至是相关的，例如 C = XX * A。目前，这些值只是设置为一些默认值。有时甚至会存​​在复杂的关系，例如牛顿法等算法的多种可能解决方案，具体取决于起始值。

对不起我的绘画技巧不好

现在我可以对根节点的值应用评级。我想要的是通过调整树深处的 XX 值来优化这个评级。每个节点内的计算可以是许多可能的公式的范围，而容差可以是许多可能的模式之一，所以我不能只找出一些公式，但我需要一些非常灵活的算法。我不知道这样的算法。有人有想法吗？

/编辑：澄清一下，目前还不清楚树中有多少值是空闲的。不仅有一个 XX，而且可能有任意数量（我猜最多 10 个），所以我的第一步是识别这些值。此外，我将在一个时间窗口内对许多生成的树执行此操作，因此速度也不是不重要的。谢谢：）

4

2 回答 2

1

正如另一个答案所指出的，这看起来像是一个优化问题。您可以考虑使用遗传算法。基本上，您尝试通过“交配”具有不同特征（在您的情况下为叶子上的值）的不同个体（在您的情况下为树）并根据目标函数（在您的情况下，您在根节点上获取）。可以通过向您的种群添加突变来改进算法（就像在自然界的进化中一样）。

于 2012-08-24T14:22:17.263 回答
1

如果您有 3 个输入值 XX、YY 和 ZZ，则您正在搜索 3 维空间。您要做的是应用优化算法或启发式算法。您对算法的选择是关键，这是您的时间和计算机时间之间的成本效益。我猜你只想做一次。

无论您使用哪种方法，您都需要了解问题，这意味着了解您的算法如何随着不同的输入值而变化。有些解决方案有一个很好的最小值，很容易找到（例如使用牛顿法），有些则没有。

我建议从简单开始。最基本的方法之一就是进行迭代搜索。它很慢，但它有效。您需要确保您的迭代步长不会太大，这样您就不会错过一些甜蜜点。

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 回答