hungaro_print_2012_1

Prévia do material em texto

Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Me´todo Hu´ngaro
Prof. Dr. Leandro Balby Marinho
Ana´lise e Te´cnicas de Algoritmos
Prof. Dr. Leandro Balby Marinho 1 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Roteiro
1. Introduc¸a˜o
2. Problema de Alocac¸a˜o de Tarefas
2. Me´todo Hu´ngaro
Prof. Dr. Leandro Balby Marinho 2 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Introduc¸a˜o
I Adequado a problemas de otimizac¸a˜o Combinato´ria.
I Resolve o problema da alocac¸a˜o em tempo polinomial (normalmente
O(n3)).
I Origem: E. Egerva´ry e D. Ko¨nig (1931)
I Criador: H. Kuhn (1955)
Prof. Dr. Leandro Balby Marinho 2 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Roteiro
1. Introduc¸a˜o
2. Problema de Alocac¸a˜o de Tarefas
2. Me´todo Hu´ngaro
Prof. Dr. Leandro Balby Marinho 3 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Problema de Alocac¸a˜o de Tarefas
I Alocar n agentes para n tarefas tal que o custo total de alocac¸a˜o
seja o menor poss´ıvel.
I Instaˆncias do problema podem ser especificadas por uma matriz de
custo C ∈ Rn×n:
C =

c1,1 c1,2 · · · c1,n
c2,1 c2,2 · · · c2,n
...
...
. . .
...
cn,1 cn,2 · · · cn,n

onde ci,j representa o custo de alocar o agente i para realizar a
tarefa j .
Prof. Dr. Leandro Balby Marinho 3 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Roteiro
1. Introduc¸a˜o
2. Problema de Alocac¸a˜o de Tarefas
2. Me´todo Hu´ngaro
Prof. Dr. Leandro Balby Marinho 4 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Teorema da Alocac¸a˜o O´tima
Teorema 1
Se um nu´mero real e´ somado ou subtra´ıdo de todas as entradas de uma
linha ou coluna, enta˜o uma alocac¸a˜o o´tima para a matriz resultante e´
tambe´m uma alocac¸a˜o o´tima para a matriz original.
Ao diminuir as linhas e colunas, estamos comparando-as com
valores relativos.
Prof. Dr. Leandro Balby Marinho 4 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 1
Uma soluc¸a˜o o´tima para a matriz abaixo seria: c1,2, c2,1 e c3,3
C =
 900 750 750350 850 550
1250 950 900

Subtraindo a menor entrada de cada linha temos:
C =
150 0 00 500 200
350 50 0

Note que a soluc¸a˜o o´tima continua a mesma e e´ representada pelas
entradas com custo 0.
Prof. Dr. Leandro Balby Marinho 5 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Teorema de Ko¨nig
Teorema 2
Se o nu´mero m´ınimo de trac¸os que atravessam todos os zeros for n,
temos uma alocac¸a˜o poss´ıvel para cada linha/coluna.
C =
150 0 00 500 200
350 50 0

Prof. Dr. Leandro Balby Marinho 6 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Algoritmo
1. Para cada linha, subtraia o m´ınimo da linha.
2. Para cada coluna, subtraia o m´ınimo da coluna.
3. Use o m´ınimo de trac¸os poss´ıveis para cobrir todos os zeros da
matriz. Na˜o ha´ receita de bolo para isso – basicamente tentativa e
erro. Se voceˆ usou k trac¸os:
I Se j = n, temos uma soluc¸a˜o o´tima. Escolha um 0 por linha e
coluna.
I Se j 6= n, determine a menor entrada que na˜o tenha sido
riscada. Subtraia essa entrada de todas as entradas na˜o
riscadas e a some a todas as entradas com 2 riscos (Volta ao
passo 3).
Prof. Dr. Leandro Balby Marinho 7 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 1 cont.
Passo 1: Para cada linha, subtraia o m´ınimo da linha.
C =
 900 750 750350 850 550
1250 950 900

C =
150 0 00 500 200
350 50 0

Prof. Dr. Leandro Balby Marinho 8 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 1 cont.
Passo 2: Para cada coluna, subtraia o m´ınimo da coluna.
C =
150 0 00 500 200
350 50 0

Como o m´ınimo de cada coluna e´ 0, a matriz permanece a mesma nesse
passo.
C =
150 0 00 500 200
350 50 0

Prof. Dr. Leandro Balby Marinho 9 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 1 cont.
Passo 3: Cubra cada 0 com o m´ınimo de trac¸os
C =
150 0 00 500 200
350 50 0

Como n = 3 trac¸os, temos uma soluc¸a˜o o´tima.
C =
150 0 00 500 200
350 50 0

Prof. Dr. Leandro Balby Marinho 10 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 1 cont.
Soluc¸a˜o: Escolha um 0 por linha e coluna
C =
150 0 00 500 200
350 50 0

