Ternärsökning

Från Wikipedia
Hoppa till navigering Hoppa till sök

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[redigera | redigera wikitext]

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

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

Då finns två alternativ:

Om f(m1) < f(m2) så finns extrempunkten i intervallet [m1 , j].

Om f(m1) > f(m2) så finns extrempunkten i intervallet [i, m2].

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

Tidskomplexitet

I ett diskret intervall bestående av punkter, där m1 och m2 väljs som tredjedelar av intervallet, kommer körningstiden av algoritmen ges av

om tar konstant tid att beräkna. Enligt mästarsatsen ger detta en tidskomplexitet på

Rekursiv algoritm[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

  • 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