Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL DO PARANÁ – UFPR
CIÊNCIA DA COMPUTAÇÃO
LEONARDO TERNES SANTOS
OTIMIZAÇÃO DE FLUXO EM GRAFOS
CURITIBA, MARÇO 2013
LEONARDO TERNES SANTOS
OTIMIZAÇÃO DE FLUXO EM GRAFOS
Trabalho de graduação, apresentado para
obtenção do grau de bacharel em ciência da
computação da Universidade Federal do
Paraná, UFPR.
Orientador: Prof. Andre Guedes
CURITIBA, MARÇO 2013
3
RESUMO
Este trabalho trata da aplicação e implementação do problema de fluxo
máximo, utilizando em específico o algoritmo push-relabel na linguagem C para
calcular tal fluxo.
Neste documento será apresentado aplicações práticas do problema, o
funcionamento do algoritmo push-relabel utilizando imagens para melhor
compreensão do exemplo e uma análise de seu custo computacional.
Pretendo demonstrar com este trabalho a aplicabilidade do problema em
casos do cotidiano assim como a viabilidade através do algoritmo escolhido de
resolver tais problemas.
Palavras-chave: Otimização, fluxo, grafos, push, relable.
4
LISTA DE FIGURAS
Figura 1 - Grafo em estado inicial ....................................................................... 9
Figura 2 - Grafo após push da fonte para seus vizinhos .................................... 10
Figura 3 - Push a partir do nó um ...................................................................... 11
Figura 4 - Retorno de fluxo para fonte ....................................................................... 12
Figura 5 - Relabel(2) e push(2,4) .............................................................................. 12
Figura 6 - Retorno de fluxo do nó 2 para fonte .......................................................... 13
Figura 7 - Relabel(4) e push(4,5) .............................................................................. 13
Figura 8 - Retorno de fluxo do nó 4 para o nó 2 ........................................................ 14
Figura 9 - Retorno de fluxo do nó 2 para fonte .......................................................... 14
Figura 10 - Log da execução do exemplo utilizado em 2.1 ...................................... 15
Figura 11 - Função pushRelabel implementada em C .............................................. 22
Figura 12 - Função discharge implementada em C ................................................... 23
Figura 13 - Função push implementada em C .......................................................... 24
Figura 14 - Função relabel implementada em C ....................................................... 24
Figura 15 - Grafo demonstrando altura máxima que um nó pode obter .................... 28
5
SUMÁRIO
1. INTRODUÇÃO .......................................................................................... 6
2. O PROBLEMA .......................................................................................... 7
2.1. Aplicações ......................................................................................................... 7
3. O ALGORITMO PUSH-RELABEL ............................................................. 8
3.1 O Funcionamento .............................................................................................. 8
3.1.1 Log da execução .......................................................................................... 15
3.2 Variáveis .......................................................................................................... 20
3.3 Funções ........................................................................................................... 21
3.3.1 PushRelabel ................................................................................................. 21
3.3.2 Discharge ..................................................................................................... 22
3.3.3 Push ............................................................................................................. 23
3.3.4 Relabel ......................................................................................................... 24
3.4 Análise de custo .............................................................................................. 25
3.4.1 Rede residual ............................................................................................... 25
3.4.2 Lema 1 ......................................................................................................... 25
3.4.3 Lema 2 ......................................................................................................... 26
3.4.4 Fato 3 ........................................................................................................... 27
3.4.5 Fato 4 ........................................................................................................... 27
3.4.6 Fato 5 ........................................................................................................... 28
3.4.7 Fato 6 ........................................................................................................... 28
3.4.8 Fato 7 ........................................................................................................... 29
3.4.9 Fato 8 ........................................................................................................... 30
3.4.10 Fato 9 ........................................................................................................ 30
3.4.11 Fato 10 ...................................................................................................... 30
3.4.12 Fato 11 ...................................................................................................... 31
4 CONCLUSÃO ................................................................................................. 32
5 REFRÊNCIA BIBLIOGRÁFICA ...................................................................... 33
6
1. INTRODUÇÃO
O problema em encontrar o fluxo máximo em um grafo direcionado com
capacidades nas arestas é algo estudado em diversas pesquisas e em outros
campos, e encontrar algoritmos eficientes para resolver este problema tem recebido
muita atenção. Discussão sobre este problema e suas aplicações pode ser
encontrada nos livros de Even, Ford and Fulkerson, Lawler, Papadimitriou and
Steiglitz entre outros.
O objetivo primário do problema de fluxo máximo, é, dado um ponto inicial
e um ponto final , descobrir qual o fluxo máximo que pode transitar de para
dentro de uma rede direcionada. Entretanto, durante a execução do algoritmo
podemos obter outras informações relevantes além do número que delimitará o
fluxo, como por quais caminhos devemos trafegar e qual a capacidade de cada
caminho.
Tendo em vista a capacidade de otimização do problema descrito, quero
através deste trabalho demonstrar algumas aplicações que podem ser resolvidas
com este problema utilizando em específico o algoritmo push-relabel, que
atualmente é o que possui o melhor custo de execução, explicando por completo
seu funcionamento e demonstrando seu custo computacional.
7
2. O PROBLEMA
Dado um grafo G direcionado onde a capacidade do nó para o nó é dada
por ( ), nó inicial e nó destino , queremos saber qual o fluxo máximo que
poderá ser enviado de para e por quais caminhos.
2.1. Aplicações
Em um mundo onde a otimização do tempo é tão necessária, conseguimos
através da representação de problemas como um grafo, utilizar a solução dada por
algoritmos que retornam o fluxo máximo para melhorar o desempenho de diversos
problemas, alguns deles citados abaixo:
Maximizar o fluxo de uma rede de distribuição de uma companhia a partir de
suas fabricas para seus clientes. Exemplo baseado na descrição de aplicações do
problema de fluxo máximo feita pelo Dr. Paulo Roberto Gomes Luzzardi para o
programa de mestrado em ciência da computação retirada do link
http://www.ufjf.br/epd015/files/2010/06/fluxo_maximo2.pdf.
Controlar o trânsito de uma cidade através dos semáforos baseado na
capacidade das ruas de comportar carros e do tráfego atual em cada uma delas.
Distribuição de pacotes em uma rede (internet/intranet) de tal forma que os
mesmos não trafeguem apenas por um caminho, e sim de forma distribuída entre
toda a rede disponível.
Para calcular o fluxo máximo, iremos utilizar o algoritmo push-relabel, que
atualmente é o algoritmo com melhor custo para resolver o problema do fluxo
máximo.
8
3. O ALGORITMO PUSH-RELABEL
Para calcular o fluxo descrito em 2, o algoritmo utiliza duas funções
principais: push e relabel. Tais funções mantem os seguintes dados:
( ). Fluxo de u para v. A capacidade disponível é dada por c(u,v) - ƒ(u,v).
height(u). Nós chamamos a função push de u para v apenas se height(u) >
height(v). Para todos u, height(u) é um inteiro positivo.
Excess(u). Soma do fluxo de e para u.
Após cada passo do algoritmo, teremos um pré-fluxo que deve satisfazer as
seguintes condições:
ƒ(u,v) < c(u,v). O fluxo entre u e v não excede a capacidade.
ƒ(u,v) = - ƒ(v,u). Mantemos o fluxo da rede.
∑ ƒ( ) ( ) para todos os nós u ≠ s. Somente a fonte pode
produzir fluxo.
No algoritmo implementado para testes e demonstrações presentes nesse
trabalho, também temos outras funções auxiliares como as funções pushRelabel
,discharge e funções auxiliares para imprimir matrizes e vetores gerando logs de
execução.
3.1 O Funcionamento
Para melhor compreensão, podemos fazer uma analogia do algoritmo com
uma rede de tanques (vértices) interligada por canos (arestas) onde queremos saber
qual a capacidade máxima de água que podemos enviar para um tanque destino “t”
a partir de um tanque inicial “s”. O deslocamento da água será feito elevando a
altura do tanque desejado, assim a água poderá escorrer para um tanque de altura
mais baixo.
Vamos assumir a figura 1 como o exemplo de grafo para demonstrar o
funcionamento do algoritmo.
9
Figura 1: Grafo em estado inicial.
Inicialmente, o algoritmo iguala a altura do vértice inicial com o número de
vértices presente no grafo e inicia todos os outros vértices com altura zero. Como
podemos apenas enviar o fluxo de nós mais altos para mais baixos, agora com o nó
inicial mais alto que os demais podemos enviar o fluxo para seus vizinhos.
A partir deste ponto, chamamos a função push do nó inicial para todos seus
vizinhos enviando todo o fluxo permitido pela capacidade de suas arestas. A figura
2 demonstra a situação do fluxo após o push inicial, onde podemos observar a
mudança de ( ) e ( ).
10
Figura 2: Grafo após push da fonte para seus vizinhos.
Após o push inicial partindo do nó fonte, observamos além da mudança no
fluxo, também o vetor que controla o excesso presente no fluxo atual tem seus
valores no nó 1 e 2 atualizados. Nossa intenção é que, no final da execução do
algoritmo, todos os vértices com exceção da fonte e do destino estejam com
excesso de fluxo igual a zero.
A partir de tal ponto, o algoritmo irá navegar em todos os nós tentando jogar
o fluxo excessivo para seus vizinhos. Como todos os nós fora o fonte estão com sua
altura zero e podemos apenas enviar fluxo de um nó mais alto para um nó mais
baixo, será necessário chamar a função relabel para aumentar minimamente a altura
tornando possível o envio de fluxo do nó corrente.
Após o ajuste na altura, iremos enviar todo o fluxo possível do nó corrente
para seus vizinhos através de função push. Caso ainda haja excesso de fluxo no nó
corrente, enviaremos fluxo de volta para a fonte.
As figuras a seguir demonstram a execução completa do algoritmo para o
grafo exemplo.
11
Figura 3: Push a partir do nó um.
Podemos observar na figura 3 que só é possível realizar o push(1,2) pois a
altura do nó 1 foi aumentada na função relabel. Mesmo após o push de 1 para seus
vizinhos ainda há excesso no nó selecionado, então será necessário devolver fluxo
para a fonte. A figura 4 demonstra que foi necessário tornar a altura do nó 1 maior
que a altura do nó fonte, utilizando a função relabel, para podermos devolver fluxo.
Isso se deve ao princípio citado anteriormente nessa sessão, onde para poder enviar
fluxo de um nó a para um nó b, height(a) > height(b). Retornando o fluxo para a
fonte, o excesso do nó 1 é zerado e podemos prosseguir para o próximo nó.
12
Figura 4: Retorno de fluxo para fonte.
Como conseguimos zerar o excesso do nó 1, o algoritmo pula para o
próximo nó e repete os passos descritos anteriormente.
Figura 5: Relabel(2) e push(2,4)
13
Figura 6: Retorno de fluxo do nó 2 para fonte.
Figura 7: Relabel(4) e push(4,5).
14
Figura 8: Retorno de fluxo do nó 4 para o nó 2.
É importante observar na figura 8, que o retorno de fluxo não é feito
diretamente para a fonte e sim para o nó 2, o que aumentará novamente o excesso
do nó 2, fazendo necessário também o retorno do excesso dele. O detalhe de como
o algoritmo sabe para onde deve ser retornado o fluxo será apresentado mais
abaixo.
15
Figura 9: Retorno de fluxo do nó 2 para fonte.
Na figura 9 podemos observar que não há nenhum nó com excesso de fluxo,
então o algoritmo retorna a soma dos fluxos partindo da fonte, ou seja, o fluxo
máximo que pode ser enviado do nó fonte para o nó destino.
3.1.1 Log da execução
Na figura 10 podemos observar um log detalhado com o valor das variáveis
descritas em 2.2 para a execução demonstrada em 2.1.
16
17
18
19
20
Figura 10: Log da execução do exemplo utilizado em 2.1.
3.2 Variáveis
Existem algumas variáveis utilizadas na iteração de laços que não foram
descritas abaixo.
Flow: Matriz que guarda o fluxo/pré-fluxo.
Capacities: Matriz que guarda a capacidade de cada aresta.
Nodes: Número de nós no grafo.
Init: Nó fonte.
Dest: Nó destino.
Excess: Vetor que guarda o excesso de cada nó.
Height: Vetor que guarda a altura de cada nó.
List: Lista dos nós do grafo com exceção da fonte e do destino.
Seen: Vetor dos nós que já foram visitados.
21
3.3 Funções
Após compreendermos a lógica do algoritmo, iremos nos aprofundar em
como é efetuado o controle de execução e o que cada função do algoritmo
implementado para este trabalho faz.
3.3.1 PushRelabel
Função responsável por fazer a inicialização dos vetores de controle e por
fazer o push de inicialização a partir do nó fonte para todos seus vizinhos ( dois nós
são vizinhos caso sejam adjacentes ou seja, tem uma aresta os conectando
diretamente). Após o push inicial, será chamada a função discharge para todos os
nós do grafo com exceção dos nós fonte e destino, ou seja, a chamada é feita para
todos os elementos do vetor list. Para retornar o fluxo máximo, após o termino da
execução da função discharge conforme descrito acima, basta somar o fluxo que
está sendo enviado do nó fonte para todos seus vizinhos.
Podemos observar na figura 11 o exemplo da função implementada em C.
22
Figura 11: Função pushRelabel implementada em C.
3.3.2 Discharge
Função que terá como responsabilidade eliminar o excesso de fluxo para o
nó que ela foi chamada. Para cumprir seu objetivo, ela utiliza o vetor de controle
seen para verificar por quais nós ela já percorreu.
Primeiramente a função tenta realizar um push para todos os vizinhos do nó
para a qual foi chamada, entretanto para efetuar o push do nó u para o nó v, c(u,v) -
ƒ(u,v) > 0 e height(u) > height(v). Após enviar todo fluxo possível, caso ainda haja
fluxo é a função discharge que será responsável por identificar tal situação e
chamará a função relabel para aumentar a altura do nó, tornando possível o retorno
23
de fluxo para a fonte através de uma nova chamada da função push, entretanto
desta vez no sentido reverso (do nó selecionado para a fonte).
É importante ressaltar neste ponto, que o algoritmo sabe que deve retornar o
fluxo para a fonte (ou nó que está lhe enviando fluxo em excesso) pois todos os nós
os quais ele poderia enviar fluxo estão com a capacidade esgotada e, como ƒ(u,v) =
-ƒ(v,u), quando testarmos se é possível efetuar um push para um nó anterior
(entenda nó anterior um nó com um id < id do nó selecionado) através da condição
c(u,v) - ƒ(u,v) > 0 e height(u) > height(v), ƒ(u,v) será negativo pois u > v, então
temos que c(u,v) + ƒ(u,v) > 0 para ƒ(u,v) não nulo. Neste caso c(u,v) sempre será
nulo pois não há aresta de u para v, caso contrário teria sido efetuado o push para
tal aresta na primeira parte da função. Neste caso height(u) é maior que height(v)
pois tivemos a altura de u aumentada previamente como descrito. O entendimento
de como a altura dos nós é controlada será melhor explicado na função relabel.
Com todo o excesso devolvido para o responsável por causar tal excesso no
nó selecionado, a função retorna.
Podemos observar na figura 12 o exemplo da função implementada em C.
Figura 12: Função discharge implementada em C.
3.3.3 Push
A função push é a responsável por enviar o fluxo de um nó u para um nó v.
Para fazer isso, a função verifica qual é o mínimo entre o excesso do nó u
24
(excess[u]) e a capacidade atual da aresta (c(u,v) - ƒ(u,v)) para descobrir quanto
fluxo ela poderá enviar sem exceder o limite da aresta.
Após definir quanto fluxo será enviado, a função atualiza a matriz flow e o
vertor excess conforme na implementação demonstrada na figura 13.
Figura 13: Função push implementada em C.
3.3.4 Relabel
Função responsável por aumentar a altura de um nó u passado como
parâmetro da função, tornando assim possível o envio de fluxo deste nó através da
função push.
Para saber o quanto deverá ser aumentada na altura do nó u, a função
percorre todas as arestas de u, pegando a menor altura de algum vizinho v entre
todos os v’s onde existe a possibilidade de enviar fluxo (c(u,v) - ƒ(u,v) > 0).
Figura 14: Função relabel implementada em C.
A descrição das funções acima foi baseada no artigo escrito na wikipedia que pode
ser encontrado no link http://en.wikipedia.org/wiki/Push-
25
relabel_maximum_flow_algorithm e no artigo “A New approach to the maximum-flow
problem” de Andrew V. Goldberg e Robert E. Tarjan.
3.4 Análise de custo
A demonstração abaixo foi retirada do link
http://theory.stanford.edu/~trevisan/cs261/lecture12.pdf, realizada por Luca Trevisan
da universidade de Stanford. Algumas imagens foram adicionadas para facilitar a
compreensão de alguns fatos.
Nós iremos começar demonstrando que nenhum vértice pode atingir uma
altura maior que | | . Provando isto, nós conseguimos definir um limite de
operações relabel que podem ser executadas, o que é um importante ponto de início
para analisarmos o número de operações push.
3.4.1 Rede residual
Dado uma rede de fluxo ( ) e um fluxo em ( ), nos definimos a
rede residual ( ) de ( ) como:
O conjunto de nós de ( ) é o mesmo de ( ) ou seja .
Cada aresta ( ) de tem a capacidade ( ).
Cada aresta ( ) de tem a capacidade ( ).
3.4.2 Lema 1
A cada passo, se um vértice v tem um excesso de fluxo positivo, então
existe um caminho de v para s na rede residual.
Prova: Sabemos que todo o fluxo só pode ser gerado por s, então se um
vértice v tem um excesso de fluxo positivo, tal fluxo deve vir de s através de um
26
caminho feito de arestas com fluxo positivo. A única parte do argumento que não é
rigorosa é quando nós falamos que se um vértice v tem um fluxo positivo então deve
haver um caminho de s para v feito inteiramente do arestas com fluxo positivo.
Considere A como o conjunto de vértices que são alcançáveis a partir de s
por tal caminho. Por causa da restrição do pré-fluxo nos vértices , nós temos
∑ ( )
∑(∑ ( )
∑ ( )
)
más, na segunda expressão, todos os termos da forma ( ) onde e
se cancelam, pois aparecem uma vez com o sinal de mais e outra de menos.
O resultado de tal cancelamento é
∑ ( )
∑ ( )
∑ ( )
onde a ultima inequação segue do fato de ( ) deve ser zero quando
e .
Então quando temos ( ) para todo , o que significa que cada
vértice que tem ( ) deve estar em , e então deve ser alcançavel a partir de
por um caminho feito de arestas com fluxo positivo.
A conexão entre este lema e a tarefa de limitar as alturas dos vértices virá
nas observações seguintes.
3.4.3 Lema 2
A cada passo, se existe uma aresta ( ) que tenha uma capacidade
( ) na rede residual, então ( ) ( ) .
Prova: No inicio, a rede residual possui:
I. As arestas da rede original entre os vértices fora , e todos os vértices
tem a mesma altura 0.
II. Arestas dos vizinhos de para , e tais arestas vão “para cima”.
27
Se nos fizermos uma operação relabel no vértice , a propriedade se
mantém verdadeira para todas as arestas ( ) com capacidade positiva vindo para
. Agora sobre as arestas com capacidade positiva saindo de , se nós fizemos uma
operação relabel foi porque nós tinhamos ( ) ( ), então após tal operação nós
ainda temos ( ) ( ) .
Se nós fizermos um push na aresta ( ), nós devevemos inserir a aresta
reversa ( ) na rede residual. Entretanto a operação push só ocorre quando
( ) ( ), então a aresta ( ) satisfaz a propriedade.
3.4.4 Fato 3
A cada passo, se existe um caminho de para na rede residual, então
( ) ( ) | |
Prova: Se existe um caminho de tamanho de para na rede residual,
então, aplicando vezes o corolário 1, nos temos ( ) ( ) , e se existir um
caminho de para deve existir um caminho de tamanho máximo | | .
A partir de tais argumentos podemos começar a tirar conclusões relevantes
para nossa analise.
3.4.5 Fato 4
A cada passo do algoritmo, não existe caminho de para na rede residual.
Porque, se houve tal caminho, nos teríamos ( ) ( ) | | , mas no
início nos temos que ( ) | | e ( ) , e as alturas de e nunca mudam.
Isto significa que se o algoritmo terminar, então ele terá como saída o fluxo
otimizado. De agora em diante, nos sobra estimar o tempo de execução do
algoritmo, que nos faremos achando limites superiores para o número de vezes que
as várias operações podem ser executadas.
28
3.4.6 Fato 5
A cada passo do algoritmo, cada vértice tem sua altura no máximo | | .
Prova: Cada vez que é aumentada a altura de um vértice , é porque ele
tem um excesso de fluxo. Se um vértice tem um excesso de fluxo, então existe um
caminho de para na rede residual. Se existe tal caminho, então ( ) ( )
| | | | .
A imagem abaixo demonstra o caso onde a altura será | | , quando a
capacidade do caminho tem uma forma de “funil”, ou seja, para o conjunto de
arestas dado por [a1,a2,...,an], ( ) ( ) ( ).
Figura 15: Grafo demonstrando altura máxima que um nó pode obter.
3.4.7 Fato 6
O algoritmo executa no máximo (| | ) ( | | ) | | operações
relabel.
29
Prova: Existem no máximo | | vértices que a execução de operações
relabel são admissíveis, e em cada uma delas o algoritmo executa a operação no
máximo | | vezes (fato 5).
Agora iremos estimar o número de operações push. Nós chamamos uma
operação push de saturada caso ela use toda capacidade restante da aresta,
fazendo ela sumir completamente da rede residual. Caso contrário, a operação push
é não saturada.
3.4.8 Fato 7
O algoritmo executa no máximo | | | | operações push saturadas.
Prova: Considere uma aresta ( ). A primeira vez será executado um push
saturado de para , pois ( ) ( ). Após o push saturado, a aresta ( )
desaparece da rede residual, e então não poderá existir outro push saturado de
para (e, de fato, nenhum push de qualquer tipo), até enviar de volta algum fluxo
para com um push na direção oposta. Mas para isto acontecer primeiro temos
( ) ( ), que requer no mínimo 2 relabels de . Para o próximo push saturado
de para , nos devemos ter novamente ( ) ( ), que requer mais dois relabels
no mínimo. Então, entre 2 pushes saturados de para , no mínimo 4 relabels
devem ocorrer em e em .Em uma visão geral, e podem sofrer relabel no
máximo | | vezes, e então podem existir no máximo | | pushes saturados.
No máximo | | arestas podem aparecer na rede residual, e então no total
nos temos no máximo | | | | pushes saturados.
A parte mais interessante da análise é como nos analisamos o número de
pushes não saturados.
A cada passo da execução do algoritmo, nos definimos a “energia” do pré-
fluxo atual como
( ) ∑ ( )
( )
30
a soma das alturas de todos os vértices que tem excesso de fluxo. O algoritmo
começa num estado nulo de energia, mas a energia vira um depois da primeira
operação de relabel. Quando a energia vira zero novamente, é porque não existem
nós com excesso de fluxo, então o algoritmo para.
Nós temos as seguintes observações.
3.4.9 Fato 8
Cada passo relabel aumenta a energia exatamente em uma unidade.
3.4.10 Fato 9
Cada push saturado aumenta a energia no máximo em | | unidades.
Prova: Uma operação push numa aresta ( ) não modifica a altura de
nenhum vértice, mas ele pode enviar excesso de fluxo para o vértice que
possivelmente tinha zero de excesso de fluxo antes, então a energia aumenta em
( ) | | unidades.
3.4.11 Fato 10
Cada push não saturado diminui a energia por pelo menos uma unidade.
Prova: Se nós efetuamos um push numa aresta ( ), porque o push seria
não-saturado? A única razão que nos faria não saturar uma aresta é que o excesso
de fluxo de é menor que a capacidade residual de ( ), e então nós podemos
enviar todo o excesso de fluxo de para . Mas isso significa que, depois de um
push não saturado ao longo de ( ), o excesso de fluxo de torna-se zero e então
( ) não é mais contada como energia. É possível que não tenha excesso de fluxo
antes do push e agora tenha, o que significa que nós precisamos adicionar ( ) na
energia, mas nós ainda tempos que a nova energia é no máximo a velha energia
31
menos ( ) mais ( ) e, relembrando que só fizemos um push se ( ) ( ), nós
temos que a nova energia é no máximo a velha energia menos um.
3.4.12 Fato 11
O número total de pushes não saturados é no máximo | | | | | |.
Prova: Se, em algum ponto da execução do algoritmo, o pré-fluxo ainda não
for um fluxo factível, então sua energia deverá ser maior que zero. Se, neste ponto,
o algoritmo tiver executado operações relabel, operações de push saturado e
operações de push não saturado, então
( ) | |
e nós sabemos que | | e | | | |, então a expressão acima
implica
| | | | | |
Então se, em algum ponto da execução do algoritmo, nós não tivermos
alcançado a condição terminal ainda, isto implica que executamos menos que
| | | | | | pushes não saturados.
Equivalentemente, quando o algoritmo termina, ele executou no máximo
| | | | | | pushes não saturados.
No geral, temos um total de no máximo (| | | |) operações, e cada
operação pode ser implementada em tempo ( ), então o tempo de execução do
algoritmo é (| | | |).
32
4 CONCLUSÃO
Neste trabalho, observamos que calcular o fluxo máximo é um problema
importante de otimização onde vários casos do dia-a-dia podem ser otimizados
através de tal calculo, auxiliando a aumentar capacidade de produções, diminuir o
tempo de distribuição de cargas, até mesmo aumentar a velocidade em uma rede de
computadores distribuindo pacotes baseado no peso que cada caminho pode
carregar.
Para calcular o fluxo máximo, aprendemos o algoritmo push-relabel que
atualmente é considerado o algoritmo com melhor custo computacional para resolver
tal problema. Através da execução passo-a-passo de um exemplo, verificamos seu
funcionamento e pudemos observar os métodos utilizados para descobrir a
capacidade máxima de fluxo entre os nós destino e inicial, assim como qual a
capacidade de cada caminho que obtemos através da rede residual no final da
execução do algoritmo.
Após compreender corretamente a execução do algoritmo, identifiquei que
algumas otimizações poderiam ser efetuadas na implementação utilizada neste
trabalho, tais como fazer uma lista de vizinhos para cada nó, o que reduziria a
necessidade de percorrer todos os nós na função discharge, ou modificar a
heurística utilizada para definir as alturas dos nós sem a necessidade de percorrer
por todo o conjunto, por exemplo, identificando um corte mínimo no grafo. Apesar de
existir otimizações a serem feitas que possam ser relevantes em grafos com baixa
densidade com alto número de nós, o complexidade assintótica continua sendo
(| | | |).
Estudos futuros poderiam ser direcionados a implementar tais otimizações
em problemas do cotidiano das pessoas, auxiliando a melhorar o desempenho de
várias atividades citadas anteriormente neste trabalho, melhorando a qualidade de
vida de todos.
33
5 REFRÊNCIA BIBLIOGRÁFICA
Even S., Graph Algorithms. Computer Science Press, Potomac, Md., 1979.
FORD, L. R., JR.; FULKERSON, D. R. Flows in Networks. Princeton
University Press, Princeton, N.J., 1962.
LAWLER, E. L. Combinatorial Optimization: Networks and Matroids. Holt,
Rinehart, and Winston, New York, 1976.
PAPADIMITRIOU, C. H.; STEIGLITZ, K. Combinatorial Optimization:
Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, N.J., 1982.
TARJAN, R. E. Data Structures and Network Algorithms. Society for
Industrial and Applied Mathematics, Philadelphia, Pa., 1983.
AUTOR DESCONHECIDO, Push-relabel maximum flow algorithm,
http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm, 2013.
GOLDBERG, A. V.; TARJAN, R. E. A New Approach to the Maximum-
Flow Problem, Journal of the Association for Computing Machinery, Vol. 35, No. 4,
1988.
TREVISAN, L., Handout 12,
http://theory.stanford.edu/~trevisan/cs261/lecture12.pdf , Stanford University, 2011.
