근사 검색은 어떻게 비단조 함수의 값과 매개변수를 효율적으로 찾을 수 있습니까?-C++-php.cn

근사 검색은 어떻게 비단조 함수의 값과 매개변수를 효율적으로 찾을 수 있습니까?

DDD

풀어 주다： 2024-12-30 22:54:10

원래의

627명이 탐색했습니다.

How Can Approximation Search Efficiently Find Values and Parameters for Non-Monotonic Functions?

함수 피팅 및 방정식 풀이를 위한 근사값 및 매개변수

근사 검색의 내부 작동 방식을 이해하는 것은 다항식 피팅, 매개변수 함수 및 초월 함수와 관련된 문제를 해결하는 데 중요합니다. 방정식. 이 접근 방식을 사용하면 엄격하게 단조롭지 않은 함수를 처리할 때에도 값과 매개변수를 효과적으로 추정할 수 있습니다.

근사 검색 작동 방식

근사 검색은 이진 검색의 개념을 모방하지만 그렇지 않습니다. 검색된 함수가 엄격하게 단조롭다는 제약을 부과하지 않습니다. 작동 방식은 다음과 같습니다.

알려진 간격 에 걸쳐 고르게 분포된 프로브 샘플 포인트.
오차 또는 함수 값 f(x) 사이의 거리를 계산합니다. 각 샘플 포인트와 목표 값 y0.
최소 오류가 있는 샘플 포인트를 식별합니다( aa).
aa를 중심으로 더 좁은 간격 내에서 1~3단계를 반복하여 정확도를 높입니다.
원하는 정확도에 도달하거나 최대 재귀 횟수에 도달할 때까지 재귀를 계속합니다.

주요특징

처리능력 단조롭지 않은 함수 또는 엄격한 함수가 아닌 함수.
O(log(n)) 복잡도로 안정적이고 효율적인 알고리즘을 제공합니다.
사용자 정의 정밀도 및 오류 계산이 가능합니다.

구현

다음은 근사치의 단순화된 C 구현입니다. 검색:

class approx {
public:
    void init(double a0, double a1, double da, int n, double *e) {
        a0 = min(a0, a1); a1 = max(a0, a1); // Ensure a0 < a1
        da = abs(da);
        this->n = n; e = e;
        e0 = -1.0; i = 0; a = a0; aa = a0;
        done = false; stop = false;
    }
    void step() {
        if ((e0 < 0.0) || (e0 > *e)) { e0 = *e; aa = a; }  // Better solution
        if (stop) {
            i++;
            if (i >= n) { done = true; a = aa; return; }  // Final solution
            a0 = aa - fabs(da);
            a1 = aa + fabs(da);
            a = a0; da *= 0.1;
            a0 += da; a1 -= da;
            stop = false;
        } else {
            a += da;
            if (a > a1) { a = a1; stop = true; }  // Next point
        }
    }
};

로그인 후 복사

사용 예

y = f(x)가 y0에 가장 가까운 x 값을 찾고 싶다고 가정해 보겠습니다. 근사 클래스를 사용하는 방법은 다음과 같습니다.

approx aa;
double ee, x, y, x0, y0 = your_target_value;
for (aa.init(0.0, 10.0, 0.1, 6, &ee); !aa.done; aa.step()) {
    x = aa.a;
    y = f(x);
    ee = abs(y - y0);
}

로그인 후 복사