Kolminkertainen haku

Kolminkertainen haku (Ternary search)  on tietojenkäsittelytieteellinen menetelmä löytää maksimi ja minimi funktiolle , joka joko ensin tiukasti lisää , sitten tiukasti laskee tai päinvastoin. Kolmiosainen haku määrittää, että minimi tai maksimi ei voi olla alueen ensimmäisessä tai viimeisessä kolmanneksessa, ja toistaa sitten haun kahdella jäljellä olevalla kolmanneksella. Kolminkertainen haku osoittaa " hajoita ja hallitse " -ohjelmointiparadigman.

Toiminto

Oletetaan, että etsimme funktion f ( x ) maksimiarvoa ja tiedämme, että maksimi on A:n ja B :n välillä . Jotta algoritmi olisi sovellettavissa, x :n täytyy olla jokin arvo , joka

Algoritmi

/** Löytää maksimin funktiolle, jossa yksi ääripää on välillä l ja r. Minimi löytyy vaihtamalla toiminnot if/else-haaroissa. */ kaksinkertainen l = ..., r = ..., EPS = ...; // syötetiedot double m1 , m2 ; while ( r - l > EPS ) { m1 = l + ( r - l ) / 3 ; m2 = r- ( r - l ) / 3 ; _ jos ( f ( m1 ) < f ( m2 )) l = m1 ; muu r = m2 ; }

Katso myös