3

背景：我的程序中有一个函数，它采用一组点并在这些点生成的曲线上找到最小值和最大值。问题是它非常慢，因为它使用 while 循环根据近似误差来计算最小值/最大值。不完全确定这是什么形式的方法，因为我不是自己写的，但我知道我们需要一种新的更有效的方法。

问题：我的问题是什么是最好和最有效的方法/算法来找到曲线上的最小最大点，使用 C#，也非常准确？

关于曲线：我附近有我大学的数值分析书，所以我需要的只是一个方法名称和一个正确方向的推动。我可以生成尽可能多的点来逼近曲线，但我想将点数保持在有效的最小值。曲线总是呈正弦/余弦曲线的一段形状，但并不总是相同的曲线，而且总是小于一个周期。Theta 的范围是 0° 到 359.999...° 它有一些相位和幅度偏移，并且 Y 永远不会是负数。这个函数/算法必须快速运行，因为它会随着曲线的变化每隔几百毫秒运行一次。

任何建议表示赞赏。

编辑

有关曲线的更多信息：这些点是在鼠标移动时生成的。这些点是基于带惰轮的驱动设计中的橡胶带长度的一组点，例如汽车中的蛇形皮带。惰轮的位置决定了皮带的长度，我得到曲线[皮带长度（y）与惰轮位置（x）]。在这种情况下，惰轮是一个可旋转的惰轮，将具有恒定的圆周运动。如果驱动设计改变，曲线也会改变，要么是因为长度点改变，要么是因为惰轮的运动范围受到限制。惰轮的运动范围可能是 0° 到 359.999...°，并且是如上所述的 theta。对于开槽惰轮，最大范围是曲线周期的 1/2（更简单的问题）。

我想我需要的是两种类型的惰轮的通用求解器，但真正的问题是旋转惰轮。

4

7 回答 7

2

如果你有一个二次方程，那么最大值或最小值总是在方程的微分为 0 时。如果你的二次方程有一个公式 ax^2 + bx + c = 0，那么这个点将是当 x = -b/2a。

是否是最大 opr 最小值可以通过查看 a 来确定。如果 a > 0 则它是最小值，如果 a < 0 则它是最大值（如果 a = 0 则它不是二次的）。

我希望这会有所帮助。如果你还没有这种形式的曲线方程，你能说出你必须从什么开始工作吗？

编辑：问题已经改变，曲线是正弦曲线的一部分，不再是二次曲线。因此，这个答案不再合适。

编辑2：

对于正弦曲线，一般方程为 y = a sin(mx+t) + c。您将永远无法准确确定原始方程，因为对于任何解决方案，都会有一个更高频率的解决方案也匹配。我目前不确定精确计算 a 需要多少点（这将给出曲线的最小值和最大值）。

于 2010-07-06T15:28:44.887 回答
0

你有所有可用的点吗？这些点所代表的功能的“形状”是否没有限制？如果是这样，那么你可能会被卡住，遍历这些点将是你最好的选择......
虽然如果你在这个集合上有任何其他工作要做，你可能希望按 Y 坐标对其进行排序以供将来使用加工。

（保留两个数组 - 作为输入提供的一个（它可能按 x-corrd 排序？）和按函数 value(y-coord) 排序的一个）...

编辑： 如果您知道曲线的形状总是“像”Sin/Cos 曲线的一部分，那么如果您知道可能表示的最小周期，您可以通过使用二分搜索算法进行一些优化来“寻找”拐点（其中斜率（Y 向左和向右的变化）具有不同的符号。对于左侧检查的每个点，向右移动块 = 允许周期的一半，直到找到拐点, 或斜率改变符号... 然后向后移动 x 最后一次变化的一半，直到找到拐点。[对右边的点做相反的事情]

检查/找到第一个和最后一个拐点的递归例程，比较它们以确定哪个最大，然后递归检查并找到它们之间的感染点，直到所涉及的两个点小于最小允许周期彼此，将产生一些性能提升......

