MAC0325  Otimização Combinatória

Recuperação

     A recuperação consiste em uma tarefa de programação que deverá ser entregue até o dia 4 de fevereiro. Nesta tarefa vocês deverão implementar três algoritmos para o problema do fluxo máximo.

     A implementação deverá ser em C e utilizar as estruturas de dados da notas de aulas de MAC0328 Algoritmos em grafos do professor Paulo Feofiloff. Em particula, do capítulo "Fluxos em redes" o programa deve utilizar a

Estruturas de dados para redes de fluxo
descrita, com as adaptações necessárias.

     Os algoritmos que deverão ser implementados são:

  1. Método dos incrementos máximos (aula16, Maximum capacity augmenting paths);
  2. Algoritmo de Edmonds e Karp (aula 18, Shortest augmenting paths);
  3. Algoritmo genérico dos pré-fluxos (aula 20).

A idéia é que vocês tentem fazer a implementação mais eficiente que puderem.

  A rede deve ser lida da entrada padrão e a saída deve ser escrita na saída padrão. O formato da entrada da rede é uma pequena variação do The Famous DIMACS Graph Format que é usado nos

DIMACS Implementation Challenges
Uma descrição deste formato de entrada e do formato de saída pode ser vista a partir de
CATS Maximum Flow Page,
siga o link formats. Após ler a rede no formato de entrada, o seu programa deve, para cada um dos três algoritmos:
  1. encontrar o fluxo máximo na rede;
  2. medir e escrever o tempo consumido para resolver o problema;
  3. escrever o fluxo encontrado no formato de saída.

 

 

 

 

Last modified: Fri Dec 19 15:11:30 BRST 2008