Exercícios resolvidos: divisão e conquista além dos exemplos clássicos

Explicação

Correspondência com a busca binária

A trilha não é um vetor ordenado, mas a resposta da abelha impõe uma ordem espacial:

• BEE_LEFT elimina o ponto central e todas as posições à direita;
• BEE_RIGHT elimina o ponto central e todas as posições à esquerda;
• NEST_FOUND encerra a busca.

O invariante é: se o ninho ainda não foi encontrado, sua posição permanece em [begin, end).

Atualização do intervalo

Se a abelha voar para a esquerda, a nova região é [begin, middle), portanto end = middle.

Se ela voar para a direita, a nova região é [middle + 1, end), portanto begin = middle + 1.

Rastreamento para o ninho na posição 731

[0, 1024), middle = 512  → direita
[513, 1024), middle = 768 → esquerda
[513, 768), middle = 640  → direita
[641, 768), middle = 704  → direita
[705, 768), middle = 736  → esquerda
[705, 736), middle = 720  → direita
[721, 736), middle = 728  → direita
[729, 736), middle = 732  → esquerda
[729, 732), middle = 730  → direita
[731, 732), middle = 731  → encontrado

Foram necessárias 10 solturas nesse caso. O limite de 11 também cobre as posições menos favorecidas pela escolha do ponto central.

Uma tentativa sequencial poderia precisar de 1.024 solturas para alcançar a última posição. A redução pela metade limita a busca a 11 solturas neste simulador.

Resposta esperada

static int locate_nest(int begin, int end) {
    while (begin < end) {
        const int middle = (begin + end) / 2;
        const BeeDirection direction = release_bee(middle);

        if (direction == NEST_FOUND) {
            return middle;
        }

        if (direction == BEE_LEFT) {
            end = middle;
        } else {
            begin = middle + 1;
        }
    }

    return -1;
}

A implementação completa está em ninho_abelhas_solucao.c. Ela localiza todos os ninhos testados, mantém o intervalo semiaberto e respeita o limite de 11 solturas.

No pior caso do intervalo fornecido, a busca sequencial usa até 1.024 solturas, enquanto a redução sucessiva usa no máximo 11.

Explicação

Região possível

No início, qualquer janela pode conter a sala:

x_min = 0
x_max = W - 1
y_min = 0
y_max = H - 1

Esses quatro valores descrevem um retângulo. A cada resposta do detector, uma parte desse retângulo deixa de ser possível.

Atualização horizontal

• Se a direção contém L, a sala está à esquerda: x_max recebe x_atual - 1.
• Se a direção contém R, a sala está à direita: x_min recebe x_atual + 1.
• Se não existe L nem R, a coluna já está determinada: os dois limites recebem x_atual.

Atualização vertical

• Se a direção contém U, a sala está acima: y_max recebe y_atual - 1.
• Se a direção contém D, a sala está abaixo: y_min recebe y_atual + 1.
• Se não existe U nem D, a linha já está determinada: os dois limites recebem y_atual.

Uma resposta diagonal contém uma informação horizontal e outra vertical. Por exemplo, UL permite podar simultaneamente as janelas à direita e as janelas abaixo da posição atual.

Escolha da próxima janela

Depois de atualizar os limites, escolha o centro da região restante:

próximo_x = (x_min + x_max) / 2
próximo_y = (y_min + y_max) / 2

No estado fornecido, UL produz:

x possível: [6, 8]
y possível: [2, 5]

Com divisão inteira:

próximo_x = (6 + 8) / 2 = 7
próximo_y = (2 + 5) / 2 = 3

A próxima janela é (7, 3).

O programa precisa manter os limites entre os turnos. Recomeçar com o edifício inteiro apagaria o conhecimento obtido nas respostas anteriores.

Resposta esperada

1. Representar as posições possíveis pelo retângulo inclusivo [x_min, x_max] × [y_min, y_max].
2. Usar L e R para reduzir o eixo horizontal, e U e D para reduzir o eixo vertical.
3. Fixar um eixo na coordenada atual quando a resposta não possui letra referente a esse eixo.
4. Escolher o centro do retângulo restante como próxima janela.
5. Para o estado fornecido, obter x ∈ [6, 8], y ∈ [2, 5] e próxima janela (7, 3).
6. Justificar que regiões incompatíveis com a direção são descartadas sem inspeção individual. A quantidade de turnos cresce de forma logarítmica em relação às dimensões do edifício.

Explicação

Primeira divisão

Os quadrantes de tamanho 2 × 2 são:

superior esquerdo:  0 0    uniforme → 0
                    0 0

superior direito:   1 1    uniforme → 1
                    1 1

inferior esquerdo:  0 1    não uniforme
                    0 0

inferior direito:   1 1    uniforme → 1
                    1 1

O quadrante inferior esquerdo precisa ser dividido novamente. Seus quatro pixels, na ordem definida, são 0, 1, 0 e 0. Sua codificação é (0100).

Ao combinar os quatro resultados da raiz, obtemos:

(01(0100)1)

Por que todas as partes continuam

Uma região não uniforme não informa qual quadrante é dispensável. Cada quadrante contém pixels que precisam aparecer na representação final. Portanto, as quatro chamadas continuam e seus resultados são concatenados entre parênteses.

Estrutura da divisão e conquista

• Dividir: separar a região em quatro quadrantes.
• Resolver: codificar recursivamente os quatro quadrantes.
• Combinar: colocar as quatro codificações, na ordem definida, entre parênteses.
• Encerrar: escrever uma única cor quando a região for uniforme. Uma região de um pixel sempre satisfaz esse caso.

Subdividir uma região já uniforme criaria chamadas que repetiriam a mesma cor. Isso aumentaria o trabalho e produziria uma representação maior sem preservar informação adicional.

Custo no pior caso

Para uma região de lado n, a verificação de uniformidade examina $n^2$ pixels. Se nenhuma região maior for uniforme, surgem quatro subproblemas de lado $n/2$:

Como cada nível examina, ao todo, os $n^2$ pixels e existem $\log_2 n$ níveis:

Resposta esperada

1. Os quadrantes superior esquerdo, superior direito e inferior direito são uniformes e produzem 0, 1 e 1. O quadrante inferior esquerdo não é uniforme.
2. A codificação completa é (01(0100)1).
3. Nenhum quadrante pode ser descartado porque todos contêm pixels que participam da representação final.
4. A solução deve verificar a uniformidade, encerrar em regiões uniformes e fazer quatro chamadas recursivas para regiões não uniformes.
5. A combinação deve preservar a ordem superior esquerdo, superior direito, inferior esquerdo e inferior direito.
6. Com a verificação fornecida, o pior caso é $\Theta(n^2\log n)$ para uma imagem de lado n.
7. Uma região uniforme deve encerrar a recursão porque um único símbolo já representa todos os seus pixels.

A implementação completa está em compressao_quadtree_solucao.c. Ela imprime:

Codificação: (01(0100)1)