Нахождение локального минимума

Question

Код ниже правильно находит локальный максимум массива, но не может найти локальный минимум. Я выполнил поиск в Интернете, чтобы найти лучшие методы поиска минимумов, и я думаю, что я использую правильный метод ниже, основанный на этих поисках. Но в приведенном ниже коде есть какая-то ошибка, которую я до сих пор не вижу, пройдя по каждой строке много раз в течение нескольких дней.

Переменные startX и endX определяют выбранное пользователем окно, в котором код должен находить локальные мин / макс. Если вы манипулируете значениями startX и endX, вы увидите, что приведенный ниже код всегда выводит минимум в качестве первого индекса выбранного окна, что указывает на то, что он не выполняет итерацию по индексам в окне для поиска минимума.

Может кто-нибудь найти ошибку и показать, как исправить приведенный ниже код, чтобы найти локальный минимум?

class LocalMinMax {
static double[] pts;
static int visiblePoints=5000;
static int startX = 200;
static int endX = 700;

public static void main (String[] args) {
    int lastX2 = 0;
    int maxWidth = 800;
    double hstep = (double) maxWidth / visiblePoints;
    int maxHeight = 400;
    pts = new double[visiblePoints];
    double max = Double.NEGATIVE_INFINITY;
    double min = Double.POSITIVE_INFINITY;
    int minIndex = -1;
    int maxIndex = -1;
    for (int i = 0; i < visiblePoints; i++){
        pts[i] = (double) ((((Math.sin(.009*i))*(Math.cos(.004*i))) * (maxHeight/3) * .95) + (maxHeight/2));
        int x2 = (int) (i * hstep);
        if(x2>=startX){
            int sectionStartIndex = i;
            int sectionEndIndex = (int)(endX/hstep);
                for(int k=sectionStartIndex;k<sectionEndIndex;k++){
                    if(min>pts[k]){
                        min = pts[k];
                        minIndex = x2;
                        System.out.println("minIndex, min, pts["+k+"]: , x2 are: "+minIndex+", "+min+", "+pts[k]+", "+x2);
                    }
                    if(max<pts[k]){
                        max = pts[k];
                        maxIndex = x2;
                    }}}
        if(lastX2!=x2){
            lastX2=x2;
            if(x2==startX){
                int width = endX - startX;
                System.out.println("WINDOW: width, startX, endX are: "+width+", "+startX+", "+endX);
                }}}
    int maxVal = (int)max;
    int minVal = (int)min;
    System.out.println("LOCAL MAX: maxIndex, maxVal are: "+maxIndex+", "+maxVal);
    System.out.println("LOCAL MIN: minIndex, minVal are: "+minIndex+", "+minVal);
    }}

Answer 1

Поскольку функция f(x) = sin(ax) + cos(bx) (как минимум) дважды дифференцируема , альтернативный подход заключается в нахождении минимумов и максимумов аналитически.Там, где первая производная равна нулю, функция будет иметь локальный экстремум .Знак второй производной указывает, является ли экстремум минимальным или максимальным.

Answer 2

Одним из подходов является сканирование назад через окно sectionStartIndex..sectionEndIndex, как показано ниже. Это не решение, но оно позволит увидеть, как зеленый прямоугольник движется вверх и вниз, так как отслеживает минимум.

for (int k = sectionStartIndex; k < sectionEndIndex; k++) {
    int j = sectionEndIndex - k;
    if (min > pts[j]) {
        System.out.println("minIndex, min, pts[" + j + "]: "
            + minIndex + ", " + min + ", " + pts[j]);
        min = pts[j];
        minIndex = x2Count;
    }
    if (max < pts[k]) {
        max = pts[k];
        maxIndex = x2Count;
    }
}

Добавление: выведение инициализации массива из цикла является одним из подходов, как показано ниже. Обратите внимание на использование делителя double в операциях масштабирования.

Более серьезная проблема - оценка функции в одном домене и выборка в другом. Я бы отделил представление (координаты мыши) от модели (действительные числа, представленные double). Введите методы для преобразования координат между ними, такие как *scale* функции, видимые здесь . Пусть модель оценит функцию при движении мыши; оптимизировать только в случае необходимости.

Local: maxIndex, maxVal: 200, 326
Local: minIndex, minVal: 200, 79

class LocalMinMax {

    static double[] pts;
    static int visiblePoints = 5000;
    static int startX = 200;
    static int endX = 700;

    public static void main(String[] args) {
        int lastX2 = 0;
        int maxWidth = 800;
        double hstep = maxWidth / (double) visiblePoints;
        int maxHeight = 400;
        pts = new double[visiblePoints];
        for (int i = 0; i < pts.length; i++) {
            pts[i] = (((Math.sin(.009 * i)) * (Math.cos(.004 * i)))
                * (maxHeight / 3d) * .95) + (maxHeight / 2d);
        }
        double max = Double.NEGATIVE_INFINITY;
        double min = Double.POSITIVE_INFINITY;
        int minIndex = -1;
        int maxIndex = -1;
        for (int i = 0; i < visiblePoints; i++) {
            int x2 = (int) (i * hstep);
            if (x2 >= startX) {
                int sectionStartIndex = i;
                int sectionEndIndex = (int) (endX / hstep);
                for (int k = sectionStartIndex; k < sectionEndIndex; k++) {
                    if (min > pts[k]) {
                        min = pts[k];
                        minIndex = x2;
                      //System.out.println("minIndex, min, pts[" + k + "], x2: "
                      //+ minIndex + ", " + min + ", " + pts[k] + ", " + x2);
                    }
                    if (max < pts[k]) {
                        max = pts[k];
                        maxIndex = x2;
                      //System.out.println("maxIndex, max, pts[" + k + "], x2: "
                      //+ maxIndex + ", " + max + ", " + pts[k] + ", " + x2);
                    }
                }
            }
            if (lastX2 != x2) {
                lastX2 = x2;
                if (x2 == startX) {
                    int width = endX - startX;
                }
            }
        }
        int maxVal = (int) max;
        int minVal = (int) min;
        System.out.println("Local: maxIndex, maxVal: " + maxIndex + ", " + maxVal);
        System.out.println("Local: minIndex, minVal: " + minIndex + ", " + minVal);
    }
}