Franklina M. B. Toledo / Alysson M. Costa Otimização em grafos Problemas de otimização em...

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Otimização em grafos

Problemas de otimização em árvores

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Otimização em árvores

• ... voltando à primeira aula...

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Definição: uma árvore é um grafo conexo sem ciclos.

– uma árvore tem exatamente n-1 arcos.– uma árvore tem ao menos dois nós folha (nós com grau 1)– existe apenas um caminho entre dois nós quaisquer de uma árvore.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Definição: uma floresta é uma coleção de árvores

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Minimum spanning tree (MST)

• Problema da árvore geradora mínima:

– Seja o grafo G=(V,A)

– Seja cij o custo associado a um arco (i,j) 2 A.

Obter a árvore T que conecta todos os nós de V, com custo mínimo (custo = )

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Aplicações

• Aplicações diretas– O problema prático com o qual se quer trabalhar

naturalmente pode ser definido como o problema de se encontrar uma MST.

• Aplicações indiretas– Através de manipulações, pode-se obter a

solução do problema original através da obtenção de uma MST.

• Como subproblema de outros problemas

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Aplicações diretas

• Projeto de sistemas físicos onde entidades precisam ser conectadas e não é necessário redundância.

• Exemplos:– projetos viários (em regiões periféricas)– televisão a cabo– linhas de transmissão– linhas telefônicas– redes de computadores– etc.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Exemplos (Ahuja)– Conectar terminais em equipamentos de

maneira a minimizar o total de cobre gasto;– Construir redes de tubulações conectando

bairros, de modo a minimizar o comprimento da rede;

– Conectar vilas em regiões afastadas;– Construir circuitos digitais de alta frequência;– Conectar computadores em redes LAN.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Aplicações indiretas

• Manipulações no problema original, de modo a torná-lo um MST.

retirado de Ahuja et al. (1993).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

"On the history of the MST" Graham and Hell

1985

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Cluster analysis:– Particionar dados em grupos representativos.

retirado de Ahuja et al. (1993).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Sequência

• Condições de otimalidade;• Algoritmos:

– Kruskal– Prim– Sollin

• Modelos matemáticos• Variações do problema.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Condições de otimalidade

• Condições de otimalidade de corte(cut optimality conditions)

• Condições de otimalidade de caminho(path optimality conditions)

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Preliminares:

– arco-árvore (tree arcs): um arco que pertence à árvore que está sendo estudada;

– arco-não-árvore (nontree arcs): um arco que não pertence à árvore que está sendo estudada.

retirado de Ahuja et al. (1993).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Observação simples (I):– para todo arco-não-árvore (k,l), a árvore T

contém um único caminho entre os nós k e l. O arco (k,l) em conjunto com este caminho define um ciclo.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Observação simples (II):– se eliminarmos um arco-árvore (i,j) de uma

árvore, o grafo resultante particiona o conjunto de nós V em dois subconjuntos. Chamamos o conjunto de arcos do grafo G com um terminal em cada subconjunto de corte (cut).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Condição de optimalidade de corte:

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de corte: para cada arco (i,j) 2 T*, cij · ckl para todo arco (k,l) pertencente ao corte obtido pela exclusão do arco (i,j) de T*.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de corte: para cada arco (i,j) 2 T*, cij · ckl para todo arco (k,l) pertencente ao corte obtido pela exclusão do arco (i,j) de T*.

• Prova: ! (toda árvore T* deve satisfazer a condição).

Se existe um arco-não-árvore (k,l) pertencente ao corte gerado por (i,j) com ckl < cij, então trocar (i,j) por (k,l) em T* gera uma árvore T' de custo menor que T*.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de corte: para cada arco (i,j) 2 T*, cij · ckl para todo arco (k,l) pertencente ao corte obtido pela exclusão do arco (i,j) de T*.

• Prova: Ã (se T* satisfaz as condições, então T* é MST).

Seja To uma uma MST, com To T*. T* contém um arco (i,j) que não está em To.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de corte: para cada arco (i,j) 2 T*, cij · ckl para todo arco (k,l) pertencente ao corte obtido pela exclusão do arco (i,j) de T*.

