Push-relabel algorithm
The following image illustrates a partially executed flow graph and the Push-Relabel algorithm, with the respective residual graph displayed on the right. The algorithm followed a FIFO order of selecting nodes and then selected nodes by alphabetical order when they were simultaneously activated. Active nodes are the ones that have excess in the pre-flow.
Based on the process illustrated, mark the correct alternative of the next step in the algorithm:
a) Relabeling of 'c', transforming 'h' to 2, and returning the excess flow to 'b' using Push.
b) Relabeling of 'a', transforming 'h' to 8, and returning the excess flow to 'S' using Push.
c) Relabeling of 'c', transforming 'h' to 8, and returning the excess flow to 'S' using Push.
d) Relabeling of 'e', transforming 'h' to 1, and pushing the excess flow to 't'.
e) None of the above
Original idea by: Giorgio Rossa
Linda questão, mas tenho um problema com ela. Entendi que a FIFO é mantida para colocar todos os vértices ativos. Entendi também que o algoritmo se baseia em selecionar um nó, dar relabel nele e depois dar pushes dele até esgotar seu excesso ou saturar as arestas no grafo residual saindo dele. Entendi também que, se um vértice recebe um push, ele vai pra FIFO (se já não estiver lá). Pois bem, eis a questão. Quando os pushes saturam as arestas saindo, mas o vértice continua com excesso, ele entra de novo para a FIFO? Deveria, não? Após os vértices que receberam os pushes dele? Mas, neste caso, o relabel de a para 8 e push dele de volta para S já deveria estar executado antes de selecionar o e, certo? Mas o grafo "after some steps" não mostra isso. Fiquei confuso.
ResponderExcluirOlá professor, obrigado! Realmente, eu fiz a questão errado! Realmente, quando satura as operações de push acredito que o node deveria voltar para a fila (ainda assim, poderia existir uma implementação que todos os push e relabel possíveis sao executados em cada nó, mas não achei indicação disso em nenhum lugar). O node 'e' estava atrás da fila e não deveria ter sido executado o push. Atualizei a imagem com dois passos anteriores, e adicionei o meu erro como uma das alternativas não válidas.
ExcluirMelhorou bem, mas agora o problema é que a figura ficou muito grande para caber no blog. Vai ficar sobrando, o que é feio. Tem como resolver isso?
ExcluirEu diminui o tamanho para ficar dentro das margens.
ExcluirOk, ficou boa agora. Vou pegar. Mudei umas coisinhas.
ResponderExcluir