Upload
paulotiago
View
21
Download
0
Embed Size (px)
DESCRIPTION
Teoria dos Grafos - Aula 14 - Grad UERN - 19-01-2015 - Matching
Citation preview
Prof. Dario José Aloise
Teoria dos GrafosEstudo de Problemas Clássicos
Mossoró, 19 de janeiro de 2015
DEPARTAMENTO DE INFORMÁTICA
PROBLEMAS CLÁSSICOS
Árvore Geradora Mínima
Caminho mais Curto
Matching ou emparelhamento
Coloração
Caixeiro Viajante
Roteamento de Veículos
Emparelhamento( Matching )
MATCHING OU EMPARELHAMENTO
Definição: Um matching em um grafo G é um conjunto de arestas que não
formam loops e que não compartilham vértices entre si.
Exemplo:
Um vértice incidente às arestas de um matching M é dito saturado por M.
Um matching perfeito de G satura todos os vértices de G.
MATCHING OU EMPARELHAMENTO
O tamanho de um matching M é igual a quantidade de arestas de M.
Um matching M de um grafo G é maximal se toda aresta que não participa
de M é incidente a alguma aresta em M.
Se M for o matching de maior cardinalidade de G então ele é chamado
matching máximo.
MATCHING OU EMPARELHAMENTO Um caminho alternante em um matching M é um caminho cujas arestas alternam entre
aquelas que estão em M e aquelas que não estão em M.
Um caminho alternante, cujos vértices extremos não são saturados por M, é um
caminho de aumento de M.
Quando M possuir um caminho de aumento P podemos trocar as arestas deste
caminho, substituindo aquelas que não estão em M pelas que estão. Isto irá aumentar
em uma (1) unidade o tamanho do matching.
Observação: o matching máximo é caracterizado pela ausência de caminhos de
aumento.
MATCHING OU EMPARELHAMENTO
Matching Máximo X Matching Maximal
Um matching M é máximo se não existe um matching M' tal que |M‘ | > |M |.
A propósito, um matching M é maximal se não existe um matching M' do qual M
faça parte própria (portanto, M é maximal se não existe aresta a fora de M tal
que M+{a } também é um matching).
MATCHING OU EMPARELHAMENTO
Observação: A prova de ambos os teoremas pode ser encontrada em http://www.cos.ufrj.br/~celina/cos742/jai99.pdf
FUNDAMENTAÇÃO TEÓRICA
Teorema 1 (Berge, 1957): Um matching M tem cardinalidade máxima em G se
e somente se G não possui caminho M-aumentante.
Teorema 2 (Hall, 1956): Seja G um grafo bipartido com bipartição X, Y . Então
G admite matching que satura todo vértice de X se e somente se |N(S)| |S|,
para todo S X.
Corolário 1: Seja G um grafo bipartido com bipartição X , Y. Então G admite matching
perfeito se e somente se |X| = |Y | e |N(S)| |S|, para todo S X.
Corolário 2: Um grafo bipartido tem um matching perfeito se e somente se |N(S)| |S|,
para todo S V .
Matching Perfeito
Dado um grafo G= (V,E), o problema de matching é encontrar o matchingmáximo de G. Quando a cardinalidade do matching é V 2 , afirmamos que o matching é completo ou perfeito [PAPADIMITRIOU (1998)]. Isto é todos os vértices estão casados. Em grafos bipartidos G=(U,V,E), devemos ter V = U para que um matching perfeito possa existir.
Ref.: Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization: Algorithms and
Complexity, Publisher: Dover Publications; Unabridged edition ,1998. 9
MATCHING OU EMPARELHAMENTO
MATCHING OU EMPARELHAMENTO
PRINCIPAIS ALGORITMOS:
Algoritmo Húngaro (Grafos bipartidos sem pesos)
Algoritmo de Kuhn (Grafos bipartidos com pesos)
Algoritmo de Edmonds (Caso geral sem pesos)
Observação: Maiores detalhes sobre os algoritmos pode ser encontrado em:
http://www.cos.ufrj.br/~celina/cos742/jai99.pdf
MATCHING OU EMPARELHAMENTO
APLICAÇÕES:
Problema de atribuição de pessoal
Dados n funcionários e n posições numa empresa. Cada funcionário está qualificado
para uma ou mais posições. É possível atribuir uma posição a cada funcionário, de
modo que cada funcionário ocupe exatamente uma posição na empresa? O objetivo
é encontrar uma atribuição ou uma alocação que maximize a eficiência total dos
funcionários.
Problema dos casamentos
Dada uma matriz onde cada entrada é 0 ou 1, um conjunto de entradas é independente se
não temos duas entradas na mesma linha ou na mesma coluna. Pede-se encontrar um
conjunto independente de entradas de valor 1 que tem cardinalidade máxima. Podemos
interpretar as linhas da matriz como sendo rapazes e as colunas como sendo moças. Uma
entrada i, j com valor 1 seria o caso de rapaz e moça compatíveis. O objetivo é casar um
número máximo de casais compatíveis.
MATCHING OU EMPARELHAMENTO
APLICAÇÕES: Problema de construção de amostras
Um vendedor de brinquedos educativos possui em estoque brinquedos de várias
formas geométricas (cubos, pirâmides, etc.), cada qual fabricado em várias cores.
O vendedor quer carregar consigo o menor número de objetos tal que cada cor e
cada forma estejam representadas pelo menos uma vez.
Observação: Com base nesta aplicação pode-se provar a equivalência entre o
problema de cobertura de cardinalidade mínima e o problema de emparelhamento
de cardinalidade máxima.
OUTROS PROBLEMAS
Alocação de tarefas
Elaboração de Horários
K-servos
Empacotamento
Clique máxima
Cobertura de Vértices
OTIM-SPT
Um exemplo de Aplicação
Otimização do Corte do Layout : Ênfase na Indústria de Confecções
MCC - Teoria dos Grafos 14
UM EXEMPLO DE APLICAÇÃO
Otimização do Corte do Layout na
Indústria de Confecções
Objetivo
Encontrar uma seqüência ótima de corte daspeças do enfesto, de forma a minimizar odeslocamento total (ou percurso) do braçomecânico (robô) que efetua o corte e atendero mais rápido possível o setor de montagem.
Processo de Produção
Exemplo de enfesto...
Problema do Encaixe
Um exemplo de Layout
Figura sem os rótulos
Aplicação de Grafos
Problema de Percurso:
O início dos Problemas de Roteamento em Arcos
Leonhard Euler (1736) - Publicou o primeiro artigo em grafos
C
As pontes de Königsberg e o multigrafo associado.
BA
D
Construindo um Grafo Euleriano
Teorema - O número de vértices ímpares de qualquer grafo conexo é par.
Edmonds & Johnson (1973) propôs
Algoritmo 1-Matching
Complexidade: O ( n³ )
Problema de Matching
Problema do Carteiro Chinês:===
O Problema do Carteiro Chinês é um problema de roteamento
onde se pretende achar um percurso fechado (circuito) de
comprimento mínimo que passa por cada aresta de um grafo pelo
menos uma vez.=====================================
(b)
11
22
33
4455
66
88 77
Formulação Matemática do PCC:
,
. :
0 ( 1, )
1 ,
0 e inteiro ,
ij ij
i V j V
ij ji
j V j V
ij ji
ij
Min Z c x i j
s a
x x i V
x x ij E
x ij E
cij = custo de percorrer a aresta ij ;
xij = número de vezes que a aresta ij é percorrida de i para j.
Inter-relacionamento entre Matching e o PCC:
Algoritmo do Carteiro Chinês [Edmonds (1973)
Matching Perfeito
Abordagem Exata:
Continuação:
Formulação Matemática do Problema do Layout :
1
1
1 1 1 1
( )( )
( )( )
{ , }
. . :
0 , p/
( ) ( ) 0 , p/
1 , ,
, {0,1}
O O
O O
V VV V
ij ij rs rs
i j r s
ik kj E
j ki k
ik rk kj ks O
r V j k s Vi k
ij ji
ij ij
Min Z l x d y i j r s
s a
x x k V
x y x y k V
x x i j V
x y
Abordagem Heurística:
• O método exato embora forneça a solução ótimado problema quanto a minimizar o percurso(tempo) de corte das peças no layout, do pontode vista prático,não satisfaz a condição deatender o mais rápido possível o setor demontagem.
• O objetivo inclui, portanto, a prioridade de cortar peças inteiras com a finalidade acima.
• O problema passa agora a ser semelhante ao do Carteiro Rural, o qual é NP-difícil.
Heurísticas Propostas:
HEURÍSTICA I
(sem prioridade de aresta ou vértice)
Dados iniciais
1. Posição original do braço mecânico,
2. LAYOUT desenhado, com dimensões e referências,
3. GRAFO ASSOCIADO;
ETAPA 0 – PROCEDIMENTOS DE INICIALIZAÇÃO
Iniciar de um vértice qualquer no grafo G=(V,E,c), denominando-o de ATIVO.
ETAPA 1 – LAÇO DE CONTINUIDADE
ENQUANTO existir vértice de grau
Ø FAÇA
1. Percorrer cortando a maior aresta associada ao vértice ATIVO
1. SE encontrar um vértice de grau Ø, ENTÃO
Procurar o vértice ativo (vértice com alguma aresta associada) mais
próximo ao vértice de grau Ø (zero) .
SENÃO FINALIZE.
FIM DO ENQUANTO
HEURÍSTICA 2
(com prioridade: vértice denso por arestas)
Dados iniciais
Posição original do braço mecânico,
LAYOUT desenhado, com dimensões e referências,
GRAFO ASSOCIADO;
ETAPA 0 – PROCEDIMENTOS DE INICIALIZAÇÃO
Iniciar de um vértice qualquer denso por arestas no grafo G=(V,E,c),
denominado de vértice ATIVO.
ETAPA 1 – LAÇO DE CONTINUIDADE
REPITA
ENQUANTO existir aresta em ATIVO FAÇA
Percorrer cortando uma aresta de maior custo associada ao vértice ATIVO.
Fixar ou tornar em evidência a figura (peça) de menor índice associada a
aresta citada.
Cortar a figura (peça) em evidência, totalmente
FIM DO ENQUANTO
Procurar por um vértice mais próximo, denominado-o de ATIVO (não
necessariamente percorrendo pelas arestas do Grafo – Problema do Carteiro
Rural).
ATÉ G=Ø;
HEURÍSTICA 3
(com prioridade: vértice denso por figuras)
Dados iniciais
Posição original do braço mecânico,
LAYOUT desenhado, com dimensões e referências,
GRAFO ASSOCIADO;
ETAPA 0 – PROCEDIMENTOS DE INICIALIZAÇÃO
Iniciar de um vértice qualquer denso, isto é, com um a quantidade razoável de
figuras (peças) associadas no grafo G=(V,E,c), denominando-o de ATIVO.
ETAPA 1 – LAÇO DE CONTINUIDADE
REPITA
ENQUANTO existir figura associada ao vértice ATIVO FAÇA
Percorrer cortando uma figura (peça), iniciando o corte pela aresta de maior
custo associada a ela.
SE existir mais de uma figura associada a essa aresta, ENTÃO
considerar em primeiro lugar aquela de menor índice.
SE grau(ATIVO) = 0 e existir figura parcialmente cortada, ENTÃO procurar
por um vértice mais próximo dentre aqueles pertencentes as figuras
associadas ao vértice ATIVO e continuar o percurso de corte a partir desse
novo vértice até que a figura fique totalmente cortada.
FIM DO ENQUANTO
SE grau (vértice ATUAL 0 ), ENTÃO faça ATUAL = ATIVO.
SENÃO procurar por um vértice de grau 0 mais próximo do vértice
atual.
ATÉ QUE G = Ø;
Pós-otimização:Caso 1 - O braço mecânico termina o procedimento de corte e volta ao ponto de partida (origem). Então
a solução ótima permanecerá como a do Carteiro Chinês sobre o grafo Euleriano. E o matching perfeito
de peso mínimo refletirá fielmente o deslocamento adicional mínimo do braço mecânico (robô).
Caso 2 - O robô ao terminar a última peça a ser cortada não retorna ao ponto de origem. Então
deveremos comparar e retirar a maior das arestas encontradas pelo matching perfeito de peso mínimo e
aquela maior aresta encontrada por um dos diversos matching maximais, mas de tal forma que a
contribuição para o deslocamento do robô fique a menor possível. Isto implica na seguinte formulação
matemática para esta situação de parada do robô:
1 2
1 2min maxiji i
ij
c i i
( *)c
Conclusões e Sugestões:
Esta pesquisa teve por mérito mostrar o quanto é
importante também o corte do Encaixe ou Layout do
enfesto na Indústria de confecções;
A verificação que o ótimo nem sempre é obtido através
do matching perfeito de peso mínimo;
A apresentação de algoritmos aproximativos polinomiais
para a resolução do problema na prática.
Como sugestão fica o desenvolvimento de um
trabalho que reconheça os pontos do grafo pelo simples
scanneamento do Encaixe.
Restrições:
a faca não pode furar o meio
a faca não pode voltar
bordas com restrições
os retalhos não podem ser cortados
há necessidade de priorizar peças no corte
há restrições para prender o enfesto
a faca não trabalha com grandes angulosidades
etc.
FIM
Reptiles, 1943. MC Escher (1898-1972).