Ternärsökning

En ternärsökning är en teknik inom datavetenskap för att söka efter minimum eller maximum av en unimodal funktion (d.v.s. en funktion där detta minimum eller maximum är unikt). En ternärsökning avgör i vilken halva max- eller min-punkten befinner sig, och halverar sedan upprepat intervallet tills tillräcklig precision har uppnåtts. Det är ett exempel på en söndra och härska-algoritm.

Algoritmen

Låt f(x) vara en unimodal funktion definierad på intervallet [i, j], med ett unikt maximum. Betrakta två punkter m₁ och m₂ sådana att i < m₁ < m₂ < j.

Till exempel kan vi välja m₁ = i + (j - i)/3, m₁ = j - (j - i)/3, eller m₁ = (i + j)/2, m₁ = (i + j)/2 + 1.

Då finns två alternativ:

Om f(m₁) < f(m₂) så finns extrempunkten i intervallet [m₁ , j].

Om f(m₁) > f(m₂) så finns extrempunkten i intervallet [i, m₂].

I båda fallen kan vi reducera intervallets storlek med en konstant faktor, och upprepa.

Tidskomplexitet

I ett diskret intervall bestående av $n$ punkter, där m₁ och m₂ väljs som tredjedelar av intervallet, kommer körningstiden av algoritmen ges av

$T(n)=T(2n/3)+O(1)$

om $f$ tar konstant tid att beräkna. Enligt mästarsatsen ger detta en tidskomplexitet på $\Theta (\log n)$

Rekursiv algoritm

def ternarySearch(f, left, right, absolutePrecision):
    '''
    left and right are the current bounds; 
    the maximum is between them
    '''
    if abs(right - left) < absolutePrecision:
        return (left + right)/2

    leftThird = (2*left + right)/3
    rightThird = (left + 2*right)/3

    if f(leftThird) < f(rightThird):
        return ternarySearch(f, leftThird, right, absolutePrecision) 
    else:
        return ternarySearch(f, left, rightThird, absolutePrecision)

Iterativ algoritm

def ternarySearch(f, left, right, absolutePrecision):
    """
    Find maximum of unimodal function f() within [left, right]
    To find the minimum, reverse the if/else statement or reverse the comparison.
    """
    while True:
        #left and right are the current bounds; the maximum is between them
        if abs(right - left) < absolutePrecision:
            return (left + right)/2

        leftThird = left + (right - left)/3
        rightThird = right - (right - left)/3

        if f(leftThird) < f(rightThird):
            left = leftThird
        else:
            right = rightThird

Se även

• Newtons metod inom optimering (kan användas för att hitta ett nollställe av derivatan)
• Gyllene snittet-sökning (väldigt lik ternärsökning, användbar om f är dyr att beräkna)
• Binärsökning (can be used to search for where the derivative changes in sign)
• Interpolationssökning
• Exponentiell sökning
• Linjärsökning
• n-dimensionell ternärsökningsimplementation