C =
 900 750 750350 850 550
1250 950 900

Total = 750 + 350 + 900 = 2000
Prof. Dr. Leandro Balby Marinho 11 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 2
Considere a matriz abaixo:
Pos 1 Pos 2 Pos 3
Jogador 1 4 2 4
Jogador 2 2 2 3
Jogador 3 3 1 5
Se voceˆ fosse um te´cnico de um time com sala´rios atrasados e quisesse
sabotar o time. Como escalar um time para que ele tenha a maior chance
de perder?
Prof. Dr. Leandro Balby Marinho 12 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 2 cont.
Passo 1: Para cada linha, subtraia o m´ınimo da linha.
C =
4 2 42 2 3
3 1 5

C =
2 0 20 0 1
2 0 4

Prof. Dr. Leandro Balby Marinho 13 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 2 cont.
Passo 2: Para cada coluna, subtraia o m´ınimo da coluna.
C =
2 0 20 0 1
2 0 4

C =
2 0 10 0 0
2 0 3

Prof. Dr. Leandro Balby Marinho 14 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 2 cont.
Passo 3: Cubra cada 0 com o m´ınimo de trac¸os.
C =
2 0 20 0 1
2 0 4

Como n = 2 trac¸os, subtraia a menor entrada na˜o riscada de todas as
outras.
C =
1 0 00 1 0
1 0 2

Prof. Dr. Leandro Balby Marinho 15 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 2 cont.
Repete Passo 3: Cubra cada 0 com o m´ınimo de trac¸os.
C =
1 0 00 1 0
1 0 2

C =
1 0 00 1 0
1 0 2

Prof. Dr. Leandro Balby Marinho 16 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 2 cont.
Soluc¸a˜o: Escolha um 0 por linha e coluna.
C =
1 0 00 1 0
1 0 2

C =
4 2 42 2 3
3 1 5

Total = 4 + 2 + 1 = 7
Prof. Dr. Leandro Balby Marinho 17 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Problemas de Maximizac¸a˜o
I Da forma como foi apresentado, o me´todo hu´ngaro resolve
apenas problemas de minimizac¸a˜o.
I Como resolver problemas de maximizac¸a˜o sem alterar o
algoritmo?
Multiplicar por −1 a matriz de custo.
Prof. Dr. Leandro Balby Marinho 18 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 3
Considere a matriz abaixo:
Pos 1 Pos 2 Pos 3
Jogador 1 4 2 4
Jogador 2 2 2 3
Jogador 3 3 1 5
Se voceˆ fosse um te´cnico de um time e soubesse a qualidade de cada
jogador em cada posic¸a˜o. Como escalar um time para que ele seja o mais
forte poss´ıvel?
Prof. Dr. Leandro Balby Marinho 19 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 3 cont.
Passo 0: Multiplica a matriz por −1.
C =
4 2 42 2 3
3 1 5

C =
−4 −2 −4−2 −2 −4
−3 −1 −5

Prof. Dr. Leandro Balby Marinho 20 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 3 cont.
Passo 1: Para cada linha, subtraia o m´ınimo da linha.
C =
−4 −2 −4−2 −2 −4
−3 −1 −5

C =
0 2 01 1 0
2 4 0

Prof. Dr. Leandro Balby Marinho 21 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 3 cont.
Passo 2: Para cada coluna, subtraia o m´ınimo da coluna.
C =
0 2 01 1 0
2 4 0

C =
0 1 01 0 0
2 3 0

Prof. Dr. Leandro BalbyMarinho 22 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 3 cont.
Passo 3: Cubra cada 0 com o m´ınimo de trac¸os.
C =
0 1 01 0 0
2 3 0

Como n = 3 trac¸os, temos uma soluc¸a˜o o´tima.
C =
0 1 01 0 0
2 3 0

Prof. Dr. Leandro Balby Marinho 23 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Exemplo 3 cont.
Soluc¸a˜o: Escolha um 0 por linha e coluna.
C =
0 1 01 0 0
2 3 0

C =
4 2 42 2 3
3 1 5

Total = 4 + 2 + 5 = 11
Prof. Dr. Leandro Balby Marinho 24 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Matriz Na˜o-Quadrada
I Quando houver mais agentes (ou vice-versa) que tarefas ainda
podemos aplicar o me´todo hu´ngaro.
I Nesse caso, adicione tarefas (ou agentes) fictA˜cias de custo 0
de modo que a matriz de custo seja quadrada.
Prof. Dr. Leandro Balby Marinho 25 / 26 UFCG CEEI
Introduc¸a˜o Alocac¸a˜o de Tarefas Me´todo Hu´ngaro
Refereˆncias
Slides Prof. Tiago Massoni e Prof. Rohit Gheyi.
Prof. Dr. Leandro Balby Marinho 26 / 26 UFCG CEEI
	1. Introdução
	2. Problema de Alocação de Tarefas
	2. Método Húngaro