Redes

ADSA

António Câmara

Redes

• Método do caminho mais curto• Localização de equipamentos• Minimum spanning tree• Carteiro chinês• Caixeiro viajante• Links

Redes

• Redes são sistemas de linhas (arcos) ligando pontos (nós). Exemplos:– Vias de comunicação– Sistemas de rega, abastecimento de água e

drenagem– Linhas de alta tensão– Linhas telefónicas– Percursos alternativos (no espaço e no tempo)

Método do caminho mais curto

• Dada uma rede de n nós (1, 2, …, n) correspondente a cada arco (i, j) existe um número dij0 (distância, custo, tempo)

• O problema consiste em determinar o comprimento do caminho mais curto e o percurso desse caminho entre a origem, nó 1, e o nó de destino, nó n

Método do caminho mais curto

1

2

3

4

6

5

3

7

4

2

1

9

6

3

3

3

Método do caminho mais curto

• Determinar o caminho mais curto do nó 1 ao nó 6

• Aplicação do método de Dijsktra:– Atribuir um rótulo a todos os nós que pode ser

temporário ou permanente– Um rótulo temporário representa um limite superior

na distância mais curta do nó 1 e aquele nó– Um rótulo permanente é a distância mais curta entre

o nó 1 e aquele nó

Método do caminho mais curto

• L(0)= [0, 3, 7, 4, , ]*

* rótulo permanente

• L(1)= [0, 3, 7, 4, , ] * *

• Para cada um dos restantes nós, calcule-se um número igual à soma do rótulo permanente do nó 2 e a distância do nó 2 ao nó j

Método do caminho mais curto

• Compare-se este número com o rótulo temporário do nó j. O menor destes números passa a ser o novo rótulo do nó j. Exemplo: – Para o nó 3, min (3+2, 7)= 5

• L(2)= [0, 3, 5, 4, , 12] * * *

• Usa-se agora o rótulo permanente do nó 4 como âncora.

Método do caminho mais curto

• Calculam-se os novos rótulos temporários dos nós 3, 5 e 6

• L(3)= [0, 3, 5, 4, 7, 12] * * * *

• O nó 3 assume assim um rótulo permanente• L(4)= [0, 3, 5, 4, 7, 11]

* * * * *

• Usando o rótulo permanente do nó 5, mudamos o nó 6 para 10

Método do caminho mais curto• L(5)= [0, 3, 5, 4, 7, 10]

* * * * * *

• Para determinar a sequência de nós no caminho mais curto do nó 1 ao nó 6 opera-se no sentido inverso

• O nó j precede o nó 6 se a diferença entre os rótulos permanentes dos nós 6 e j iguala o comprimento do arco j a 6

• Percurso solução 6-5-4-1

Método do caminho mais curto

• Localização de infraestruturas lineares:– Afectar os arcos de índices reflectindo custos e/ou

impactes ambientais– Método de Dijkstra pode ser aplicado em sistemas

raster (pixeis são nós da rede) e vectoriais

• Método dos k-caminhos mais curtos pode ser aplicado para gerar alternativas

Método do caminho mais curto

Enumeração de alternativas em planeamento de usos do solo

Célula 1 Célula 2 Célula3

Uso1

Uso 2

Uso 3

Nó fict.

Uso 1

Uso 2

Uso 3

Uso 1

Uso 2

Uso 3

Nó fict.

Localização de equipamentos

• Método do caminho mais curto pode ser utilizado na localização de dois tipos de equipamentos:– Equipamentos que convém localizar minimizando a

distância média desses equipamentos à população que os utiliza. Exemplo: serviços não urgentes como os correios

Localização de equipamentos

– Equipamentos que convém localizar minimizando a máxima distância desses equipamentos aos potenciais utilizadores. Exemplo: serviços de urgência como os quartéis de bombeiros e hospitais

Localização de equipamentos

• Representar as possíveis localizações como nós• Indicar para esses nós os valores da procura

anual (pj)• Comprimentos dos arcos reflectem as distâncias

entre os locais• Método de solução:

– Calcular a matriz dij

Localização de equipamentos

– A distância total percorrida anualmente pelos potenciais utilizadores de um local i e residentes num local j pode ser expressa pela matriz [pj x dij]

– Pode-se então estimar as distâncias total e média percorridas por todos os potenciais utilizadores da região se o equipamento se localizar no nó I, calculando o somatório pj.dij e depois dividindo por pj

Minimum spanning tree

• Uma “spanning tree” é uma árvore de um grafo G que contém o conjunto completo de nós N de G.

