15.053
O Problema do Fluxo de Custos
Mínimos
Uma rede com custos,
Terça-feira 2 de abril
Grafo Direcionado G = (N, A).
• O Problema do Caminho mais Curto
• Algoritmo de Dijkstra para solucionar o Problema
do Caminho mais Curto
Distribuir: Observações de Aula
Conjunto de nós N, conjunto de
arcos A;
Capacidade uijj no arco (i,j)
limite inferior 0 no arco (i,j)
Custo cij no arco (i,j)
Oferta/demanada bi para o nó i.
(Valores positivos indicam oferta)
capacidades, ofertas e
demandas
Minimizar o custo de envio de fluxo
de forma que o Fluxo que sai de i – Fluxo que
entra em i = bi
0 ¡≤ xij ≤ uij
1
2
O Problema do Caminho mais Curto
Fórmula
De maneira geral, a fórmula LP é dada como
Minimizar
sujeito a
3
Qual é o caminho mais curto de um nó-fonte
(freqüentemente chamado de s) até um nó-consumidor
(freqüentemente chamado de t)?
Qual é o caminho mais curto do nó 1 até o nó 6?
Suposições dessa aula:
1. Existe um caminho da fonte até os demais nós.
2. Todos os comprimentos de arcos são não-negativos
4
Outra Fórmula
Fórmula como um programa linear
De maneira geral, a fórmula para o caminho mais
curto de uma fonte, s, até o consumidor, t, é dada por
A fórmula LP para o caminho mais curto de uma
fonte s, para todos os demais nós é dada como
Minimizar
Minimizar
sujeito a
sujeito a
5
6
1
Algumas Perguntas a Respeito do
Problema do Caminho mais Curto
Possíveis Placares Esportivos
• Onde ele surge na prática?
• Flumbaya é um esporte aquático pouco comum
onde existem dois tipos de placares diferentes.
Eles podem marcar o gymbol, que vale 7 pontos,
ou pode marcar o quasher, que vale 5 pontos.
Um comentarista na TV anunciou o placar final
de 19 a 18 para um jogo. Isso é possível?
– Aplicações diretas
– Aplicações Indiretas (e freqüentemente sutis)
• Como é possível solucionar o Problema do Caminho mais
Curto?
– Algoritmo de Dijkstra
• Como é possível medir o desempenho de um algoritmo?
– medidas de tempo de CPU
– Garantias de Desempenho
• Como é possível definir que a solução é mesmo o
caminho mais curto?
– Conexão com a dualidade LP
7
8
Mais informações sobre Flumbaya
Mais informações sobre Flumbaya
Não existe um
caminho do nó
0 até o nó 18.
Um placar de
18 pontos é
impossível.
Dados: Gymbol vale n1 pontos
Quasher vale n2 pontos:
determinar se é possível marcar q pontos
A rede: G = (N, A), onde N = {0, …, q}
para cada nó j = 0 to q – n1 , (j, j+n1) ε A
para cada nó j = 0 to q – n2, (j, j+n 2) ε A
Pergunta: Existe um caminho em G do nó 0 para o nó q?
Fato: se n 1 e n 2 não possuem um divisor comum inteiro
(diferente de 1 e – 1), então o número de pontos que não
pode ser atingido e (n 1-1)(n2-1)/2. Ponto extra para quem
fornecer esse fato. (Cuidado, é difícil de provar).
9
Uma aplicação indireta: Encontrando
layouts ótimos para parágrafos
Uma aplicação indireta: Encontrando
layouts ótimos para parágrafos
TeX decompõe os parágrafos de maneira ótima ao
selecionar os pontos de quebra ótimos para cada linha. Ele
possui uma sub-rotina que calcula a atratividade F(i,j) de
uma linha que começa com a palavra i e termina com a
palavra j-1. Como podemos usar F(i,j) para criar um
problema do caminho mais curto cuja solução será a
resposta para o problema do parágrafo?
TeX decompõe os parágrafos de maneira ótima ao
selecionar os pontos de quebra ótimos para cada linha. Ele
possui uma sub-rotina que calcula a atratividade F(i,j) de
uma linha que começa com a palavra i e termina com a
palavra j-1. Como podemos usar F(i,j) para criar um
problema do caminho mais curto cuja solução será a
resposta para o problema do parágrafo?
10
TeX decompõe os parágrafos de maneira ótima ao
selecionar os pontos de quebra ótimos para cada linha.
Ele possui uma sub-rotina que calcula a atratividade
F(i,j) de uma linha que começa com a palavra i e
termina com a palavra j-1. Como podemos usar F(i,j)
para criar um problema do caminho mais curto cuja
solução será a resposta para o problema do parágrafo?
Cada palavra
corresponde a um
nó e um arco (i,j)
indica que a linha
começa com a
palavra i e
termina com a
palavra j-1.
Um caminho de Tex
para “termina”
corresponde a um
layout de parágrafo.
11
O valor de um
caminho é a “feiura”
desse caminho. 12
2
Uma Aplicação na Compressão de Dados:
Aproximação de Funções Lineares por Partes
No exemplo de parágrafo
• ENTRADA: Uma função linear por partes
• n diferentes decisões sim-não
– Decisão j: Sim significa iniciar a linha na palavra j
–
Não: não inicie a linha na palavra j
• O custo de cada decisão sim depende apenas
da próxima decisão sim
– f(i,j) é o custo de começar uma linha com a
palavra i, assumindo-se que a palavra j começará
a próxima linha.
– n pontos a 1 = (x1,y1), a 2 = (x2,y2),..., an = (xn,yn).
– x1 x2 ... xn.
•
Objetivo: aproximar f com menos pontos
– c* é o “custo” por ponto incluído
– cij = custo de aproximação da função por meio de pontos i,
i+1, . . ., j-1 por uma única linha ligando o ponto i ao ponto
j. (soma dos erros ou erros ao quadrado).
• Crie o problema do caminho mais curto com os
nós 1, 2, …, n+1 onde o custo do arco (i,j) é f(i,j).
Qual é o caminho mais curto de 1 até n+1
13
Aproximação de Funções Lineares por
Partes
• Objetivo: aproximar f com menos pontos
14
Ao aproximar as funções
• n diferentes decisões sim-não
– Decisão j: Sim significa iniciar a linha na palavra j
–
Não: não inicie a linha na palavra j
– c* é o “custo” por ponto incluído
– c36 = |a4 - b4| + |a5 - b5| = soma dos erros (outra
métrica também está OK.)
• O custo de cada decisão sim depende apenas
da próxima decisão sim
– cij é o custo de selecionar o ponto i seguido pelo
ponto j e leva em consideração o custo de
selecionar i e os custos de aproximação dos
pontos i+1, …, j-1.
15
16
Uma Etapa-Chave nos Algoritmos de
Caminho Mais Curto
Algoritmo de Dijkstra para o
Problema do Caminho mais Curto
Faça o exemplo com
seu colega. Encontre
os caminhos mais
curtos por meio de
inspeções.
Exercícios: encontre o caminho mais curto do nó 1 para
todos os demais nós. Registre as distâncias usando
rótulos, d(i) e o predecessor imediato de cada nó, pred(i).
d(1)= 0, pred(1)=0;
d(2) = 2, pred(2)=1
Encontra as demais distâncias, na ordem de
distâncias crescentes a partir do nó 1.
• Crie um problema do caminho mais curto com os
nós 1, … ,n onde o custo do arco (i,j) é cij. Qual é
o problema do caminho mais curto entre 1 e n?
17
• Deixe que d( ) denote um vetor de rótulos de
distância temporal.
• d(j) é o comprimento de um caminho do nó de
origem 1 até o nó j.
• Atualização do Procedimento (i)
para cada (i,j) ε A(i) faça
se d(j) > d(i) + cij então d(j) : = d(i) + cij e pred(j) : = i;
Até esse ponto, o melhor caminho de 1 a j tem o
comprimento de 78
18
3
Uma Etapa-Chave nos Algoritmos de
Caminho Mais Curto
Algoritmo de Dijkstra
• Deixe que d( ) denote um vetor de rótulos de
distância temporal.
• d(j) é o comprimento de um caminho do nó de
origem 1 até o nó j.
começo
d(s) : = 0 e pred(s) : = 0;
d(j) : = µ para cada j Î N - {s};
LISTA : = {s};
enquanto LISTA ¹ Æ faça
começo
deixe d(i) : = min {d(j) : j Î
LISTA};
remova nó i de LIST;
atualize (i)
se d(j) diminui, coloque j em LIST
fim
fim
• Atualização do Procedimento (i)
para cada (i,j) ε A(i) faça
se d(j) > d(i) + cij então d(j) : = d(i) + cij e pred(j) : = i;
P(1,j) é um “caminho” de 1 a j de comprimento 72.
Um Exemplo
Fim
Inicializar as
distâncias.
LIST = conjunto
de nós
temporários
Selecione o nó i em
LIST com um rótulo
de distância
mínima e então
atualize (i)
19
Leia os arcos
fora de i e
atualize d( ),
pred ( ) e LIST
Encontre o nó i
em LIST com a
mínima distância
21
20
O Resultado do Algoritmo de Dijkstra
Para encontrar o
caminho mais
curto a partir do nó
j, trace o caminho
de volta do nó até
a fonte.
Dijkstra fornece o caminho mais curto do nó 1
até os demais nós. Fornece a árvore de caminho
mais curto.
22
A solução do fio e dualidade LP
Comentários sobre Tempo de
Execução
• algoritmo de Dijkstra é eficaz na sua forma atual.
O tempo de execução cresce como n2.
• Pode se tornar bem mais eficaz
• Na prática, é executado em tempo linear com o
número de arcos (ou quase isso).
23
Deixe que d(j) denote a distância do nó até a fonte.
d(1) = 0
Dual:
d(2) <= d(1) + 2;
Máx d(t)-d(s)
d(5) <= d(2) + 2; d(2) <= d(5) + 2
p.q. d(s) = 0
d(5) <= d(3) + 3; d(3) <= d(5) + 3
d(j) <= d(i) + c24ij
etc.
4
A solução do fio
A solução do fio
É possível obter o caminho
mais curto do nó 1 ao nó 6?
Se a resposta por sim,
explique por quê.
Imagine substituir cada arco por um fio de mesmo
comprimento. Dessa forma, o arco (1,3) seria substituído
por um fio de 4 polegadas de comprimento, unindo o nó
1 ao 3.
Agora segure o nó 1 em uma mão e o nó 6 na outra e
estique o fio.
Observação : Até certo
ponto, estamos
maximizando a distância
física do nó 1 ao nó 6.
25
26
Resumo
Algumas consideração finais
• Aplicações diretas e indiretas para o problema
do caminho mais curto
• O algoritmo de Dijkstra encontra o caminho mais
curto do nó 1 até os demais nós em ordem
crescente de distância do nó fonte.
• A operação de gargalo identifica o rótulo de
distância mínima. É possível acelerar a operação
e obter um algoritmo incrivelmente eficaz.
• A solução do fio otimiza a LP dual assim como o
problema do caminho mais curto.
• O problema do caminho mais curto está sempre
presente durante a otimização de redes
27
• Existe uma conexão interessante com a
programação dinâmica
• Existem outras técnicas de solução. Veremos
uma em outra aula.
28
5