Algoritmos gulosos

Com atividades $A=[0,3)$, $B=[1,2)$ e $C=[2,4)$, escolher a que começa mais cedo seleciona apenas $A$. Escolher a que termina mais cedo seleciona $B$ e depois $C$, com duas atividades em vez de uma. O exemplo mostra que a regra de escolha decide o resultado. Um algoritmo guloso fixa uma escolha sem a desfazer e resolve o que resta com a mesma regra.

Para justificar a regra, é preciso provar que existe uma solução ótima compatível com essa escolha e que o problema restante conserva a mesma estrutura. Uma instância onde a regra funciona não prova a regra. Uma instância onde falha refuta-a.

Seleção de atividades

Cada atividade tem início $s_i$ e fim $f_i$, com $s_i<f_i$. Uma pessoa faz atividades sem sobreposição e quer maximizar a quantidade. Usamos intervalos $[s_i,f_i)$, pelo que uma atividade pode começar no instante em que a anterior termina.

A regra é ordenar por fim crescente e aceitar a primeira atividade compatível com a última escolhida. O fim mais cedo deixa pelo menos tanto tempo livre como qualquer alternativa para continuar, o que torna plausível que a escolha não prejudique o resto. A prova abaixo confirma essa intuição.

Para $A=[0,3)$, $B=[1,2)$, $C=[2,4)$, $D=[3,5)$ e $E=[4,6)$, a ordem por fim é $B,A,C,D,E$. Escolhemos $B$, rejeitamos $A$ por ser incompatível, escolhemos $C$, rejeitamos $D$ e escolhemos $E$. O resultado tem três atividades.

Prova por troca

Seja $a$ a atividade de fim mais cedo e $O$ uma solução ótima. Ordena as atividades de $O$ por tempo e chama $b$ à primeira. Como $f_a\le f_b$, substituir $b$ por $a$ mantém a compatibilidade com todas as atividades seguintes. A quantidade não muda. Existe, portanto, uma solução ótima que começa por $a$.

Depois de escolher $a$, o resto é o mesmo problema restrito às atividades que começam a partir de $f_a$. Se o resto escolhido não fosse ótimo, podíamos substituí-lo por um melhor e melhorar a solução completa. As escolhas são ótimas por indução sobre o número de atividades.

A ordenação custa $O(n\log n)$ e a passagem custa $O(n)$. Se a entrada já estiver ordenada por fim, o custo é $O(n)$. Empates no fim podem ser resolvidos por qualquer ordem válida, sem alterar a garantia.

Escolher o início mais cedo falha com $[0,10)$, $[1,2)$ e $[2,3)$: escolhe uma atividade em vez de duas. Escolher a duração mais curta também não tem esta prova. Se cada atividade tiver um valor diferente e o objetivo for somar valores, maximizar a quantidade é outro problema e pode exigir programação dinâmica.

Carga em ordem e blocos contíguos

Uma sequência de caixas com pesos $[6,4,5,5]$ tem de ser carregada nessa ordem em camiões de capacidade 10. Só um camião recebe caixas de cada vez. Enchemos o primeiro com $6+4$ e o segundo com $5+5$: dois camiões. Mandar o primeiro embora depois do 6 deixaria três blocos $[6]$, $[4,5]$ e $[5]$, com um camião a mais.

Assume $0<p_i\le W$ para cada caixa, capacidade $W$ igual em todos os camiões, sem reordenar nem repartir caixas. A regra coloca no camião atual o maior prefixo do que falta cuja soma cabe. Quando a próxima caixa já não cabe, abre outro camião. Uma passagem custa $\Theta(n)$ e guarda apenas a carga atual e o número de camiões, além das fronteiras se forem pedidas.

