Qual é a diferença entre o fluxo máximo e o fluxo máximo?

Question

Qual é a diferença entre o fluxo máximo e o fluxo máximo.Estou lendo estes termos enquanto trabalhava em algoritmos Ford Fulkerson e eles são bastante confusos.Eu tentei na internet, mas não consegui uma resposta razoável.Eu acredito que o fluxo máximo é bastante claro, pois significa que a quantidade máxima de fluxo que pode ser transferida da fonte para afundar em uma rede, mas o que é exatamente o fluxo máximo.

Por favor, responda em termos leigos, se possível.

obrigado.

Answer 1

Resposta curta:

Pense no topo das montanhas, Cada um deles é uma solução máxima, Não há lugar próximo que é maior que eles, mas apenas o topo da montanha Everest tem a altura máxima e é, portanto, a solução máxima.

Resposta mais longa:

Deixe-me explicar em termos geométricos: Pense em um avião (por exemplo, uma grande paz de papel). Cada ponto do avião é uma solução possível para o problema. A altura de cada ponto é a qualidade da solução correspondente a esse ponto. Em otimização, queremos encontrar a solução ideal, isto é, o ponto mais alto no avião. Uma ideia de encontrar a solução ideal é começar de uma possível solução no plano e melhorar pouco a pouco: Cada vez que nos movemos de um ponto para perto, o que é maior. Isso é chamado de algoritmo de pesquisa local. Este processo pára quando chegamos a um ponto que é maior do que todos os pontos próximos. Tal ponto é chamado de ótimo local. A solução correspondente é chamada máxima, pois não podemos aumentar a qualidade da solução, movendo-se para qualquer solução perto dela. No entanto, uma solução máxima não precisa ser a solução ideal, é ideal em comparação com seus vizinhos.

Existem condições comuns que, se satisfeitas Nós não teremos ótimos locais no plano que não são otimais globalmente. Em tais situações, podemos usar algoritmos de busca locais para encontrar a solução ideal. Uma dessas condições é se o plano de soluções é convexo, intuitivamente para cada dois pontos, temos todos os pontos na linha conexão também no espaço da solução e A qualidade de cada uma delas pode ser determinada a distância relativa do ponto para os dois endpoints e a qualidade dos dois endpoints. Otimização sobre espaços convexes é estudado em otimização convexa .

Agora, vamos voltar ao problema do fluxo máximo. Corrigir um gráfico como entrada. Pense em cada fluxo que satisfaça a capacidade e a preservação do fluxo requisitos como ponto. Nós chamamos esses fluxos válidos. Queremos encontrar um fluxo máximo. Dois pontos estão próximos um do outro se pudermos obter um aumentando ou diminuindo o fluxo através de um caminho da fonte para a pia.

Podemos começar pelo fluxo onde o fluxo em todas as bordas são zero (Este é um fluxo válido). Em cada passo, encontramos um caminho da fonte para a pia no gráfico de capacidade restante atualizado (o peso de cada borda é a quantidade de sua capacidade que não está sendo usada) De alguma forma (por exemplo, usando BFS) e aumente o fluxo adicionando isso. Isso nos dá um algoritmo de busca local. O problema é que o espaço de soluções não é convexo e Podemos acabar com um fluxo que não podemos aumentar mais, mas não é um fluxo máximo.

O que podemos fazer? Uma ideia é mudar o espaço de soluções para um convexo. Para a intuição, pense em uma estrela em um avião. Os pontos dentro da estrela não fazem um espaço convexo Mas podemos transformá-lo em um espaço convexo, incluindo mais pontos em nosso espaço de solução e transformando-o em um Pentágono.

Isso é essencialmente o que fazemos considerando o fluxo existente em as bordas originais do gráfico Como novas bordas (chamadas bordas residuais ) onde fluir sobre eles corresponde à diminuição do fluxo existente nas bordas originais. Isso torna o espaço convexo e nosso algoritmo de pesquisa local não fica preso em soluções que são localmente ideais, mas não globalmente ideais.