Localizando ciclos negativos para o algoritmo de cancelamento de ciclo

9

Estou implementando o algoritmo de cancelamento de ciclo para encontrar uma solução ideal para o problema de fluxo de custo mínimo. Ao encontrar e remover ciclos de custo negativos na rede residual, o custo total é reduzido em cada rodada. Para encontrar um ciclo negativo, estou usando o algoritmo bellman-ford.

Meu problema é: o Bellman-ford encontra apenas ciclos que podem ser acessados ​​a partir da fonte, mas também preciso encontrar ciclos que não são acessíveis.

Exemplo: na rede a seguir, já aplicamos um fluxo máximo. A beira(A,B)torna muito caro. Na rede residual, temos um ciclo de custo negativo com capacidade1. Removê-lo, nos daria uma solução mais barata usando bordas(A,C) e (C,T), mas não podemos alcançá-lo da fonte S.

Etiquetas: Custo / Fluxo / Capacidade

insira a descrição da imagem aqui

Obviamente, eu poderia executar o Bellman-ford repetidamente com cada nó como fonte, mas isso não parece uma boa solução. Estou um pouco confuso porque todos os papéis que li parecem pular esta etapa.

Você pode me dizer, como usar o bellman-ford para encontrar todos os ciclos negativos (acessíveis ou não)? E se não for possível, qual outro algoritmo você propõe?

Patrick Schmidt
fonte
Se um ciclo não pode ser alcançado através da fonte, como isso pode afetar o fluxo total?
Nicholas Mancuso
Não afetará o valor do fluxo, mas o custo total. Veja o novo exemplo.
Patrick Schmidt
2
Eu acho que você deveria estar carregando Bellman-Ford da pia, não? Se você encontrar um fluxo máximo,f, abaixo do gráfico residual Gf não haverá um caminho de s para t. Portanto, Bellman-Ford deve ser executado emGf com t.
Nicholas Mancuso

Respostas:

2

Para expandir meu comentário, lembre-se, esse algoritmo para encontrar fluxo de custo mínimo baseia-se no fato de que fé máximo. Executando primeiro a Ford-Fulkerson para encontrarf e a rede residual resultante Gf, o custo f é então reduzido por encontrar ciclos negativos em Gf. Ou seja, encontrando ciclos negativos emGf nós não mudamos a quantidade de fluxo, f, mas apenas o custo.

Agora, executando Bellman-Ford de t no Gf podemos rastrear para trás em arestas com fluxo não negativo (por definição de Gf) Se os ciclos estiverem adjacentes a qualquer aresta nesses caminhos, podemos "transferir" uma certa quantidade de fluxo para outras arestas do ciclo. Em outras palavras, mantemos o fluxo líquido por algum ciclo o mesmo, mas somos capazes de alterar o custo.

Observe um ciclo inacessível de tdeve ter fluxo zero. Caso contrário, teríamos uma contradição emf sendo máximo.


Peço desculpas pela "ondulação da mão" dessa explicação. Vou tentar ser mais formal quando tiver tempo esta noite.

Nicholas Mancuso
fonte
Obrigado, sua última frase deixa claro. Portanto, basta lidar com ciclos acessíveis a partir deT.
Patrick Schmidt
0

Minha sugestão: você deve iniciar o algoritmo a partir de T, a fim de encontrar um ciclo negativo em sua rede residual. O resultado deve ser o mesmo, mas você pode alcançar o círculo

Sven Jung
fonte
1
Isso funciona para este gráfico, mas você pode ter ciclos negativos que não estão conectados a S ou T. Suspeito que o OP queira uma solução que funcione em geral.
Peter Shor
sim, em geral você não consegue encontrar todos os ciclos negativos, mas o OP quer melhorar sua rede residual verificando os custos. Então círculos negativos inacessível não importa
Sven Jung
Eu quero usar isso para obter um fluxo de custo mínimo. Portanto, a nova pergunta seria: É suficiente eliminar todos os ciclos alcançáveis ​​da piaT(Na rede residual). No momento não consigo encontrar um exemplo contrário
Patrick Schmidt
Você pode visualizar um fluxo como originário em S e indo para Tou inverta todas as arestas e veja-as como originárias de T e indo para S. Se eliminar todos os ciclos alcançáveis ​​a partir da fonteS não funciona, eliminando todos os ciclos acessíveis da pia Tnão vai funcionar. A fonte e o coletor se comportam simetricamente.
Peter Shor
é claro que é o mesmo se você inverter todas as arestas e começar com T, porque nada mudou. Mas por que não começar em T sem inverter as arestas?, Então você deve encontrar um ciclo negativo acessível, se existente. A questão é, se os ciclos negativos inacessíveis realmente não importa
Sven Jung
0

Eu acho que não é suficiente rodar Bellman-Ford de T ou S. Considere um exemplo em que há uma borda de S para T e um ciclo de custo negativo não alcançável nem de S nem de T.

Uma solução é adicionar um S 'auxiliar e adicionar uma aresta de S' a qualquer outro vértice com custo 0. Em seguida, execute Bellman-Ford da S '. Desta forma, todos os ciclos negativos são alcançáveis ​​a partir de S '.

Além disso, você realmente não precisa adicionar esse vértice auxiliar S 'em sua implementação. Apenas inicialize d (v) = 0 para qualquer vértice v.

Veja como a Boost Graph Library a implementa.

Hongjie Chen
fonte