A seguir está uma versão em Markdown do conteúdo do PDF, preservando a estrutura de slides, títulos e listas para facilitar processamento posterior (por exemplo em Quarto, MkDocs, Obsidian ou pipelines de LLM). O texto foi extraído do documento ****.
Vou apresentar uma versão limpa e estruturada, mantendo títulos e conteúdo.
BCC402 – Algoritmos e Programação Avançada
Prof. Marco Antonio M. Carvalho Prof. Túlio Ângelo M. Toffolo 2011/1
Departamento de Computação (DECOM)
Na aula anterior
- Programação Dinâmica
Na aula de hoje
- Algoritmos Gulosos
Problemas Combinatórios
Problemas combinatórios são problemas em que:
- Uma solução é a combinação de um subconjunto de elementos.
- O espaço de busca é o conjunto de todas as soluções possíveis.
- Esse espaço pode incluir soluções viáveis ou inviáveis.
Objetivos
As soluções de um problema combinatório são avaliadas de acordo com um objetivo.
O objetivo pode ser representado por uma expressão matemática.
As variáveis da expressão representam os elementos do espaço de busca.
O objetivo pode ser:
- Maximizar a função objetivo
- Minimizar a função objetivo
Restrições
Problemas combinatórios possuem restrições que definem quais soluções são válidas.
- Uma solução que respeita todas as restrições é chamada viável.
- Uma solução que viola restrições é chamada inviável.
Exemplo: Problema da Mochila
Dada:
- uma mochila com capacidade C
- n objetos (x_i)
cada objeto possui peso (p_i)
Objetivo:
Preencher a mochila com maior peso total possível, respeitando a capacidade (C).
Modelagem Matemática
Variáveis:
- (x_i )
onde:
- (x_i = 1) se o objeto está na solução
- (x_i = 0) caso contrário
Função objetivo:
[ _{i=1}^{n} p_i x_i]
Restrição:
[ _{i=1}^{n} p_i x_i C]
Exemplo numérico
Suponha:
- (C = 15)
- (n = 4)
Pesos:
| objeto | peso |
|---|---|
| p1 | 12 |
| p2 | 2 |
| p3 | 4 |
| p4 | 8 |
Espaço de Busca
O espaço de busca consiste em todas as combinações possíveis de objetos.
Exemplo de soluções:
- (x_1)
- (x_2)
- (x_1 x_2 x_3 x_4)
- (x_2 x_3 x_4)
- (x_2 x_4)
etc.
Soluções
Uma solução ótima é:
- uma solução viável
- que maximiza ou minimiza a função objetivo.
Pode existir:
- uma única solução ótima
- várias soluções ótimas
Vizinhança
Durante a busca por soluções:
- podemos mover de uma solução para outra
- duas soluções que diferem por um movimento são chamadas vizinhas
Ótimo Local x Ótimo Global
Ótimo global
- melhor solução considerando todo o espaço de busca
Ótimo local
- melhor solução dentro da vizinhança
Um ótimo local não é necessariamente o ótimo global.
Métodos Exatos e Heurísticos
Métodos Exatos
- Sempre encontram a solução ótima global
Porém:
- podem ser muito caros computacionalmente
Métodos Heurísticos
Geram soluções boas, mas:
- não garantem optimalidade
Vantagens:
- geralmente mais rápidos
Métodos Aproximados
- possuem garantia matemática de proximidade da solução ótima
Problemas Difíceis
Problemas como NP-completos possuem desafios:
- não é possível explorar todo o espaço de busca
- precisamos usar heurísticas
Algoritmos Gulosos
Algoritmos gulosos:
- tomam a melhor decisão local em cada passo
Características:
- fazem escolhas miopes
- escolhem sempre o ótimo local
Em alguns casos:
- isso leva ao ótimo global
Propriedades
Algoritmos gulosos:
- não reconsideram decisões
- não realizam busca exaustiva
Diferente de:
- backtracking
Estrutura de um Algoritmo Guloso
Um algoritmo guloso geralmente possui:
- Conjunto de opções
- Critério guloso
- Função de viabilidade
- Função objetivo
- Função de solução
Processo Geral
Inicialmente:
- solução = conjunto vazio
A cada passo:
- Escolher o melhor elemento
- Verificar se é viável
- Se viável → adicionar
- Senão → descartar
Parar quando a solução estiver completa.
Aplicações de Algoritmos Gulosos
Exemplos clássicos:
Árvores Geradoras Mínimas
- Prim
- Kruskal
Caminho mínimo
- Dijkstra
Cobertura de conjuntos
- Chvátal
Subestrutura Ótima
Um problema possui subestrutura ótima quando:
- a solução ótima pode ser construída a partir das soluções ótimas de subproblemas
Isso permite resolver o problema incrementalmente.
Árvores Geradoras
Dado um grafo:
[ G = (V,E)]
Uma árvore geradora:
- conecta todos os vértices
- não possui ciclos.
Árvore Geradora Mínima
Uma árvore geradora mínima:
- minimiza a soma dos pesos das arestas
Aplicação:
- planejamento de redes
- infraestrutura de cabos
- redes elétricas
Algoritmo de Prim
Algoritmo guloso que:
- inicia em um vértice
- adiciona sempre a aresta de menor peso disponível
Processo:
Escolher um vértice inicial
Enquanto existirem vértices fora da árvore:
- escolher a aresta de menor peso conectando a árvore a um novo vértice
Algoritmo de Kruskal
Outro algoritmo guloso.
Processo:
- Ordenar arestas pelo peso
- Selecionar arestas em ordem crescente
- Adicionar a aresta se não formar ciclo
Cobertura de Conjuntos
Dado:
- um conjunto (X)
- uma família de subconjuntos (F)
Objetivo:
Encontrar um subconjunto de (F) que cubra todos os elementos de (X).
Projeto de Algoritmos Gulosos
Aspectos importantes:
- definir um critério guloso adequado
- usar operações eficientes
- escolher estruturas de dados apropriadas
Vantagens
- simplicidade
- implementação fácil
- bom desempenho em vários problemas
Desvantagens
- não garantem solução ótima
- dependem muito do critério guloso escolhido
Observação
Deve-se olhar para um algoritmo guloso como um detetive, e não apenas como um matemático.
Próxima Aula
- Práticas
Fim
Se quiser, posso também gerar:
1️⃣ uma versão ainda melhor para LLM/RAG (com separação por seções e metadados) 2️⃣ uma versão Quarto (.qmd) pronta para gerar slides 3️⃣ um markdown com todas as imagens preservadas do PDF 4️⃣ um dataset estruturado por slide (ótimo para IA educacional).