A prova acompanha a fronteira de cada bloco. Seja $g_j$ a última caixa carregada pelos primeiros $j$ camiões gulosos e $o_j$ a última de qualquer outra solução válida. O primeiro bloco guloso é o maior prefixo que cabe, logo $g_1\ge o_1$. Supondo $g_{j-1}\ge o_{j-1}$, há dois casos. Se $g_{j-1}\ge o_j$, o guloso já passou essa fronteira. Caso contrário, as caixas de $g_{j-1}+1$ até $o_j$ são um sufixo do bloco $j$ da outra solução. Como os pesos são positivos, esse sufixo também cabe num camião. O guloso coloca pelo menos essas caixas e fica $g_j\ge o_j$.

Assim, se uma solução acaba em $q$ camiões, $o_q=n$ e o guloso também já acabou até ao camião $q$. A regra minimiza o número de camiões. A hipótese da ordem é essencial: se pudermos reordenar $[6,6,4,4]$, dois camiões com $6+4$ chegam, enquanto a regra sobre essa ordem usa três.

Mochila fracionária

Aqui cada objeto é divisível. Com peso $w_i>0$, valor $v_i\ge0$ e fração $x_i\in[0,1]$, queremos maximizar $\sum_i v_i x_i$ sujeito a $\sum_i w_i x_i\le W$. A densidade $v_i/w_i$ é o valor por unidade de peso.

Ordena por densidade decrescente. Leva cada objeto inteiro enquanto couber. Quando um não cabe, leva a fração que preenche a capacidade restante.

Com $A=(6,12)$, $B=(5,9)$, $C=(5,9)$ e capacidade 10, levamos $A$ inteiro e $4/5$ de $B$. O peso é $6+4=10$ e o valor é $12+7{,}2=19{,}2$.

A prova troca peso, não objetos inteiros. Se uma solução leva peso de um objeto menos denso enquanto ainda pode levar mais do mais denso, troca uma quantidade $\varepsilon$ do primeiro para o segundo. A capacidade mantém-se e o valor não diminui. Repetindo, existe uma solução ótima que enche primeiro os objetos mais densos. A ordenação dá $O(n\log n)$ tempo.

Na mochila 0-1, a troca fracionária é proibida. No mesmo exemplo, o guloso leva $A$ e fica com valor 12, enquanto levar $B$ e $C$ dá 18. A hipótese de divisibilidade era necessária.

Poucas exceções numa mochila 0-1

Na mochila 0-1, assume pesos positivos e valores não negativos. Se apenas $k$ objetos têm peso excecional e os restantes $n-k$ partilham o mesmo peso $w$, enumera os $2^k$ subconjuntos excecionais. Rejeita os que excedem $W$ e completa cada um com os regulares de maior valor que cabem.

Ordena os regulares por valor decrescente uma vez e guarda somas de prefixos. Para capacidade restante $R$, cabem $q=\min(n-k,\lfloor R/w\rfloor)$ objetos. A soma dos primeiros $q$ valores dá em $O(1)$ a melhor conclusão desse ramo: trocar um escolhido por outro de maior valor conserva o peso e não piora o resultado. Com leitura da entrada e até $k$ operações por subconjunto, o custo é $O(n\log(n+1)+2^k(k+1))$. Para $k$ fixo, o fator exponencial é constante.

Se os regulares tiverem valor igual, mas pesos diferentes, a escolha muda: ordena-os por peso crescente e leva o maior prefixo que cabe. Qualquer seleção de $q$ objetos pesa pelo menos tanto como os $q$ mais leves. Encontrar o maior prefixo pelas somas acumuladas custa $O(\log(n+1))$ por ramo, por pesquisa binária. O total é $O(n\log(n+1)+2^k(k+\log(n+1)))$.

Quando peso e valor dos regulares são ambos iguais, já não há ordenação: calcula diretamente quantos cabem. A pesquisa pode custar $O(2^k(k+1))$ depois de ler e confirmar os $n$ objetos. O custo total inclui $\Omega(n)$. Uma tabela em $W$ não é necessária nestes casos. Se outra parte regular exigisse DP em capacidade binária, o resultado poderia ser apenas pseudopolinomial.

