Heurísticas e Metaheurísticas 02

Prévia do material em texto

ENP557 –Heur. e Metaheurísticas
Aula 02 – Heurísticas Construtivas
HEURÍSTICAS CONSTRUTIVAS
 Heurísticas Construtivas são heurísticas que, dado
apenas os parâmetros de um problema, conseguem
encontrar uma solução viável em tempo polinomial
 Somente a viabilidade é garantida
 Entretanto, espera-se que este algoritmo seja
projetado de modo a almejar soluções cujo custo esteja
próximo ao da solução ótima do problema
ALGORITMOS GULOSOS
 Técnica mais simples e mais utilizada
 Parte de uma solução parcial (vazia)
 Adiciona ou remove, sequencialmente, elementos da
solução através de um critério guloso estabelecido
 Retorna uma solução viável ao final da rotina iterativa
BIN PACKING 1-D PROBLEM
BIN PACKING 1-D PROBLEM
 Dado um conjunto de itens 𝑖 = 1,2,3,… , 𝑛 com
diferentes volumes 𝑎1, 𝑎2, 𝑎3, … 𝑎𝑛 que devem ser
empacotados em um número finito de caixas de
capacidade 𝑉, o objetivo do problema é minimizar o
número de caixas utilizadas
BIN PACKING 1-D PROBLEM
BIN PACKING 1-D PROBLEM
 Heurística First-Fit Decreasing (FFD)
 Os itens são organizados em ordem decrescente
 O item é inserido na primeira caixa que o comporta
 Caso não exista espaço nas caixas disponíveis, uma
nova caixa é criada
BIN PACKING 1-D PROBLEM
BIN PACKING 1-D PROBLEM
BPP –ESTRUTURAS NECESSÁRIAS
ITEM CAIXA
 Index
 Peso
 Se o item já foi alocado
 Capacidade restante
 Quantidade de itens
 Itens alocados
BPP –ESTRUTURAS NECESSÁRIAS
ITEM CAIXA
MINIMUM COVER PROBLEM
MINIMUM COVER PROBLEM
 Dada uma coleção finita 𝑆 de conjuntos finitos,
dizemos que uma subcoleção Τ de 𝑆 cobre um conjunto
finito 𝐸 se todo elemento de 𝐸 pertence a algum
conjunto de Τ
 Neste caso, dizemos também que Τ é uma cobertura
de 𝐸
MINIMUM COVER PROBLEM
 Um caso particular do problema da cobertura é o
problema de cobertura por arestas
 Neste problema, dado um grafo 𝐺 = 𝑉, 𝐴 , e um custo
𝑐𝑎 para cada aresta 𝑎 ∈ 𝐴, desejamos encontrar um
subconjunto Τ de arestas de 𝐴 de custo mínimo de
forma que todo vértice de 𝑉 seja atingido por ao menos
uma aresta de Τ
 Neste caso, dado 𝐺 = 𝑉, 𝐴 , temos que 𝐸 é o conjunto
de vértices de um grafo 𝐸 = 𝑉 , 𝑆 é o conjunto de
arestas 𝑆 = 𝐴 e 𝑐𝑆 é o custo das arestas 𝑐𝑆 = 𝑐𝑎
MINIMUM COVER PROBLEM
MINIMUM COVER PROBLEM
 Heurística Cobertura Máxima
 Atribuir a cada vértice o seu índice de cobertura
(quantidade de arestas cobertas)
 Inserir o vértice disponível com o maior índice de
cobertura
 Excluir vértices que não contenham arestas não
cobertas
 Repetir passo 2
MINIMUM COVER PROBLEM
b
e
a
MCP –ESTRUTURAS NECESSÁRIAS
PONTO ARESTAS
 Index
 Se o ponto foi selecionado
 Ponto 01
 Ponto 02
 Se a aresta é coberta
MCP –ESTRUTURAS NECESSÁRIAS
PONTO ARESTAS