Háromszoros keresés

A hármas keresés (Ternary search)  egy számítástechnikai módszer egy olyan függvény maximumának és minimumának megkeresésére, amely vagy először szigorúan növeli , majd szigorúan csökkenti , vagy fordítva. A hármas keresés megállapítja, hogy a minimum vagy maximum nem lehet sem a régió első, sem utolsó harmadában, majd megismétli a keresést a maradék két harmadban. A hármas keresés az „ oszd meg és uralkodj ” programozási paradigmát mutatja be.

Funkció

Tegyük fel, hogy az f ( x ) függvény maximumát keressük, és tudjuk, hogy a maximum A és B között van . Ahhoz, hogy az algoritmus alkalmazható legyen, rendelkeznie kell olyan x értékkel , amely

Algoritmus

/** Megkeresi egy olyan függvény maximumát, amelynek egy szélső értéke l és r között van. A minimum megtalálásához elegendő az if/else ágak műveleteit felcserélni. */ dupla l = ..., r = ..., EPS = ...; // bemeneti adatok double m1 , m2 ; while ( r - l > EPS ) { m1 = l + ( r - l ) / 3 ; m2 = r - ( r - l ) / 3 ; ha ( f ( m1 ) < f ( m2 )) l = m1 ; más r = m2 ; }

Lásd még