Anais do 13O Encontro de Iniciação Científica e Pós-Graduação do ITA – XIII ENCITA / 2007
Instituto Tecnológico de Aeronáutica, São José dos Campos, SP, Brasil, Outubro, 01 a 04, 2007.
ALGORITMOS DE OTIMIZAÇÃO COMBINATÓRIA
Henry Wei Cheng Hsu
Instituto Tecnológico de Aeronáutica, Praça Marechal Eduardo Gomes, 50 -Vila das Acácias – S. J. dos Campos
Bolsista PIBIC-CNPq
[email protected]
Nei Yoshiriro Soma
Instituto Tecnológico de Aeronáutica, Praça Marechal Eduardo Gomes, 50 -Vila das Acácias – S. J. dos Campos
[email protected]
Resumo. O artigo apresentará diversas situações em que os algoritmos de otimização combinatória se mostram de especial
utilidade. Além disso será apresentada a modelagem de problemas, uma tarefa de extrema importancia que muitas vezes necessita
de grande criativadade.
Palavras chave: Algoritmo, Otimização ,Combinatória ,Grafo, Programação Dinâmica
1. Introdução
Os algoritmos de otimização combinatória se mostram de extrema importância para a computação. Eles
permitem a análise e otimização de situações em um número muito grande de áreas de aplicação. Alguns poucos
exemplos são: redes sociais, mapeamento genético, rotas de aviação, sistemas de comunicação, gerenciamento de
estoque, bancos de dados, entre muitos outros.
Nessa iniciação científica, propôs-se o estudo de algoritmos que abrangem a teoria dos grafos, programação
dinâmica e teoria dos números. Além disso, foi necessária uma familiarização com linguagens de programação e com
estrutura de dados.
No decorrer do ano letivo da iniciação científica houve muito progresso nos estudos e implementação de
algoritmos. Ocorreu o estudo teórico de algoritmos nas áreas de teoria dos grafos, programação dinâmica, e teoria dos
números. Além disso, houve muita prática na implementação de algoritmos e também uma atividade muito importante
que é a modelagem e resolução de problemas de diversas áreas através de algoritmos de otimização.
Uma atividade paralela altamente proveitosa é a participação na “ACM Internacional Collegiate Programming
Contest”. Junto com os alunos de graduação do Instituto Tecnológico de Aeronáutica Hélder Suzuki e Cesário Martins,
foi formado uma equipe para a participação nessa competição. A preparação para o evento envolveu reuniões semanais,
a resolução e implementação de dezenas de questões de competições passadas, disponíveis no web site
http://acm.uva.es [5], além do estudo de algoritmos, de técnicas de resolução e da utilização da criatividade para a
resolução de problemas.
É de extrema importância o conhecimento dos algoritmos de otimização. No entanto, em diversas apliações
apenas o uso destes algoritmos não é suficiente. É necessário antes modelar a situação e adaptá-la para o uso de
algoritmos conhecidos. Essa tarefa, na maioria das vezes, é bastante difícil. Justamente por esse motivo, ela se torna a
mais interessante e a mais intrigante para os estudiosos de computação.
Nesse relatório serão apresentadas pequenas situações a serem solucionadas. Algoritmos de otimazação serão
utilizados. Porém o enfoque da solução será nas idéias utilizadas para a modelagem da questão. Após a descrição de
cada situação será feito um breve comentário. Em seguida será apresentada a solução, estas contendo idéias que as
tornam belas e elegantes.
2.Situação
Uma indústria fabrica copos plásticos de três tamanhos (pequeno, médio e grande) e os vende em diferentes
tipos de pacotes. Cada tipo de pacote é identificado por três inteiros positivos (S1, S2, S3) em que Si denota a quantidade
de copos de tamanho i no pacote. No entanto, nunca ocorre S1 =S2 =S3. Deseja-se juntar uma quantidade de pacotes tal
que exista o mesmo número de copos dos três tamanhos. Por exemplo, se houver 4 tipos de pacotes: (1, 2, 3), (1, 11, 5),
(9, 4, 3) e (2, 3, 2). É possível juntar três pacotes do tipo (1, 2, 3), um do tipo (9, 4, 3) e dois do tipo (2, 3, 2). Dessa
forma obtém-se 16 copos de cada tipo. Dadas a quantidade de tipos de pacotes e as suas configurações, deseja-se
determinar se é possível obter a mesma quantidade de copos dos três tamanhos.
2.1.Comentário
A princípio a questão se encaixa na área de Teoria dos Números. No entanto a resolução apresentada a seguir
toma outro caminho, utilizando-se apenas de argumentos geométricos, tornando-a particularmente elegante.
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
2.2.Solução
Para cada tripla, considere o par ordenado definido da seguinte forma (S1, S2, S3) → (S2-S1, S3-S1). Obtêm-se
os N pares ordenados correspondentes aos trios ordenados iniciais. O problema equivalente torna-se: juntar uma
determinada quantidade de pares ordenados de cada tipo para obter o par (0,0) como resultado. Para o prosseguimento
da resolução, será feita a definição de fecho convexo.
O fecho convexo de um conjunto Q de pontos é o menor polígono convexo P para o qual cada ponto em Q está
no limite de P ou em seu interior.
Considere cada par ordenado como um vetor no plano R2. Deseja-se saber se é possível somar os vetores (é
permitido repetir o mesmo vetor) para que a resultante total seja nula. A seguir será mostrada uma maneira de responder
essa questão.
Traça-se o fecho convexo dos N pontos. Se a origem estiver no interior do fecho, a resposta da questão é
afirmativa, caso contrário a resposta é negativa.
Se a origem estiver fora do fecho convexo, é possível traçar uma reta de forma que todos os vetores estão em
um mesmo semi-plano definido pela reta.
y
x
Fig 1 – A origem está fora do fecho convexo, logo qualquer resultante dos vetores estará em um dos semi-planos
definido acima, portanto a resultante nunca será nula.
A resultante pertence ao mesmo semi-plano dos N vetores, portanto nunca é nula.
Para o caso em que a origem está contida no fecho convexo deve-se prosseguir da seguinte maneira: escolher
três pontos tal que o triângulo formado contém a origem. É possível obter a resultante nula apenas com estes três
vetores.
(a,b)
(0,0)
(e,f)
(g,h)
(c,d)
Fig 2 – A origem está contida no triângulo formado pelos pontos (a,b), (c,d) e (e,f)
As coordenadas (a,b), (c,d) e (e,f) são inteiras. Por geometria analítica, é fácil verificar que (g,h) possui
coordenadas racionais. Adotando pesos racionais para os pontos (c,d) e (e,f) e somando-os é possível obter o ponto
(g,h). Multiplicando (g,h) por um peso racional anula-se o vetor (a,b). Logo, é possível escolher pesos racionais para
cada um dos vetores (a,b), (c,d) e (e,f) e obter a resultante (0,0).
Como conclusão, se a origem está contido no fecho convexo dos N pontos, a resposta do problema é
afirmativa.
Para passar essa resolução para uma linguagem de programação são necessários dois algoritmos muito
importantes. O primeiro é determinar o fecho convexo de um conjunto Q de pontos. O outro é a verificação de um
ponto estar contido em um polígono convexo. A seguir será apresentado o pseudo-código dos dois algoritmos.
Fecho convexo: A varredura de Graham
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
O procedimento mantém uma pilha S de pontos candidatos. A função TOP(S) retorna o ponto no topo da pilha
S sem alterar S. NEXT-TO-TOP(S) retorna o ponto no topo da pilha S sem alterar S.
GRAHAM-SCAN(Q)
1- Seja p0 o ponto mais à esquerda dentre os pontos em Q com coordenada y mínima
2- Sejam(p1,p2,...,pm) os pontos restantes em Q, ordenados por ângulo polar em ordem da direita para a esquerda
em torno de p0 (se mais de um ponto tiver o mesmo ângulo, remova todos eles, exceto o mais afastado de p0)
3- PUSH(p0,S)
4- PUSH(p1,S)
5- PUSH(p2,S)
6- para i←3 até m
7do while o ângulo formado pelos pontos NEXT-TO-TOP(S), TOP(S) e pi formar uma volta não à
esquerda
8do POP(S)
9PUSH(pi,S)
10- return (S)
Para verificar se um ponto P está contido em um polígono convexo basta seguir o seguinte procedimento:
traça-se uma semi-reta horizontal do ponto P ao infinito. Se a semi-reta cruzar o polígono uma única vez, o ponto está
contido no polígono. Caso haja dois cruzamentos o ponto está fora do polígono. Como o polígono é convexo, só
existem essas duas possibilidades.
3.Situação
Existem 2n diferentes sequências de n bits. Encontre uma sequência circular em que todas as sequências de n
bits aparecem exatamente uma vez. Por exemplo, para n=2 uma possível resposta é 0011 (pois as subsequências de 2
bits são 00, 01, 11, 10).
3.1.Comentário
Esse problema está relacionado com o dígrafo de De Bruijn. Informações interessantes sobre o assunto podem
ser encontrado no seguinte site:
http://en.wikipedia.org/wiki/De_Bruijn_digraph (acessado em 08/2007) [6].
3.2.Solução
Para a resolução do problema será considerado um grafo auxiliar. Os vértices do grafo são as 2n-1 seqüências
de n-1 bits. Uma aresta direcional é traçada quando os últimos n-2 bits do vértice de origem coincidem com os
primeiros n-2 bits do vértice de chegada. Em cada aresta é marcado uma seqüência de n bits construída da seguinte
forma: o primeiro bit é igual ao primeiro bit do vértice de origem, os próximos n-2 bits são os n-2 bits coincidentes
entre os dois vértices e o último bit é igual ao último bit do vértice de chegada. A Fig. 3 ilustra o grafo auxiliar para o
caso n=3.
Fig. 3 – grafo auxiliar para o caso n=3
É fácil verificar que nas arestas são geradas todas as seqüências de n bits. Outro fato importante é o de que os
n-1 bits finais de uma aresta incidente coincidem com os n-1 bits iniciais de uma aresta de saída.
A seqüência circular desejada pode ser obtida através da determinação de um ciclo Euleriano (um ciclo que
passa por todas as arestas) no grafo auxiliar. Ressalta-se que o ciclo Euleriano sempre existe pelo fato de o grafo de o
grafo ser fortemente conexo e todos os vértices possuírem grau-in igual ao grau-out. A seqüência circular é determinada
da seguinte forma:
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
1- Tome um vértice qualquer do grafo para começar o traçado de um ciclo Euleriano
2- Caminhe por todos os vértices seguindo um ciclo Euleriano. Para cada vértice visitado, adicione o último bit
desse vértice à seqüência.
3- Quando o ciclo terminar temos a seqüência desejada.
Uma possível solução para o caso n=3 é 00111010.
A seguir será apresentado o algoritmo de determinação do ciclo Euleriano, a fim de que a seqüência circular
desejada possa ser obtida com o auxílio de um computador.
EULER-TOUR(G)
1- Inicie com um vértice v0 qualquer do grafo G
2- Caminhe sucessivamente pelas arestas de G, deletando cada aresta de G conforme são percorridas. Não
percorra, em nenhum ponto particular do procedimento, por uma aresta cuja deleção divide o grafo
remanescente de G em duas partes não-vazias.
3- Continue o procedimento até todas as arestas de G serem deletadas, ocasião na qual há o retorno ao vértice v0.
4.Situação
Ao se representar um número na base decimal, são necessários os dígitos de 0 a 9. Se apenas um subconjunto
dos dígitos decimais for permitido, há apenas uma quantidade limitada de números que pode ser representada. Por
exemplo, se apenas os dígitos 1 e 2 forem permitidos, os números 11 e 12 podem ser representados, mas o número 10
não pode. Se os múltiplos de 13 forem listados: 13, 26, 39, ..., 195, 208, 221, etc., percebe-se que 221 é o menor natural
que pode ser representado utilizando somente os dígitos 1 e 2. Questão: Encontre o menor múltiplo de um certo número
N que pode ser representado utilizando somente um dado subconjunto dos dígitos decimais. Esse múltiplo pode ser o
próprio número, mas deve ser maior que zero. Considere N ≤100000. O subconjunto dos dígitos permitidos também é
fornecido.
4.1Comentário
Uma possível solução para o problema é gerar todos os números formados pelo subconjunto de dígitos dados,
e verificar a sua divisibilidade por N. No entanto, esse procedimento toma tempo exponencial. A seguir será
apresentada uma bonita solução que se utiliza da teoria dos grafos.
4.2.Solução
Considere o número decimal a0a1...ak, em que ai pertence ao subconjunto de dígitos permitidos. Adicione o
dígito ak+1 à direita do número. Fatos interessantes:
(a0a1...ak ak+1) = 10 (a0a1...ak) + ak+1 e em particular temos,
(a0a1...ak ak+1) ≡ 10 (a0a1...ak) + ak+1 (mod N)
Tome um grafo cujos vértices são os números de 0 a N-1. O conjunto {b0,..., bp} é o conjunto dos dígitos
permitidos. Uma aresta X→Y é traçada se e somente se ∃ i tal que Y ≡ 10X+bi (mod N).
X
(a0a1...ak) mod N
ak+1
Y
(a0a1...akak+1) modN
Fig. 4 – Ilustração de dois vértices que devem ser unidos por uma aresta
No universo dos números naturais módulo N, X representa o número (a0a1...ak) modN e Y o número (a0a1...ak
ak+1) mod N. Assim, diz-se que Y é gerado por x através de uma aresta do tipo ak+1.
Em um caminho iniciando por um dado vértice, a cada aresta percorrida gera-se um número cuja representação
na base decimal possui um dígito a mais. Se o caminho passar pelo vértice 0, obtém-se um número na base decimal cujo
resto módulo N é igual a zero.
Um pequeno exemplo para ilustração:
Seja {1,2} o conjunto de dígitos permitidos e N=13. Um caminho possível é:
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
2
2
2 mod 13
9
22 mod 13
1
0
221 mod 13
Fig. 5 – Ilustração de um caminho possível
A partir do vértice 2 caminhando por uma aresta do tipo 2, é gerado o número 22, que é equivalente a 9 no
mod 13. De 22 chega-se a 221 por uma aresta do tipo 1. Mas note que 221 é congruente a 0 mod 13.
Antes de prosseguir na resolução da questão, abre-se um parêntesis para um breve comentário sobre o
algoritmo da busca em largura. O BFS (Breadth First Search – busca em largura em inglês) determina o menor caminho
de uma origem a um dado vértice em um grafo não ponderado. Essa busca se mostra muito útil nesse questão, pois
procura-se um número com o menor número de dígitos possível.
A solução da questão pode ser descrita da seguinte maneira:
1- Montar o grafo cujos vértices são os números de 0 a N-1
2- Traçar as arestas conforme descrito anteriormente
3- Para cada i entre 1 e p, executar um BFS de origem bi e alvo o vértice 0. Tomar cuidado para, durante a rotina,
sempre visitar o vizinho cujo tipo de aresta seja o menor possível. Ao encontrar um caminho entre a origem bi
e o vértice 0, armazenar o número decimal obtido.
4- A resposta é o menor dentre os números armazenados.
O BFS encontra um caminho mínimo entre uma origem e o vértice 0 (caso o vértice 0 seja alcançável a partir
dessa origem). Isso significa que o número decimal gerado possui o menor número de dígitos possível. A ordem de
escolha dos vizinhos durante a busca permite que o caminho percorrido indique o menor número dentre aqueles com o
menor número de arestas. Por fim, basta escolher o menor número dentre os encontrados para cada origem.
O algoritmo da Busca em Largura.
BFS(G,s)
1- para cada vértice u ε V[G] – {s}
do cor[u] ← 0
23- cor[s] ← 1
4- Q ← 0
5- ENQUEUE (Q, s)
6- while Q ≠ 0
do u ← DEQUEUE(Q)
7for cada v ← Adj[u]
89do if cor[v] = 0
then cor[v] ← 1
1011ENQUEUE(Q, v)
12cor[u] ← 2
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
5.Situação
Desja-se colocar peças de torre em um tabuleiro de xadrez n x n, de forma que nenhum par de torres se ataque.
Porém, existem algumas casas que estão rachadas, logo não é permitido que nenhuma torre fique nessa casa. Dada as
coordenadas das casas rachadas, determinar o maior números de torres que pode-se colocar no tabuleiro.
1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
Fig 6 – Tabuleiro de xadrez contendo casas rachadas
5.1.Comentário
A solução mais natural para esse problema é a utilização da técnica de backtracking. Porém, o tempo de
execução seria exponencial, o que torna inviável a resolução para dimensões do tabuleiro muito grandes. Para essa
questão será utilizado um importante algoritmo na teoria dos grafo que é o Network Flow.
5.2.Solução
Para a resolução dessa questão é necessária a construção de um grafo de fluxo em rede.
Fig 10 – Ilustração de um possível grafo de fluxo em rede para a questão
O grafo é formado pelo vértices “torneira”, “ralo”, Hi e Vi (1 ≤ i ≤ n). Traça-se arestas da “torneira” a cada
vértice Hi, e arestas de cada Vi ao “ralo”. Traça-se uma aresta entre Hi e Vj se, e somente se a casa (Hi, Vj) do tabuleiro
não estiver rachada. Todas as arestas possuem capacidade 1.
O fluxo máximo entre a “torneira” e o “ralo” é exatamente a quantidade máxima de torres que podem ser
colocadas no tabuleiro.
As arestas entre a “torneira” e os vértices Hi têm capacidade 1, implicando que em cada linha horizontal do
tabuleiro haja no máximo uma torre. Da mesma maneira, As arestas entre o “ralo” e os vértices Vi indicam que há no
máximo uma torre em cada coluna vertical do tabuleiro.
Ao término do algoritmo de fluxo máximo, se uma aresta HiVj possuir fluxo 1, então existe uma torre na casa
(Hi, Vj) do tabuleiro. Note que uma torre nunca cairá em uma casa rachada pois não exite aresta para essa possibilidade.
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
Agora, falta apenas o algoritmo para determinação do fluxo máximo.
FORD-FUKERSON(G, s, t)
1- for cada aresta (u, v) ← E[G]
2-
do f[u, v] ← 0
3-
F[v,u] ← 0
4- while existir um caminho p de s até t na rede residual Gf
do cf(p) ← min{cf(u, v) : (u,v) está em p}
5-
for cada aresta (u, v) em p
6-
do f[u, v] ← f[u, v] + cf(p)
78-
f[v,u] ← - f[u, v]
6.Situação
Uma indústria fabrica robôs que catam lixo do chão após eventos esportivos. Antes dos robôs entrarem em
ação, uma fotografia aérea é tirada e dividida em quadrados. As localizações que contém lixo estão marcadas. Todos o
robôs partem do canto noroeste e terminam seu trajeto no canto sudeste. Um robô só pode se movimentar em duas
direções, para o Sul e para o Leste. Ao entrar em uma célula contendo lixo, o robô cata-o antes de prosseguir. Uma vez
no canto sudeste, o robô não pode ser reposicionado ou reutilizado. A tarefa é encontrar o menor número de robôs
necessários para limpar a área inteira. Por exemplo, considere a área mostrada na Fig. 11. As posições dos lixos estão
marcadas com a letra ‘G’. Os robôs partem do ponto (1,1) e chegam ao ponto (6,7).
Fig 11 – Uma fotografia aérea da área
A Fig. 12 mostra duas soluções possíveis. A segunda é melhor pois utiliza dois robôs em vez de três.
Fig. 12 – Duas soluções possíveis
6.1.Comentário
Para essa questão parede bastante natural pensar em programação dinâmica para a resolução. A seguir será
apresentada uma bela solução baseada no algoritmo da maior subseqüência crescente.
6.2.Solução
A primeira parte da solução consiste em criar uma seqüência s de naturais da seguinte forma: para cada linha,
da primeira à última, transcreva os índices das colunas em que estão as sujeiras. No exemplo mostrado nas figuras
anteriores a construção se dá na seguinte forma.
Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007
,
1ª linha : 2 4
2ª linha : 4 6
3ª linha :
4ª linha : 4 7
5ª linha :
6ª linha : 6
Seqüência s : 2 4 4 6 4 7 6.
Um robô que pegou um pedaço de lixo numa coluna i não pode mais pegar nenhum pedaço de lixo em uma
coluna de índice menor do que i, pois ele só pode andar para o leste ou para o sul.
Ao tomar uma subseqüência decrescente na seqüência s, temos que para cada elemento dessa subseqüência
deve haver um robô. A explicação é justamente o fato de que o robô não pode voltar para uma coluna de índice menor
do que a que ele está.
Dessa forma, o número de elementos da maior subseqüência decrescente é igual à quantidade de robôs
necessários para pegar todos os pedaços de lixo da área.
Agora basta apenas o algoritmo de determinação do tamanho da maior subseqüência decrescente de uma
seqüência s - a1a2...ak.
MAIOR-SUBSEQUÊCIA-DECRESCENTE (s)
1- Defina F(i) como o tamanho da maior subseqüência decrescente entre o início e o índice i da seqüência s.
2- F(0) ← 0, F(1) ← 1
3- for i ← 1 até k
4-
do F(i) = max{ F(j) } + 1, para aj ≥ ai e 0 ≤ j ≤ i-1
5- F(k) é o valor desejado
7.Agradecimentos
•
•
•
•
•
•
•
Aos meus amigos Hélder Suzuki e Cesário Martins pela grande colaboração no estudo de algoritmos e
programação
À equipe “Sushi, Yakisoba e Forró” pela união e amizade dos membros e pela ótima experiência na
participação da Maratona de programação
Ao professor Nei Yoshihiro Soma por me orientar nesse trabalho de iniciação científica
Ao professor Armando Gouveia por todo o apoio e incentivo ao estudo de programação e algoritmos
A Humberto Naves pelas dicas e orientações durante o ano
Aos professores Eduardo Tengan, Carlos Shine , Edmilson Motta e Pablo Ganassim pela ótima base
matemática que me forneceram
Ao CNPq pela oportunidade fornecida de pesquisa e desenvolvimento de um trabalho tão interessante
8. Referências
[1] CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L., STEIN, C. Algoritmos-Tradução da 2ª edição americana. Ed.
Campus, 2001
[2] JUNGNICKEL, D., Graphs, Networks and Algorithms. Springer, 1999.
[3] SEDGEWICK, R., Algorithms. ADDISON-WESLEY, 1984
[4] SKIENA, S.S., REVILLA, M.A., Programming Challenges, Ed. Springer, 2003.
[5] International ACM Programming Contest. Disponível em <http://acm.uva.es>. Acesso em 08/2007.
De
Bruijn
digraph.
[6]
Wikipedia,
the
free
<http://en.wikipedia.org/wiki/De_Bruijn_digraph>. Acesso em agosto de 2007.
encyclopedia.
Disponível
em