Busca ternária

Recebemos uma função $f(x)$ que é unimodal em um intervalo $[l, r]$. Por função unimodal, queremos dizer que ela pode ter um dos dois comportamentos

  1. A função primeiro aumenta estritamente, atinge o máximo (em um único ponto ou durante um intervalo) e depois estritamente vai diminuindo.

  2. A função primeiro diminui estritamente, atinge o mínimo e depois aumenta estritamente.

Neste artigo, assumiremos o primeiro cenário. O segundo cenário é completamente simétrico ao primeiro.

A tarefa é encontrar o máximo da função $f(x)$ no intervalo $[l, r]$.

Algoritmo

Considere 2 pontos $m_1$ e $m_2$ no intervalo: $l < m_1 < m_2 < r$. Avaliamos a função em $m_1$ e $m_2$, ou seja, encontramos os valores de $f(m_1)$ e $f(m_2)$. Agora, temos uma das três opções:

Assim, com base na comparação dos valores nos dois pontos internos, podemos substituir o intervalo atual $[l, r]$ por um novo intervalo mais curto $[l^\prime, r^\prime]$. Aplicando repetidamente o procedimento descrito ao intervalo, podemos obter um intervalo arbitrariamente curto. Eventualmente, seu comprimento será menor que uma determinada constante predefinida (precisão) e o processo poderá ser interrompido. Este é um método numérico, portanto, podemos assumir que, depois disso, a função alcance seu máximo em todos os pontos do último intervalo modificado $[l, r]$. Sem perda de generalidade, podemos ter $f(l)$ como o valor de retorno.

Não impusemos restrições à escolha dos pontos $m_1$ e $m_2$. Essa escolha definirá a taxa de convergência e a precisão da implementação. A maneira mais comum é escolher os pontos para que eles dividam o intervalo $[l, r]$ em três partes iguais. Assim, teremos

$$m_1 = l + \frac{(r - l)}{3}$$

$$m_2 = r - \frac{(r - l)}{3}$$

Se $m_1$ e $m_2$ forem escolhidos para serem próximos, a taxa de convergência aumentará um pouco.

Análise do tempo de execução

$$T(n) = T({2n}/{3}) + 1 = \Theta(\log n)$$

Ele pode ser visualizado da seguinte forma: toda vez que avaliamos a função nos pontos $m_1$ e $m_2$, estamos basicamente ignorando cerca de um terço do intervalo, o esquerdo ou o direito. Portanto, o tamanho do espaço de pesquisa é ${2n}/{3}$ do espaço original.

Aplicando o teorema mestre, obtemos a estimativa de complexidade desejada.

O caso dos argumentos inteiros

Se $f(x)$ usar inteiros como parâmetro, o intervalo $[l, r]$ se tornará discreto. Como não impusemos restrições à escolha dos pontos $m_1$ e $m_2$, a certeza do algoritmo não é afetada. Ainda é possível escolher $m_1$ e $m_2$ para dividir $[l, r]$ em três partes aproximadamente iguais.

A diferença ocorre no critério de parada do algoritmo. A busca ternária terá que parar quando $(r - l) < 3$, porque nesse caso não podemos mais selecionar $m_1$ e $m_2$ para serem diferentes entre si, bem como entre $l$ e $r$, e isso pode causar um loop infinito. Depois que $(r - l) < 3$, o restante de escolhas para os pontos $(l, l + 1, \ldots, r)$ precisa ser verificado para encontrar o ponto que produz o valor máximo de $f(x)$.

Implementação

double ternary_search(double l, double r) {
    double eps = 1e-9;              //definir o erro limite
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //avalia a função em m1
        double f2 = f(m2);      //avalia a função em m2
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    //retorna o máximo de f(x) em [l, r]
}

Aqui, eps é, de fato, o erro absoluto (sem levar em conta erros devido ao cálculo impreciso da função).

Em vez do critério r - l > eps, podemos selecionar um número constante de iterações como critério de parada. O número de iterações deve ser escolhido para garantir a precisão necessária. Normalmente, na maioria dos desafios de programação, o limite de erros é ${10}^{-6}$ e, portanto, 200 - 300 iterações são suficientes. Além disso, o número de iterações não depende dos valores de $l$ e $r$; o número de iterações corresponde ao erro relativo necessário.

Problemas