Heurísticas e Metaheurísticas 03

Prévia do material em texto

TRAVELLING SALESMAN PROBLEM
TRAVELLING SALESMAN PROBLEM
 Sendo um grafo 𝐺 = 𝑁, 𝐸 no qual 𝑁 = 1,… , 𝑛 é o
conjunto de nós e 𝐸 = 1,… ,𝑚 é o conjunto de
arestas de 𝐺, com custos 𝑐𝑖𝑗 associados a cada aresta
que liga o vértice 𝑖 ao vértice 𝑗, o problema consiste em
localizar o ciclo hamiltoniano no grafo 𝐺 , tal que
σσ𝑐𝑖𝑗𝑥𝑖𝑗 é mínimo
TRAVELLING SALESMAN PROBLEM
TRAVELLING SALESMAN PROBLEM
 Heurística Ponto mais Próximo
 Selecionar arbitrariamente um ponto inicial
 Dentre os pontos ainda não visitados, ir para o ponto
mais próximo
 Após visitar todos os pontos, retornar ao ponto inicial
TRAVELLING SALESMAN PROBLEM
TRAVELLING SALESMAN PROBLEM
TSP –ESTRUTURAS NECESSÁRIAS
PONTO CAMINHO
 Index
 Endereço (x,y)
 Se o ponto já foi visitado
 Ponto atual
 Próximo ponto
 Distância até próximo ponto
TSP –ESTRUTURAS NECESSÁRIAS
PONTO CAMINHO
HEURÍSTICAS DE ARREDONDAMENTO
 Necessita maior conhecimento em otimização
 Parte de uma solução inicial relaxada
 Utiliza valores iniciais como critério de decisão
 Retorna uma solução viável ao final da rotina
HEURÍSTICAS DE ARREDONDAMENTO
 Abordagem básica
 Formular o problema como um PLI
 Obter uma solução fracionada do problema resolvendo
sua relação linear (PL)
 Gerar uma solução inteira (parcial ou integral) através
da solução obtida pela relação linear por meio de
arredondamentos
HEURÍSTICAS DE ARREDONDAMENTO
PLI PL
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
 Abordagem básica
 Formular o problema como um PLI
 Obter uma solução fracionada do problema resolvendo
sua relaxação linear (PL)
 Gerar uma solução inteira (parcial ou integral) através
da solução obtida pela relação linear por meio de
arredondamentos
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
 Abordagem básica
 Formular o problema como um PLI
 Obter uma solução fracionada do problema resolvendo
sua relaxação linear (PL)
 Gerar uma solução inteira (parcial ou integral) através
da solução obtida pela relação linear por meio de
arredondamentos
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
 Abordagem básica
 Formular o problema como um PLI
 Obter uma solução fracionada do problema resolvendo
sua relaxação linear (PL)
 Gerar uma solução inteira (parcial ou integral) através da
solução obtida pela relação linear por meio de
arredondamentos
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
CONGESTION MINIMIZATION PROBLEM
TRAVELLING SALESMAN PROBLEM
 Abordagem básica
 Formular o problema como um PLI
 Obter uma solução fracionada do problema resolvendo
sua relação linear (PL)
 Gerar uma solução inteira (parcial ou integral) através
da solução obtida pela relação linear por meio de
arredondamentos
TRAVELLING SALESMAN PROBLEM
TRAVELLING SALESMAN PROBLEM
TRAVELLING SALESMAN PROBLEM
TRAVELLING SALESMAN PROBLEM
→𝟔 𝟓 𝟖 𝟐 𝟒 𝟑 𝟏 𝟏𝟎 𝟗 𝟕 𝟔→ → → → → → → → →
FUNÇÃO OBJETIVO → 53,9
TRAVELLING SALESMAN PROBLEM
FUNÇÃO OBJETIVO → 49,9
→𝟔 𝟕 𝟏𝟎 𝟗 𝟓 𝟖 𝟏 𝟐 𝟑 𝟔→ → → → → → → → →𝟒
TRAVELLING SALESMAN PROBLEM
Qual resultado é melhor? Por que?
Depende do que você vai fazer depois!
TRAVELLING SALESMAN PROBLEM
ARREDONDAMENTO (53,9) HEURÍSTICA GULOSA (49,9)
TRAVELLING SALESMAN PROBLEM
SOLUÇÃO ÓTIMA (47,3) HEURÍSTICA GULOSA (49,9)
TRAVELLING SALESMAN PROBLEM
SOLUÇÃO ÓTIMA (47,3) ARREDONDAMENTO (53,9)
HEURÍSTICAS DE REDUÇÃO
 Uma redução é a transformação de um problema em
