Algoritmos gulosos

Regra e prova

Fixa escolha sem desfazer. Prova que algum ótimo admite essa escolha e que o resto conserva a estrutura. Um exemplo correto não prova a regra; um contraexemplo refuta-a.

Atividades e serviço

• Atividades: ordena por fim crescente; aceita se $s_i\ge f_{\text{última}}$. Custo $O(n\log n)$, ou $O(n)$ se ordenado.
• Trocar primeira de ótimo pela de fim mais cedo conserva compatibilidade.
• Início mais cedo e duração mais curta falham. Com valores por atividade, é outro problema.
• Servidor: todos disponíveis, tempos $p_i>0$; serve por duração crescente. Trocar adjacentes $a,b$ com $p_a>p_b$ reduz soma em $p_a-p_b$. Total até terminar todos continua $\sum p_i$.

Blocos contíguos

Caixas $0<p_i\le W$, sem reordenar nem dividir. Leva maior prefixo que cabe; abre outro quando próxima não cabe. Custo $\Theta(n)$.

Fronteira gulosa $g_j\ge o_j$ após $j$ camiões, por indução com sufixo de peso positivo. Sem ordem fixa, a prova cai.

Mochila e trocos

• Fracionária: $w_i>0$, $x_i\in[0,1]$; ordena por $v_i/w_i$ e enche, com fração do último. Troca de peso para maior densidade nunca reduz valor. $O(n\log n)$.
• 0-1: troca proibida. Com $(6,12),(5,9),(5,9)$ e $W=10$, densidade dá 12 e $B+C$ dá 18.
• $k$ exceções: enumera $2^k$ subconjuntos excecionais; completa regulares por valor (peso igual) ou por peso (valor igual). Para $k$ fixo, polinomial sem tabela em $W$.
• Trocos: maior que cabe só é ótimo em sistema canónico ilimitado. Com 1,3,4 e alvo 6, dá $4+1+1$ em vez de $3+3$. Stock finito pode invalidar regra mesmo em canónico.

Huffman

Símbolos nas folhas; custo $\sum f_i\ell_i$.

1. Heap com frequências.
2. Retira dois mínimos, cria pai com soma, reinsere.
3. Repete até uma raiz.

Fusões $5+7=12$, $10+12=22$, $15+22=37$; custo $12+22+37=71$. Existe ótimo com dois mínimos como irmãos mais profundos; contrair reduz sem perder otimalidade. Heap dá $O(n\log n)$. Empates mudam códigos sem mudar custo. Um símbolo exige convenção explícita no formato.

Provas e variantes.