• Prova: Eliminando (i,j) de T* cria um corte .Adicionando (i,j) em To, cria um ciclo de deve conter

um arco (k,l) que não estava em T*, com k2S e l2 .

Como T* satisfaz as condições de otimalidade de corte, cij · ckl. Por outro lado, To é ótima, logo cij¸ckl. Logo cij=ckl. Trocando (i,j) por (k,l) em T*, temos uma árvore com mesmo custo e mais próxima de To. Repetindo o argumento, veremos que T* e To tem o mesmo custo e, consequentemente, T* é ótima.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Condições de otimalidade de corte, conclusão:

Cada arco em uma MST é de custo mínimo no corte definido ao se retirá-lo da árvore.

Por outro lado, as condições de otimalidade de corte implicam que sempre podemos adicionar à MST o arco de menor custo de um corte qualquer de um grafo.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Condição de otimalidade de caminho:

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de caminho: para cada arco-não-árvore (k,l)2 G, cij · ckl para todo arco (i,j) contido no caminho em T* que conecta os nós k e l.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de caminho: para cada arco-não-árvore (k,l)2 G, cij · ckl para todo arco (i,j) contido no caminho em T* que conecta os nós k e l.

• Prova: ! (toda árvore T* deve satisfazer a condição).

Suponha que T* é MST e existe um arco (i,j) no caminho em T* conectando os nós k e l. Se cij ¸ ckl, trocar o arco (i,j) pelo arco (k,l) geraria uma árvore de custo menor que T*, contradizendo a hipótese.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de caminho: para cada arco-não-árvore (k,l)2 G, cij · ckl para todo arco (i,j) contido no caminho em T* que conecta os nós k e l.

• Prova:

à (se a condição de otim. de caminho é satisfeita em T*, então T* é ótima). Usamos a suficiência da condição de otim. de corte.

Vamos mostrar que se uma árvore T* satisfaz as condições de otimalidade de caminho, então ela também satisfaz as condições de corte (e, consequentemente, podemos usar o teorema anterior para provar a suficiência das cond. de otim. de caminho).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Teorema: Uma árvore T* é uma MST se e somente se ela satisfaz as condições de otimalidade de caminho: para cada arco-não-árvore (k,l)2 G, cij · ckl para todo arco (i,j) contido no caminho em T* que conecta os nós k e l.

• Prova: Seja (i,j) um arco-árvore de T* como na figura. Considere um arco

T* contém um único caminho ligando k a l, logo (i,j) deve pertencer a este caminho (ele é o único que liga S a em T*).As condições de otimalidade de caminho garantem que cij · ckl. Como estas condições valem para qualquer arco (k,l), temos as cond. de otim. de corte e, portanto, T* é MST.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Maximum spanning trees

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Algoritmos

• Kruskal• Prim• Sollin• Boruvka

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Kruskal (idéia)

• (inspirado nas condições de otimalidade de caminho)Algoritmo inocente não polinomial:

– 1. comece com uma árvore qualquer T;– 2. teste as condições de otimalidade de

caminho; se satisfeitas, pare. T é ótima.– 3. como as condições não são satisfeitas,

existe um arco árvore (i,j) e um arco-não-árvore (k,l) tais que cij > ckl. Troque (i,j) por (k,l) em T e volte para 2.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Kruskal

• Polinomial. Constrói T* através da adição gulosa de arcos.– 1. ordene os arcos de maneira que os custos

sejam não decrescentes. Defina LIST, os arcos que pertencem à árvore (LIST = vazio).

– 2. Examine os arcos, verificando se a inserção deles gera um ciclo com os arcos de LIST. Se não, adicione o arco a LIST.

– 3. |LIST| = n-1 ? sim: pare (os arcos em LIST são os arcos da árvore ótima). não: volte para 2.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Ao adicionarmos arcos em uma ordem de custo não-decrescente, automaticamente satisfazemos as condições de otimalidade de caminho.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Algumas considerações computacionais (ver Ahuja).

• Brevemente:– tempo para se detectar a existência ou não de um