第二次编辑：由于我在您的其他评论中阅读了该集合永远不会包含一个以上的拐点......如果是这样，那么只需进行二进制搜索即可找到它。

伪代码：

  Check Leftmost point to see slope (Up Down or Zero)
       If Zero, done
  Check RightMost Slope 
       If Zero - Done
  If two Slopes are same sign - Done 
        - pick Bigger of two points ( - or smaller if looking for min)
  Check point in the Middle slope
     If Zero, Done
     If slope has same sign as left pt, Change Left to this Point and repeat
     If slope has same sign as right pt, Change Right to this Point and repeat
于 2010-07-06T15:32:01.803 回答
0

由于曲线总是二次的（因此总是凸的），所以应该有很多可用的方法（虽然因为我没有用 c# 编程，所以我不知道是否有可用的源）。首先想到的是牛顿法，但还有其他方法（如内点法）。有关这些算法的数学背景（不幸的是，不是它们的实现），请参阅这本教科书 (pdf)。如果您确实使用了这些方法中的任何一种，它们也适用于其他凸曲线。

于 2010-07-06T15:33:37.497 回答
0

你应该使用的算法（以及你给它的参数）取决于你的数据集是什么样的。听起来您正在评估一些连续采集的物理测量的波形。

如果是这样，那么您需要决定是否要忽略局部最小值和最大值（例如信号中的噪声尖峰）。此外，您还需要某种方法来处理数据集的边缘。换句话说，如果数据的开头是当前数据集中的最高点，但只是从前一个数据集中的一个大峰值下降，那么它是否算作一个最大值？

固定峰检测算法通常有一些方法来指定阈值和宽度（以控制对尖峰的敏感性）和缓冲区大小（以处理真正渐变的峰）。

那里有很多算法，只需选择一两个并调整参数，直到它给出您期望的结果。

于 2010-07-06T16:04:40.970 回答
0

在收集了几个点 (>=4) 后，您可以使用一种局部搜索形式将您的点与正弦曲线匹配，y = A cos(Bx+C)+D然后使用基于导数的简单公式来找到最小值。在搜索时，您应该尽可能少地保留 B 以避免冗余的高频解决方案。只是一个想法，可能效率很低。

于 2010-07-06T20:31:34.507 回答
0

从评论中，输入 X 和输出 Y 是数组

“@Mike：我生成值并将它们放在一个数组中”

我建议使用这种方法。您需要从我的代码中得到的只是 {getMaxIndex}

    private void Test()
    {
        double[] X = SetLinearRange(0, Math.PI * 2, 1000);
        double[] Y = GetOutput(X);
        int MaxIndex = getMaxIndex(Y);
        double MaxX = X[MaxIndex];
        double MaxY = Y[MaxIndex];
    }
    private double[] SetLinearRange(double Start, double End, int Sample)
    {
        double Step = (End - Start) / Sample;
        double CurrentVaue = Start;
        double[] Array = new double[Sample];
        for (int Index = 0; Index < Sample; Index++)
        {
            Array[Index] = CurrentVaue;
            CurrentVaue += Step;
        }
        return Array;
    }
    private double[] GetOutput(double[] X)
    {
        double[] Array;
        Array = (from double Item in X select myFunction(Item)).ToArray();
        return Array;
    }
    private double myFunction(double x)
    {
        double y;
        //put any function
        y = 3 * Math.Sin(5 * x + 2);
        return y;
    }
    private int getMaxIndex(double[] Y)
    {
        double YM = Y.Max();
        int Index = Y.ToList().IndexOf(YM);
        return Index;
    }

我希望那会很快。

于 2010-07-08T03:25:16.480 回答
0

我有点困惑。

如果您自己正在生成点，为什么不在生成时跟踪最大/最小点？

如果您有一个函数，就像我确定其他人已经指出的那样，只需获取导数并求解 0。这将为您提供最小/最大值的点。

于 2010-07-08T04:15:40.073 回答