Estudo

23 Fevereiro 2017, 18:30 • Luis Eduardo Neves Gouveia

Adaptação das heurísticas estudadas para problemas com vários circuitos (e..g, com vários depósitos e problema da p-mediana hamiltoniana)

Conceito de Heurística. Introdução e motivação e Heurísticas para o Problema do Caixeiro Viajante (inicio))

23 Fevereiro 2017, 16:30 • Luis Eduardo Neves Gouveia

1.        Conceito de Heurística. Introdução e motivação

       Análise: i) garantias de qualidade; ii) análise probabilística; iii) análise empírica.

      

3.    Heurísticas para o Problema do Caixeiro Viajante (como exemplo de vários temas):

       3.1  Instâncias com desigualdade triangular

              3.2  Heurística do Vizinho Mais Próximo. Análise com garantias de qualidade

       3.3 Heurística da Árvore de Suporte Duplicada. Análise com garantias de qualidade

       3.4  Heurística de Christofides. Análise com garantias de qualidade.

       3.5  Heurísticas de Inserção. Análise com garantias de qualidade.

       3.6 Análise Empírica.

Noções sobre complexidade algorítmica.

16 Fevereiro 2017, 18:30 • Francisco Saldanha da Gama

Um problema NP-difícil. Demonstração. Uma heurística específica para um problema de sequenciamento: a heurística de Schrage.

Noções sobre complexidade algorítmica.

16 Fevereiro 2017, 16:30 • Francisco Saldanha da Gama

Apresentação da disciplina.

Complexidade algorítmica: breve introdução. Problemas de decisão associados a um problema de otimização. Redução de problemas, transformação polinomial. Classes P, NP, NP-completo, NP-difícil. Um problema polinomial. Demonstração.