ciclo (método inocente): LIST a cada momento contém uma floresta. Guardamos os conjuntos conexos como diferentes listas ligadas e checar se os dois extremos do arco testado pertencem ao mesmo conjunto. Se sim, forma um ciclo (descartamos o arco). Se não, unimos os conjuntos conexos em um único.

• Complexidade total: O(nm)

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Algumas considerações computacionais (ver Ahuja).– estruturas de dados adicionais;– complexidade O(m + n log n).– O(m (n,m) ) usando melhores operações de

union-find.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Prim

• Polinomial. Baseado na condição de otimalidade de corte.

• Começa de um nó qualquer e adiciona à árvore o arco que satisfaz a condição de otimalidade de corte.– 1. Inicie com um nó qualquer i, S = {i}; S= V\

S;– 2. ache (i,j) 2 [S,S] de menor custo.– 3. faça S=S+{j} e S= V\S; – 4. |S| = n-1 ? se sim: pare; se não, volte a 2.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Prim

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• Considerações computacionais (ver Ahuja)

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Sollin

• híbrido entre Kruskal e Prim.– como em Kruskal: mantém uma floresta– como em Prim: a cada iteração, adiciona os

arcos de menor custo emanando desta floresta.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Sollin

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Sollin

• Considerações de implementação e complexidade, ver Ahuja.

• O(m log n).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Boruvka• It was first published in 1926 by Otakar Borůvka

as a method of constructing an efficient electricity network for Moravia.[1][2]

The algorithm was rediscovered by Choquet in 1938; [3] again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Sollin some time in the early 1960s. Because Sollin was the only Western computer scientist in this list, this algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.

retirado da wikipedia.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Antes de Boruvka ?

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Modelos matemáticos

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Modelos matemáticos

• Dantzig-Fulkerson-Johnson (de novo!)

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Flow formulation

retirado de http://coral.ie.lehigh.edu/~belotti/teaching/ie426-08/lecture16.pdf

idéia: uma MST deve permitir um caminho entre cada par de nós.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Variações

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Capacitated MST

0

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Steiner tree problem in graphs

• Nem todos os nós são obrigatórios...

retirado de COSTA, A. M. Otimização do planejamento da rede secundária de distribuição de energia elétrica. MSc. dissertation, Universidade Estadual de Campinas, 2002.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Steiner Tree Problem in Graphs (STP)

• Grafo equivalente

nós de Steiner: não precisam ser conectados, mas podem ser usados...

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Solução MST Solução TSP

nó terminal

nó de Steiner

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

• MST: polinomial.• TSP: NP-Hard

– Um dos 21 problemas de Karp.– impossible to approximate within any constant

factor unless P = NP (David Zuckerman 1996)*

– unless P = NP, the Steiner tree problem in general graphs cannot be approximated withina factor of 1 + for sufficiently small > 0 (M. Bern and P. Plassmann 1989)

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Métodos (exemplo)

retirado de COSTA, A. M. Otimização do planejamento da rede secundária de distribuição de energia elétrica. MSc. dissertation, Universidade Estadual de Campinas, 2002.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Pre-processamento

C. W. Duin, A. Volgenant Reduction tests for the steiner problem in graphs (republicado em Networks Volume 19 Issue 5, Pages 549 - 567 ).

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Pre-processamento (exemplos)

The Steiner tree problem ( Frank Hwang, Dana Richards, Pawel Winter )

Exclusion tests:

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Inclusion tests:

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Pre-processamento

The Steiner tree problem ( Frank Hwang, Dana Richards, Pawel Winter )

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Steiner tree problem with profits

Costa, Cordeau, Laporte, A survey of Steiner tree problems with profits, Infor 44, 99-115, 2006.

r

35

6 15

35

1

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Steiner tree problem with profits

Aplicações:

Tv a caboGás canalizado

Indiretas:Minimum 1-trees (Engevall et al., 1998) Redes Wi-fi (Friedman and Parkes, 2003)Multicasting games (Chawla, 2003)

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Reduction tests

• A reinvenção da roda... mas mais redonda!

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Hop constraints

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

ir j

ir j

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

Hop constraints• Luis Gouveia

...

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.

E de uma maneira geral...

Franklina M. B. Toledo / Alysson M. Costa 11:50 7 mai 2009.