Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05016:2017-1-trabalhos [2017/05/03 12:53]
marcus [Trabalho 3 (Fluxo s-t máximo)]
+++ inf05016:2017-1-trabalhos [2017/07/25 07:36] (Actual)
@@ Linha 1: / Linha 1: @@
+Status das entregas (25 de julho 2017):
+^ Cartão ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^
+| 120921 | s  | s  | s  | s  | s  |
+| 161896 | s  | s  | s  | s  | s  |
+| 205691 | s  | s  | s  | s  | s  |
+| 205798 |    |    |    |    |    |
+| 213917 |    |    |    |    |    |
+| 218319 | s  |    |    |    |    |
+| 218326 | s  | s  | s  | s  | s  |
+| 219436 |    |    |    |    |    |
+| 220505 | s  | s  | s  | s  | s  |
+| 228401 | s  |    |    |    |    |
+| 228483 | s  | s  | s  | s  | s  |
+| 228527 | s  | s  | s  | s  | s  |
+| 242239 | s  |    |    |    |    |
+| 242249 | s  |    |    |    |    |
+| 242274 | s  | s  | s  | s  | s  |
+| 259094 | s  | s  | s  | s  | s  |
+| 262528 | s  |    |    |    |    |
+| 264311 | s  |    |    |    |    |
+| 273103 | s  | s  |    |    |    |
+| 282838 | s  |    |    |    |    |
+| 286120 | s  | s  | s  | s  | s  |
+| 286134 | s  | s  | s  | s  | s  |
+| 286244 | s  |    | s  | s  | s  |
+| 291000 | s  | s  | s  | s  | s  |
 ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ====
@@ Linha 151: / Linha 179: @@
 ==== Trabalho 3 (Fluxo s-t máximo) ====
-Entrega: 02/11/2012
+Entrega: 23/05/2017
 === Objetivos ===
@@ Linha 159: / Linha 187: @@
 === Casos de teste ===
   * Um gerador de casos de teste em formato DIMACS em C é disponível {{http://www.inf.ufrgs.br/~mrpritt/washington.c|aqui}}.
+  * Novo: Uma versão melhor do {{http://www.inf.ufrgs.br/~mrpritt/aa/new_washington_test_dir.tar.gz|gerador}}.
   * Documentação:
 <code>
@@ Linha 256: / Linha 285: @@
 }
 </code>
+==== Trabalho 4 (Emparelhamentos) ====
+Entrega: 13/6/2017
+=== Objetivos ===
+  * Implementar o algoritmo de Hopcroft-Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos.
+  * Documentar a implementação, em particular as estruturas de dados para a representação do problema.
+  * Conduzir testes, que demonstram que a complexidade do algoritmo é O(sqrt(n)(n+m)). Em particular: complexidades O(sqrt(n)) para o número de fases e O(n+m) para a extração de um conjunto maximál de caminhos aumentantes.
+  * Decidir experimentalmente: a abordagem por redução para um problema de fluxo é mais eficiente?
+=== Casos de teste ===
+  * Gerar grafos bi-partidos randômicas com probabilidade de uma aresta 0 <= p <= 1.
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato [[http://prolland.free.fr/works/research/dsat/dimacs.html|DIMACS]] na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).
+=== Códigos disponíveis ===
+  * Gerador de casos de teste no formato DIMACS + verificação.
+  * Para compilar: Usar C++ e Boost.
+<code c++>
+#include <iostream>
+#include <cassert>
+using namespace std;
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/max_cardinality_matching.hpp>
+using namespace boost;
+// graph element descriptors
+typedef adjacency_list_traits<vecS,vecS,undirectedS>::vertex_descriptor Node;
+typedef adjacency_list_traits<vecS,vecS,undirectedS>::edge_descriptor Edge;
+// information stored in vertices
+struct VertexInformation {
+  Node mate; // partner or graph_traits<Graph>::null_vertex()
+};
+// information stored in edges
+struct EdgeInformation {};
+// graph is an adjacency list represented by vectors
+typedef adjacency_list<vecS,vecS,undirectedS,VertexInformation,EdgeInformation> Graph;
+int main(int argc, char *argv[]) {
+  assert(argc == 3);
+  unsigned n = atoi(argv[1]);
+  double p = atof(argv[2]);
+  srand48(time(0));
+  // (1) generate random bi-partite graph
+  Graph g;
+  for(unsigned i=0; i<2*n; i++)
+    add_vertex(g);
+  for(unsigned i=0; i<n; i++)
+    for(unsigned j=n; j<2*n; j++)
+      if (drand48() < p) {
+        Edge e = add_edge(i,j,g).first;
+      }
+  // (2) get maximum matching
+  edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g));
+  unsigned card = 0;
+  graph_traits<Graph>::vertex_iterator vb, ve;
+  for ( tie(vb, ve)=vertices(g); vb != ve; vb++)
+    if (g[*vb].mate != graph_traits<Graph>::null_vertex())
+      card++;
+  //cout << "The cardinality of a maximum matching is " << card/2 << "." << endl;
+  // (3) print out in DIMACS format
+  cout << "c Bi-partite graph" << endl << endl;
+  cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl;
+  graph_traits<Graph>::edge_iterator eb, ee;
+  for ( tie(eb, ee)=edges(g); eb != ee; eb++)
+    cout << "e " << source(*eb,g)+1 << " " << target(*eb, g)+1 << endl;
+}
+</code>
+==== Trabalho 5 (O algoritmo de Cristofides) ====
+Entrega: 7/7/2017
+=== Objetivos ===
+  * Implementar o algoritmo de Cristofides
+  * Testar duas variantes: a) usando um emparelhamento perfeito máximo, b) usando um emparelhamento perfeito obtido por um algoritmo guloso que seleciona cada vez a aresta livre de maior peso.
+  * Conduzir testes que avaliam o desempenho do algoritmo em termos de qualidade e tempo.
+=== Casos de teste ===
+  * Disponíveis na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}. Aplicar pelo menos nas instâncias berlin52, vm1748, pr2392, pcb3038, fnl4461, rl5934, rl5915, usa13509, brd14051, d18512.
+  * Para avaliar a qualidade: relatar o desvio relativo percentual (v-b)/b de uma solução com valor v e melhor valor conhecido b.
+  * Informar o tempo de execução em segundos.
+=== Convenções ===
+  * A implementação deve aceitar uma instância na entrada padrão (stdin) e imprimir o valor da rota obtida pelo algoritmo de Cristofides na saída padrão (stdout).
+  * O formato das instâncias é o mesmo formato usado na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}: uma documentação está {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS|aqui}}
+=== Materiais ===
+  * Para calcular o matching, usar o software {{http://pub.ist.ac.at/~vnk/software/blossom5-v2.05.src.tar.gz|Blossom V}}.
+  * Para facilitar a leitura de instâncias da TSPLIB, {{http://www.inf.ufrgs.br/~mrpritt/aa/tspParse.H}} e {{http://www.inf.ufrgs.br/~mrpritt /aa/tspParse.C}} mostram um exemplo em C++, que pode ser adaptado.
+  * {{http://www.inf.ufrgs.br/~mrpritt/aa/blossom.patch-2|Um patch}} contra blossom5 para trabalhar com coordenadas reais (e um bugfix).

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página