3

背景:私のプログラムには、一連の点を取り、それらの点によって生成された曲線の最小値と最大値を見つける関数があります。問題は、while ループを使用して近似誤差に基づいて最小/最大を計算するため、信じられないほど遅いことです。私は自分で書いたわけではないので、これがどの正式な方法なのか完全にはわかりませんが、新しいより効率的な方法が必要であることはわかっています。

質問:私の質問は、C# を使用して曲線上の最小最大ポイントを見つけるための最良かつ最も効率的な方法/アルゴリズムは何ですか?これも非常に正確ですか?

曲線について:近くに大学の数値解析の本があるので、必要なのはメソッド名と正しい方向への微調整だけです。曲線を近似するために選択した数のポイントを生成できますが、ポイントの数を効率的な最小値に維持したいと考えています。曲線は常に Sin/Cos 曲線の 1 つのセグメントの形をしていますが、常に同じ曲線であるとは限らず、常に 1 周期未満になります。Theta の範囲は 0° から 359.999...° です。位相と振幅のシフトがあり、Y が負になることはありません。この関数/アルゴリズムは、曲線が変化するにつれて数百ミリ秒ごとに実行されるため、高速に実行する必要があります。

任意の提案をいただければ幸いです。

編集

曲線の詳細:ポイントはマウスの移動で生成されます。ポイントは、車のサーペンタイン ベルトのようなアイドラーを備えたドライブ デザインのゴム ベルトの長さに基づくポイントのセットです。アイドラーの位置によってベルトの長さが決まり、曲線 [ベルトの長さ (y) 対 アイドラーの位置 (x)] が得られます。この場合のアイドラーは旋回アイドラーであり、一定の円運動をします。ドライブの設計が変わると、長さのポイントが変わるか、アイドラーの可動範囲が制限されるため、曲線が変わります。アイドラーの可動範囲は、潜在的に 0° から 359.999...° であり、上記のようにシータです。スロット付きアイドラーの場合、最大範囲は曲線の周期の 1/2 です (より簡単な問題)。

私が必要としているのは、両方のタイプのアイドラーの一般的なソルバーだと思いますが、実際の問題はピボット アイドラーにあります。

4

7 に答える 7

2

二次方程式がある場合、最大値または最小値は常に方程式の微分が 0 になる点になります。二次方程式の式が ax^2 + bx + c = 0 の場合、この点は x = -b/2a.

それが最大 opr 最小値であるかどうかは、a を見ることで判断できます。a > 0 の場合は最小値、a < 0 の場合は最大値です (a = 0 の場合は 2 次ではありません)。

それが役立つことを願っています。この種の形で曲線の方程式を持っていない場合、何から作業しなければならないかを教えていただけますか?

編集：曲線が正弦曲線の一部であり、二次曲線ではなくなるように質問が変更されました。したがって、この答えはもはや適切ではありません。

編集2:

正弦曲線の場合、一般式は y = a sin(mx+t) + c になります。元の方程式を正確に決定することはできません。これは、どの解にも一致するより高い周波数の解が存在するためです。現在、 a が何であるかを正確に計算するためにいくつのポイントが必要かはわかりません(これにより、曲線の最小値と最大値が得られます)。

于 2010-07-06T15:28:44.887 に答える
0

使用する必要のあるアルゴリズム（および指定するパラメーター）は、データセットがどのように見えるかによって異なります。継続的に取得される物理測定の波形を評価しているようです。

その場合、極小値と極大値を無視するかどうかを決定する必要があります（たとえば、信号のノイズからのスパイク）。また、データセットのエッジを処理する方法が必要になります。つまり、データの先頭が現在のデータセットの最高点であるが、前のデータセットの大きなピークから下がっているだけの場合、データの先頭は最大値としてカウントされますか？

固定ピーク検出アルゴリズムには、通常、しきい値と幅（スパイクに対する感度を制御するため）およびバッファーサイズ（実際に緩やかなピークを処理するため）を指定する方法があります。

そこにはたくさんのアルゴリズムがあります。期待する結果が得られるまで、1つまたは2つを選択し、パラメーターを微調整するだけです。

于 2010-07-06T16:04:40.970 に答える
0

私は少し混乱しています。

あなた自身がポイントを生成しているのなら、生成を行うときに最大/最小のポイントを追跡してみませんか？

他の人が指摘しているように、関数がある場合は、導関数を取得して0を解くだけです。これにより、最小/最大のポイントが得られます。

于 2010-07-08T04:15:40.073 に答える
0

いくつかのポイント (>=4) を収集した後、ローカル検索の形式を使用してポイントを正弦曲線に一致させy = A cos(Bx+C)+D、導関数に基づく単純な式を使用して最小値を見つけることができます。検索中は、冗長な高周波数ソリューションを回避するために、B をできるだけ小さくする必要があります。単なるアイデアでは、非常に非効率的である可能性があります。

于 2010-07-06T20:31:34.507 に答える
0

コメントから、入力 X と出力 Y は配列です

「@マイク：値を生成して配列に入れます」

このアプローチを使用することをお勧めします。私のコードで必要なのは {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

利用できるのはポイントのセットだけですか? また、これらの点が表す関数の「形状」に制限はありませんか? もしそうなら、あなたはおそらく立ち往生しています。ポイントを繰り返し処理するのが最善の策です...
ただし、このセットで他に行う作業がある場合は、将来使用するために Y 座標で並べ替えることをお勧めします。処理。

（両方の配列を保持します-入力として供給されたもの（おそらく x-corrd でソートされていますか？）と関数値（y-coord）でソートされたもの）...

編集: 曲線が常に Sin/Cos 曲線の一部のように形作られることがわかっている場合、表現される可能性のある最小の期間がわかっている場合は、二分探索アルゴリズムを使用して「探す」ことで最適化を行うことができます。変曲点 (傾斜 (Y の左と右への変化) の符号は異なります。左側で調べた各点について、チャンクだけ右に移動します = 変曲点が見つかるまでの許容期間の半分) 、または勾配が符号を変更します...次に、変曲点が見つかるまで、x の最後の変化の半分だけ後ろに移動します [右側の点については逆を行います]

最初と最後の変曲点を調べて見つけ出し、それらを比較してどちらが最大かを決定し、関係する 2 つの点が最小許容期間よりも短くなるまで、それらの中間にある変曲点を再帰的に調べて見つけます。互いに、パフォーマンスが向上します...

2番目の編集：セットに複数の変曲点が含まれることは決してないという他のコメントを読んだので... その場合は、バイナリ検索を実行して見つけてください。

疑似コード:

  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

曲線は常に 2 次 (したがって常に凸) であるため、多くのメソッドが利用可能であるはずです (ただし、私は C# でプログラミングしていないため、ソースが利用可能かどうかはわかりません)。ニュートン法が最初に思い浮かびますが、他にもあります (内点法など)。これらのアルゴリズムの数学的背景 (ただし、残念ながら実装については説明しません) については、この教科書 (pdf) を参照してください。これらの方法のいずれかを使用すると、他の凸曲線でも機能します。

于 2010-07-06T15:33:37.497 に答える