Search This Blog

Saturday, April 13, 2019

Aula 9 de Métodos Computacionais em Economia (2019) - Força Bruta III - Busca Exaustiva em Grafos

Na nossa nona aula de métodos computacionais discutimos os algoritmos BFS e DFS que promovem busca exaustiva em grafos e várias de suas aplicações. Esses são os slides usados em sala.


Abaixo temos os exemplos apresentados em sala de aula:

Análise empírica de redes

Como implementar o algoritmo de busca exaustiva em grafos conhecido como breadth first search - BFS (busca em largura)?

Como implementar o algoritmo de busca exaustiva em grafos conhecido como depth first search - DFS (Busca em profundidade)?

Referências Adicionais para essa aula:

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Seção 3.5]

Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Capítulo 22]

Referências complementares para essa aula:

Networks: An Introduction - Mark Newman

Soluções de exercícios:

Como implementar BFS e DFS em Python e extrair informações úteis de um grafo, como conectividade, aciclicidade, etc?

Problema das jarras