Problemas de Optimização em Redes
V 1.1, V.Lobo, EN / ISEGI, 2008
Problemas de optimização em redes
„
Problemas de
Optimização em
redes
Conceito de grafo
…
…
„
Nomenclatura de grafos (1)
„
Nós
… Ou
„
Nó
„
Nó
Lacetes
Circuito Hamiltoniano
… Passa
„
„
„
Cadeia
os nós estão ligados
Matriz de adjacências
com uma linha/coluna para cada nó, e valores 0
ou 1 consoante haja ou não ligação
de arcos
Caminho
„
Circuito
… Cadeia
… Ciclo
onde os arcos têm a mesma orientação
onde o nó inicial e final são o mesmo
onde os arcos têm a mesma orientação
Exemplo: Parque natural “Seervada”
„
Existem 7 “acampamentos”
… Um
é o de entrada para o parque: “O”
é o topo da montanha “T” onde muitos turistas
querem ir
… Um
todos os arcos
Grafo conexo
… NxN,
(outros…TSP, PERT/CPM, Min Cost flow, etc,etc,,,)
Ciclo
Circuito Euleriano
… Todos
Qual é o conjunto mínimo de arcos que liga todos os nós (ou
quais os trajectos a alcatroar para se poder ir a qualquer lugar).
„
por todos os nós
… Atravessa
C
De que modo posso fazer passar o máximo de pessoas (ou
água, ou contentores…)
… Cadeia
que começam e acabam no mesmo nó
Nomenclatura de grafos (3)
„
„
arcos orientados, ou linhas orientadas
… Arcos
B
4
1
Qual o caminho mais curo de “A” para “B”
… Sequência
Arco
orientado
Arcos
… Ou
„
aresta
linhas não direccionadas
4
2
5
Nomenclatura de grafos (2)
nodos, ou vértices
Arestas
… Ou
„
Nó
3
Minimum spanning tree (árvore de cobertura mínima)
…
„
4
1
E
G
2
F
Máximo fluxo
…
„
7
Caminho mais curto
…
„
Muitos problemas
Muitas aplicações
7
D
5
A
„
Só os jipes do parque é que podem circular nas
picadas. Cada picada:
… Demora
um determinado tempo a percorrer (custo)
uma quantidade máxima de tráfego que pode
acolher (senão afecta o equilíbrio ecológico).
… Tem
1
Problemas de Optimização em Redes
V 1.1, V.Lobo, EN / ISEGI, 2008
Exemplo: Parque natural “Seervada”
7
A
„
Modelo em rede
… Custo
„
2
2
O
dos arcos
5
B
4
1
„
T
„
ligando os mais próximos, até estarem todos
ligados
… Neste caso, é possível provar que a solução é óptima !
4
„
o caminho mais barato para chegar a “T” ?
- Escolher os dois nós mais próximos
Escolher o nó que esteja mais próximo de algum dos
nós escolhidos
… 3 – Repetir 2 até não haver mais nós
… 2-
Máximo fluxo
ligar todos os acampamentos à internet, por onde
devem passar os cabos
„
Caminho mais curto
2
2
O
A
B
C
D
E
T
0
2
5
4
-
-
-
0
2
-
7
-
-
0
1
4
3
-
0
-
4
.
0
1
5
0
7
B
C
D
E
T
D
5
4
5
B
4
1
O
A
7
A
Forma matricial
O
Exemplo
Minimum Spanning Tree
Exemplo de MST
„
Passos:
…1
pessoas posso levar a “T” ? Como ?
… Para
„
Algoritmo “guloso”
… Vamos
7
E
Caminho mais curto
… Quantas
„
5
1
3
C
Problemas
… Qual
D
4
Minimum Spanning Tree
1
3
T
Algoritmo de Dijkstra
… Ir
7
E
„
4
C
„
“expandindo” os nós “conhecidos”
Passos
… Calcular
„
A
…
D
T
…
B
O
0
os custos para os vizinhos imediatos
Calcular os custos para os vizinhos dos vizinhos
Ver se já estão na tabela
Se tivermos um custo menor, substituir a entrada na
tabela.
… Exemplo
E
C
Problema do caixeiro viajante
Exemplo do algoritmo de Dijkstra
7
A
„
O
„
O
A
1ª iteração
O
A
B
C
D
E
T
0
2
5
4
-
-
-
4
A
B
C
D
E
T
0
2
4
4
9
8
-
O
0
2
3
7
5
-
A
0
1
4
3
-
0
5
4
-
C
B
C
D
„
3ª iteração
E
T
5
1
3
1
T
„
TSP – Travelling Salesman Problem
„
Problema paradigmático para uma classe muito
importe de problemas
7
… “NP-completo”
E
4
C
O
D
4
B
5
O
2ª iteração
B
2
2
„
O
A
B
C
D
E
T
0
2
5
4
-
-
-
0
2
-
7
-
-
0
1
4
3
-
0
-
4
.
0
1
5
0
7
Problema “difícil”
… Se
o número de variáveis aumenta, o trabalho
necessário para o resolver aumenta “mais que
polinomialmente” (tanto quanto sabemos…)
… Única maneira de garantir o óptimo é experimentar
todas as soluções possíveis
… Número de soluções possíveis: (n-1)!
„
1! = 1
10! =3.628.800 100!=9,3e+157
0
……
2
Problemas de Optimização em Redes
V 1.1, V.Lobo, EN / ISEGI, 2008
Problema do caixeiro viajante
„
Enumeração exaustiva
… Leva
„
Exemplo do caixeiro viajante
„
demasiado tempo
Branch-and-bound (ou A*)
… Enumeração
“implícita” das soluções
reduzir muito drasticamente o tempo necessário
… Ideia base
… Nº
… Pode
„
„
„
„
Obter uma solução “incremental” onde o custo é
monotonamente crescente
Começar por uma solução (o melhor possível)
Ir construindo soluções até atingir o custo daquela que já temos
Exemplo
Usando Bruxelas como
base, qual o circuito mais
curto ?
„
de soluções possíveis
3! = 6
… Utilização
Paris
Paris
Londres
Bruxelas
Andorra
0,0
3,5
3,0
6,4
de B&B
Londres Bruxelas Andorra
3,5
3,0
6,4
0,0
4,6
9,1
4,6
0,0
8,8
9,1
8,8
0,0
3