Trocos e condições do sistema

Escolher a maior moeda que cabe pode falhar mesmo com stock ilimitado e moeda de valor 1. Com denominações 1, 3 e 4 e alvo 6, escolhe $4+1+1$, três moedas. O ótimo é $3+3$, duas.

Um sistema é canónico se esse guloso devolve o mínimo de moedas para todo o alvo com stock ilimitado. Não basta as denominações estarem ordenadas. Mesmo um sistema canónico ilimitado pode precisar de outra estratégia quando há stocks finitos. Um algoritmo deve distinguir “não consegui completar com esta regra” de “não existe solução”.

Ordem de serviço

Há $n$ clientes disponíveis desde o início, um servidor e tempos positivos $p_i$. Sem interrupções, queremos minimizar a soma dos tempos de conclusão. É equivalente a minimizar a espera total, porque a soma dos tempos de serviço é fixa.

A regra é servir por duração crescente. Para durações 4, 1 e 3, a ordem inicial tem conclusões 4, 5 e 8, soma 17. A ordem 1, 3, 4 tem conclusões 1, 4 e 8, soma 13.

Para provar, considera dois clientes adjacentes $a$ e $b$, depois de um prefixo de duração $P$. Na ordem $a,b$, a contribuição é $(P+p_a)+(P+p_a+p_b)$. Na ordem $b,a$, é $(P+p_b)+(P+p_b+p_a)$. A primeira menos a segunda é $p_a-p_b$. Se $p_a>p_b$, trocar reduz o total e não muda os clientes posteriores. Eliminar inversões produz a ordem crescente.

A duração total até terminar todos é sempre $\sum p_i$, pelo que não é esse total que a regra minimiza. Com tempos de chegada, prioridades ou pesos de espera, o modelo e a prova mudam.

Huffman e códigos sem prefixos

Um código binário é sem prefixos se o código de nenhum símbolo é prefixo do código de outro. Podemos representá-lo por uma árvore binária com símbolos nas folhas. A profundidade de uma folha é o comprimento do seu código.

Para frequências $f_i$, queremos minimizar $\sum_i f_i\ell_i$, o número total de bits. Huffman retira repetidamente da heap os dois nós de menor frequência, cria um pai com a soma das frequências e volta a inseri-lo.

Com frequências $a:5$, $b:7$, $c:10$, $d:15$, junta 5 e 7 em 12. Junta 10 e 12 em 22. Junta 15 e 22 em 37.

Um código é $d=0$, $c=10$, $a=110$, $b=111$. O custo é $15\cdot1+10\cdot2+5\cdot3+7\cdot3=71$ bits. Somar os pesos dos nós criados também dá $12+22+37=71$, pois cada fusão acrescenta um bit aos símbolos abaixo dela.

Por que juntar os dois mínimos

Numa árvore ótima, escolhe duas folhas irmãs de profundidade máxima. Trocar símbolos para colocar ali os dois menos frequentes não aumenta o custo: se uma frequência menor passa para uma profundidade maior enquanto a maior sobe, a variação é não positiva. Existe, assim, uma árvore ótima em que os dois mínimos são irmãos.

Contrai os dois numa folha de frequência $f_a+f_b$. O custo da árvore original é o custo da contraída mais $f_a+f_b$. Se a árvore contraída não fosse ótima, substituí-la por uma melhor melhoraria a original. A fusão é uma escolha segura e reduz o problema.

A heap dá $O(n\log n)$ tempo e $O(n)$ espaço. Empates podem produzir códigos diferentes com o mesmo custo. Com um único símbolo, a árvore teria profundidade zero. Um formato de ficheiro real deve definir como representar repetições desse símbolo, por exemplo com um código de um bit e comprimento explícito. A árvore sozinha não define todo o formato de compressão.