outro
 O problema A é redutível em B se
 Existe um modo de transformar uma instância de A em
uma instância de B
 Transformar a solução ótima de B em uma solução
ótima de A
HEURÍSTICAS DE REDUÇÃO
 A abordagem a ser utilizada é
 Transformar a instância do problema A em uma
instância do problema B
 Resolver o problema B com algum algoritmo específico
 Construir uma solução para A através da solução obtida
para o problema B
MAXIMUM CLIQUE PROBLEM
MAXIMUM CLIQUE PROBLEM
 Um clique em um grafo não direcionado G = (V, E) é um
subconjunto de vértices C ⊆ V, tal que para cada dois
vértices em C, existe uma aresta os conectando. Isso se
equivale a dizer que um subgrafo induzido de C é
completo (em alguns casos, o termo clique também
pode ser referência ao subgrafo)
MAXIMUM CLIQUE PROBLEM
 Um clique máximo é o maior clique possível em um
dado grafo. O número do clique ω(G) de um grafo G é o
número de vértices de um clique máximo em G. O
número da intersecção de G é o menor número de
cliques que, juntos, cobrem todas as arestas de G
MAXIMUM CLIQUE PROBLEM
MAXIMUM CLIQUE PROBLEM
 Embora a pesquisa por força bruta possa ser melhorada
através de algoritmos mais eficientes, estes algoritmos
possuem tempo exponencial de resolução
 Portanto, grande parte da teoria sobre o problema do
clique é dedicado à identificação de tipos especiais de
grafo que admitem algoritmos mais eficientes, ou a
definição da dificuldade computacional do problema
geral em vários modelos de computação
MAXIMUM CLIQUE PROBLEM
 O oposto de um clique é um conjunto independente,
no sentido de que cada clique corresponde a um
conjunto independente no grafo complementar
 O problema de calcular um conjunto independente faz
parte do conjunto de problemas NP-C, e é chamado de
Independent Set Problem (ISP)
INDEPENDENT SET PROBLEM
INDEPENDENT SET PROBLEM
 Na teoria dos grafos, um conjunto independente de um
grafo G é um conjunto S de vértices de G tal que não
existem dois vértices adjacentes contidos em S
 Em outras palavras, se 𝑎 e 𝑏 são vértices quaisquer de
um conjunto independente, não há aresta entre 𝑎 e 𝑏
CLIQUE → INDEPENDENT SET
CLIQUE → INDEPENDENT SET
CLIQUE → INDEPENDENT SET
INDEPENDENT SET PROBLEM
 Um modo eficiente de resolver um ISP é utilizando o
conjunto complementar da solução de um problema de
MCP
INDEPENDENT SET →MAXIMUM COVER 
MAXIMUM CLIQUE PROBLEM
 Deste modo, um método para resolver um CLIQUE é
definido por
 Reduzir a instancia de CLIQUE em uma instancia de ISP
 Resolver o problema de ISP através do conjunto
complementar do problema de MCP
 Obter a resposta de CLIQUE através do resultado
obtido ao resolver ISP
MAXIMUM CLIQUE PROBLEM
CLIQUE → INDEPENDENT SET
CLIQUE → INDEPENDENT SET
INDEPENDENT SET →MAXIMUM COVER 
INDEPENDENT SET →CLIQUE