• A “minimum spanning tree” é a árvore de todas as possíveis “spanning trees” de G com a distância total mínima

• Aplicação no desenho de “pipelines” e redes de drenagem

Minimum spanning tree

• Algoritmo de Larson e Odoni:– Inicie-se a construção da “minimum spanning tree”

num nó i. Encontre-se o nó mais próximo de i, diga--se j, ligado a i.

– Se todos os nós estão ligados, pare-se. A “minimum spanning tree” está encontrada. Se não, avance-se para o passo seguinte.

– Encontre o nó no conjunto daqueles ainda isolados mais próximo de um nó ligado e ligue-o a esse nó

Minimum spanning tree

• Grafo inicial

G

A

F

C

B

E D

5

6

10

7

6

97

5 5

9

5

7

Minimum spanning tree

• Começando em A, liga-se a G….

G

A

F

C

B

E D

5

6

6

5 5

5

Carteiro chinês

• O problema do carteiro chinês consiste em cobrir todos os arcos de uma rede partindo e chegando ao mesmo nó percorrendo uma distância total mínima

• Solução complica-se em redes mistas (incluindo arcos direccionados e outros não direccionados)

• Relevância em engenharia de ambiente na determinação de circuitos de remoção de recolha do lixo doméstico

Carteiro chinês

• Conceitos base:– Nó ímpar- um nó de que parte ou em que chega um

numero ímpar de arcos– Teorema de Euler- um grafo G possui um circuito

Euler (ou caminho Euler) se e só se possuir zero (ou exactamente dois) nós ímpares

Carteiro chinês

– Exemplos

Carteiro chinês• Algoritmo de Larson e Odoni:

– Identifiquem-se todos os nós ímpares de um grafo G. Admita-se que o seu número é m.

– Encontre-se o “matching” mais curto dos m nós ímpares entre os dois nós que constituem cada um dos m/2 pares.

– Para cada um dos pares de nós ímpares no “matching” mais curto encontrado no passo anterior, adicionem-se ao grafo G as arestas do percurso mais curto entre os dois nós do par. Obtém-se assim um grafo G1 sem nós ímpares

Carteiro chinês

– Encontre-se um circuito Euler em G1. Este circuito é a solução do problema do carteiro chinês no grafo original G

– Exemplo

d

a

c

b

e8

8

6 65

5

5

5

Carteiro chinês

• Alternativas– Duplicar d-e e a-b– Duplicar d-a e e-b– Duplicar d-c, c-b, a-c e c-e

• Melhor solução: duplicar d-a e e-b

Caixeiro viajante

• O problema do caixeiro viajante consiste na definição de um circuito mais curto ligando nós, sabendo-se a matriz das distâncias entre esses nós

• Aplicação na recolha de lixos em locais específicos como no caso da recolha de lixos nos hospitais

Caixeiro viajante

• Algoritmo de Larson e Odoni– Encontre-se a “minimum spanning tree” que cubra n

nós. Chame-se a esta árvore T.– Seja n0 o numero de nós impares dos n nós de T.

Encontre-se o “matching” mais curto entre estes nós utilizando um algoritmo apropriado. Considere-se o grafo consistindo dos arcos incluidos no “matching” óptimo como M. Crie-se o grafo H consistindo da união de M e T.

Caixeiro viajante

– O grafo H é um grafo Euleriano porque não contém nenhum nó ímpar. Desenhe-se o circuito Euleriano começando e acabando no nó desejado. Este circuito é a solução aproximada do problema do caixeiro viajante.

Caixeiro viajante

• Exemplo:– “Minimum spanning tree”

10

9

8

6

5

7

1

4

2

3 *

*

**

*

27

36

29 25 29

34

3111

36

*

Caixeiro viajante

– Construção do grafo H

10

9

8

6

5

7

1

4

2

3 *

*

**

*

27

36

29 25 29

34

3111

36 (29)

(71)

*

(43)

Caixeiro viajante

– Solução aproximada (duração total 371)

10

9

8

6

5

7

1

4

2

3

Caixeiro viajante

– Solução real (duração total 331)

10

9

8

6

5

7

1

4

2

3

TPC 3

• Caminho mais curto de 1 ou 2 a 8

1

2

4

3

5

6

7

8

8

76

5

8

8

36

7

9

10

TPC 3

• Encontrar a “minimum spanning tree” da seguinte rede

Nós 1 2 3 4

1 - 15 25 40

2 15 - - 30

3 25 - - 17

4 40 30 17 -

TPC 3

• Resolver o problema do carteiro chinês para o seguinte grafo

b

a f

e

d

c

8 8

9

9

7

7

4

4

7 5