O algoritmo sucessivo de caminho mais curto (SSP) é uma técnica poderosa para resolver o problema mínimo de fluxo de custo em uma rede. Aqui está um detalhamento do processo envolvido na implementá -lo:
1. Definição do problema: *
Rede: Você está trabalhando com um gráfico direcionado (rede) representado por:
*
nós (vértices): `V` (por exemplo, fábricas, armazéns, cidades)
*
arcs (bordas): `E` (por exemplo, estradas, oleodutos, links de comunicação)
* Capacidades
: Cada arco `(u, v)` em `e` tem uma capacidade` c (u, v) `representando o fluxo máximo que pode passar por ele.
*
Custos: Cada arco `(u, v)` em `e` tem um custo` custo (u, v) `representando o custo por unidade de fluxo através desse arco.
*
Supplência/demanda: Cada nó `v` em` v` tem um suprimento `b (v)`.
* Se `b (v)> 0`, o nó` v` é uma fonte * com uma fonte de `b (v)` unidades.
* Se `b (v) <0`, o nó` v` é um * coletor * com uma demanda de unidades `-b (v)`.
* Se `b (v) =0`, nó` v` é um nó de transbordo.
*
Objetivo: Encontre a atribuição de fluxo que minimize o custo total do envio do fluxo através da rede, satisfazendo as restrições de oferta/demanda e as restrições de capacidade.
2. Inicialização: *
Rede residual: Crie uma rede residual `g_f` com base na rede original` g`. Inicialmente, `g_f =g`. Esta rede acompanha a capacidade disponível. Para cada arco `(u, v)` em `g`, a capacidade residual é` c_f (u, v) =c (u, v) - f (u, v) `, onde` f (u, v) `é o fluxo de corrente nesse arco. Inicialmente, `f (u, v) =0` para todos os arcos.
*
Fluxo: Inicialize o fluxo `f (u, v) =0` para todos os arcos na rede original.
*
potencials (preços): Inicialize uma função potencial `pi (v)` para cada nó `v` em` v`. Um ponto de partida comum é `pi (v) =0` para todos` v`. Os potenciais são cruciais para lidar com ciclos de custo negativos.
3. Etapas do algoritmo: O núcleo do sucessivo algoritmo de caminho mais curto é um processo iterativo:
um.
Encontre uma fonte e uma pia: Selecione um nó de origem `s` (onde` b (s)> 0`) e um nó de pia `t` (onde` b (t) <0`) na rede. Se não houver esses nós, o algoritmo está completo.
b.
Computação de caminho mais curto: Encontre o caminho mais curto `p` de` s` para `t` na *rede residual *` g_f` usando os custos *reduzidos *. O custo reduzido para um arco `(u, v)` é definido como:
`` `
Cost_Reduced (u, v) =custo (u, v) + pi (u) - pi (v)
`` `
* O objetivo de usar custos reduzidos é eliminar os ciclos de custo negativos. Se os potenciais `pi` forem escolhidos de tal forma que` Cost_Reduced (u, v)> =0` para todos os arcos, o algoritmo de Dijkstra pode ser usado para encontrar o caminho mais curto.
* Se os custos negativos permanecerem após a aplicação de potenciais, o algoritmo Bellman-Ford pode ser usado (mas geralmente é mais lento).
c.
Fluxo de aumento: Seja `delta` o mínimo de:
* `b (s)` (o suprimento restante na fonte `s`)
* `-b (t)` (a demanda restante na pia `t`)
* A capacidade residual mínima ao longo do caminho mais curto `p`:` min {c_f (u, v) | (u, v) em p} `
Atualize o fluxo ao longo do caminho `p` por` delta`:
* Para cada arco `(u, v)` em `p`:
* `f (u, v) =f (u, v) + delta`
* Atualizar capacidade residual:`c_f (u, v) =c (u, v) - f (u, v)`
* Se `(u, v)` existe na rede original, atualize sua borda reversa na rede residual:Crie a borda `(v, u)` em `g_f` se não existir com` c_f (v, u) =f (u, v) `.
d.
Atualizar oferta e demanda: * `b (s) =b (s) - delta`
* `b (t) =b (t) + delta`
e.
Atualizar potenciais (variante Bellman-Ford): Esta é uma etapa * crucial * para manter custos reduzidos não negativos e garantir um comportamento correto. Após aumentar o fluxo, você precisa atualizar os potenciais. Uma abordagem comum (frequentemente usada em conjunto com Dijkstra após um Bellman-Ford inicial) é uma variante Bellman-Ford. Isso pode ser feito usando as distâncias mais curtas da iteração anterior, mas aplicada em todos os vértices. A chave é garantir que quaisquer ciclos de custo negativos introduzidos pelo aumento do fluxo sejam tratados.
*
Opção 1:Full Bellman-Ford (menos eficiente): Re-Run Bellman-Ford de um nó arbitrário `r` para todos os outros nós em` g_f` usando os custos reduzidos. Seja `d (v)` a menor distância de `r` a` v`. Atualize os potenciais:`pi (v) =pi (v) - d (v)`. Isso garante `Cost_Reduced (u, v)> =0` para todos os arcos após a atualização, mas é relativamente lento.
*
Opção 2:Algoritmo de Johnson (eficiente): Execute Bellman-Ford uma vez para calcular potenciais iniciais. Posteriormente, use o algoritmo de Dijkstra usando os custos reduzidos. Após cada aumento, recomponha os potenciais usando o resultado de Dijkstra.
f.
Repita: Volte à etapa (a) e repita o processo até que todos os suprimentos e demandas sejam atendidos (`b (v) =0` para todos os nós` v`).
4. Rescisão: O algoritmo termina quando todos os suprimentos e demandas são atendidos. O fluxo resultante `f (u, v)` para todos os arcos `(u, v)` na rede original representa o fluxo de custo mínimo.
Estruturas de dados -chave: *
Lista de adjacência/matriz: Para representar a rede `g` e a rede residual` g_f`. As listas de adjacência são tipicamente mais eficientes para gráficos esparsos.
*
Matriz de fluxo: Para armazenar o fluxo atual `f (u, v)` em cada arco.
*
Matriz de capacidade: Para armazenar as capacidades originais `c (u, v)` de cada arco.
*
Matriz de capacidade residual: Armazenar as capacidades residuais `c_f (u, v)` na rede residual.
*
Matriz potencial: Para armazenar os potenciais `pi (v)` para cada nó.
*
fila de prioridade (heap): Usado no algoritmo de Dijkstra para uma computação de caminho mais curto eficiente.
Considerações de código (exemplo python - simplificado): `` `Python
importar heapq
def sucessive_shortest_path (gráfico, capacidade, custo, suprimento):
"" "
Implementa o sucessivo algoritmo de caminho mais curto.
Args:
Gráfico:um dicionário representando o gráfico como uma lista de adjacência.
As chaves são nós, os valores são listas de nós vizinhos.
Capacidade:um dicionário representando a capacidade de cada borda (u, v).
Custo:um dicionário representando o custo de cada borda (u, v).
Supplência:um dicionário que representa a oferta/demanda de cada nó.
Valores positivos são fornecimento, valores negativos são demanda.
Retornos:
Um dicionário representando o fluxo em cada borda, ou nenhuma, se não houver solução viável.
"" "
fluxo ={} # inicialize o fluxo para zero
Para você no gráfico:
para V em gráfico [u]:
fluxo [(u, v)] =0
potencial ={nó:0 para nó no gráfico} # inicialize potenciais
enquanto é verdade:
Fontes =[Nó para o nó no suprimento se fornecimento [nó]> 0]
Pia =[Nó para o nó no suprimento se suprimento [nó] <0]
Se não for fontes ou não afundar:
quebrar # toda a oferta/demanda satisfeita
fonte =fontes [0]
pia =pia [0]
# Caminho mais curto usando dijkstra com custos reduzidos
dist, prev =dijkstra (gráfico, capacidade, custo, potencial, fonte, pia, fluxo)
se dist [pia] ==float ('inf'):# nenhum caminho encontrado, inviável
retornar nenhum # ou lidar com este caso de maneira diferente
# Fluxo de aumento
delta =min (suprimento [fonte], -supply [sink])
curr =pia
enquanto curr! =fonte:
prev_node =prev [curr]
delta =min (delta, capacidade [(prev_node, curr)] - fluxo [(prev_node, curr)])
curr =prev_node
curr =pia
enquanto curr! =fonte:
prev_node =prev [curr]
fluxo [(prev_node, curr)] +=delta
if (curr, prev_node) em capacidade:
fluxo [(curr, prev_node)] -=Delta # Fluxo para trás
outro:
fluxo [(curr, prev_node)] =-delta # inicialize, se necessário.
curr =prev_node
fornecimento [fonte] -=delta
Supply [Sia] +=Delta
# Atualize os potenciais usando as distâncias de Dijkstra
para nó no gráfico:
potencial [nó] +=dist [nó]
fluxo de retorno
Def Dijkstra (gráfico, capacidade, custo, potencial, fonte, afundamento, fluxo):
"" "
O algoritmo de Dijkstra com custos reduzidos.
"" "
dist ={node:float ('inf') para o nó no gráfico}
prev ={nó:nenhum para nó no gráfico}
dist [fonte] =0
pq =[(0, fonte)] # fila de prioridade (distância, nó)
enquanto PQ:
d, u =heapq.heappop (PQ)
Se d> dist [u]:# exclusão preguiçosa
continuar
para V em gráfico [u]:
# Considere apenas arestas com capacidade residual> 0
Se a capacidade [(u, v)] - fluxo [(u, v)]> 0:
reduzido_cost =custo [(u, v)] + potencial [u] - potencial [v]
se dist [v]> dist [u] + reduzido_cost:
dist [v] =dist [u] + reduzido_cost
prev [v] =u
heapq.heappush (pq, (dist [v], v))
retornar dist, prev
Exemplo de uso:
Gráfico ={
'S':['a', 'b'],
'a':['b', 't'],
'B':['T'],
'T':[]
}
capacidade ={
('S', 'A'):10,
('S', 'B'):5,
('a', 'b'):4,
('a', 't'):8,
('B', 'T'):12
}
custo ={
('S', 'A'):2,
('S', 'B'):4,
('a', 'b'):1,
('a', 't'):7,
('B', 'T'):5
}
suprimento ={
'S':15,
'a':0,
'B':0,
'T':-15
}
fluxo =sucessivo_shortest_path (gráfico, capacidade, custo, suprimento)
Se fluxo:
Imprimir ("Atribuição de fluxo:", fluxo)
# Calcule o custo total
total_cost =soma (fluxo [(u, v)] * custo [(u, v)] para (u, v) no fluxo)
Imprimir ("Custo total:", Total_Cost)
outro:
Imprimir ("Nenhuma solução viável encontrada")
`` `
Considerações importantes: *
ciclos de custo negativo: O algoritmo SSP foi projetado para lidar com ciclos de custo negativos. A função potencial `pi (v)` é crítica para isso. Se você não atualizar os potenciais corretamente, o algoritmo poderá não convergir ou produzir uma solução incorreta.
*
Dijkstra's vs. Bellman-Ford: * Se você * sempre * mantém custos reduzidos não negativos, o algoritmo de Dijkstra é muito mais rápido para encontrar caminhos mais curtos. Este é o cenário ideal e geralmente é alcançado com as atualizações em potencial adequadas.
* Se você não pode garantir custos reduzidos não negativos, deve * usar a complexidade do tempo Bellman-Ford, que é mais lenta (O (v * e)). É frequentemente usado apenas para o cálculo potencial inicial.
*
Rede residual: Manter a rede residual corretamente é essencial. Lembre -se de criar bordas nas costas quando o fluxo é empurrado ao longo de um arco.
*
Complexidade computacional: A complexidade do algoritmo SSP depende do algoritmo de caminho mais curto usado e do número de iterações. Na pior das hipóteses, pode ser pseudo-polinomial se as capacidades forem grandes.
*
Algoritmos alternativos: Para problemas mínimos de fluxo de custo em larga escala, outros algoritmos, como o algoritmo de rede simplex, geralmente são mais eficientes.
Em resumo, o sucessivo algoritmo de caminho mais curto é um método poderoso e conceitualmente claro para resolver problemas mínimos de fluxo de custos. Compreender os papéis da rede residual, os custos reduzidos e a função potencial é essencial para implementá -la corretamente. Escolha o algoritmo de caminho mais curto apropriado (Dijkstra ou Bellman-Ford) com base no fato de você poder garantir custos reduzidos não negativos. Lembre -se de lidar com as atualizações na oferta e demanda e também atualizar os potenciais corretamente.
