Aula Prática #09 - Pesquisa em Largura (+ordenação topológica)
(semana de 16/05 a 20/05)
Exercícios para submissão
Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:
Prazo de submissão: 5 de Junho (submeter no Mooshak de DAA)
Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relebre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de Pesquisa em Grafos. Será por isso conveniente ver o que foi falado nas teóricas:
- Slides (capítulos "7 - Grafos: Pesquisa")
- Vídeos: (vídeos #18 e #19)
Exercício 1) Ordenação topológica (aplicação de DFS)
Este exercício é uma continuação das aplicações de DFS iniciadas na aula anterior. Deve começar por fazer os exercícios base da aula #08 antes de fazer este (incluindo ter usado o código exemplo aí dado).
Implemente e submeta uma solução para o problema [DAA 029] Ordem rara.
Dicas:
- Que informação dão as strings do input sobre a ordem das letras?
- Procure representar a informação através de um grafo dirigido onde existe uma aresta de a para b se a deve aparecer antes de b na ordem desejada.
- Essencialmente, para um par de palavras consecutivo no input deve existir uma aresta entre as duas primeiras letras que são diferentes.
(não é necessário considerar pares de palavras não consecutivas no grafo, devido à transitividade da relação de ordem)
- Considere o exemplo de input dado no enunciado:
- Como ZX vem logo a seguir a XWY, temos uma aresta X→Z.
- Como ZXW vem logo a seguir a ZXY, temos uma aresta Y→W.
- Como YWWX vem a seguir a ZXW, temos uma aresta Z→Y.
O grafo geral neste caso seria X→Z→Y→W
- Depois de ter o grafo construido, calcular o desejado é fazer uma ordenação topológica! Notem que nem sempre o grafo fica uma simples cadeia como no input exemplo, mas é garantido que existe uma e só uma ordenação topológica possível. Para conhecer um algoritmo para fazer uma ordenação topológica pode espreitar as aulas teóricas [ver slides 16 a 19].
Exercício 2) Introdução à pesquisa em largura (BFS)
Comece por fazer download do código exemplo de pesquisa em largura:
- Java: BFS.java (versão original feita em Java)
- C++: bfs.cpp (adaptação para C++)
- C: bfs_c.cpp (adaptação para C/C++ "quase como em C, sem usar classes)
Se costuma usar C, a sugestão é que use a última versão, que é essencialmente C com excepção das listas, que já estão implementadas em C++ usando STL. A ideia é que progressivamente possa ir começando a usar as estruturas de dados úteis que o C++ tem e o C não, continuando no essencial a programar em C "normal" e usando C++ apenas para essas estruturas de dados.
- Compile e execute o código usando como input o ficheiro graph.txt, que corresponde ao grafo da figura seguinte:
- Procure compreender todos as linhas do código dado. Experimente mudá-lo começar a pesquisa em largura a partir de outros nós que não o 1. Antes de executar consegue prever o output?
Exercício 3) Um problema com pesquisa em largura
Usando como base o código dado no exercício anterior, implemente e submeta uma solução para o problema [DAA 030] Análise de uma rede biológica.
Dicas:
- Neste problema temos de encontrar as distâncias entre todos os pares de nós, para poder usar as definições dadas. Procure construir uma matriz como a dadada no enunciado.
- Para saber a distância de um nó v a todos os outros nós (uma linha da matriz), faz-se uma pesquisa em largura a partir do nó v [ver slides 42 a 46].
- No total vamos fazer N pesquisas em largura (uma para cada nó)
Exercício extra) Pesquisa em largura a partir de vários nós
Este exercício é um extra, e não é considerado essencial no contexto desta aula. Use-o se quiser consolidar os seus conhecimentos.
Implemente e submeta uma solução para o problema [DAA 031] Nuvem de cinzas.
Dicas:
- Este problema foi explicado nas aulas teóricas [ver slides 47 a 50].
- A ideia principal é fazer uma pesquisa em largura onde inicialmente todas as posições com cinza já estão na fila (e com distância zero).
Exercício de Desafio
Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.
Para esta semana o desafio tem mais a ver com ter código bem estruturado (não sendo especialmente complicado do ponto de vista da eficiência temporal). É um exemplo de uma aplicação de BFS a jogos, semalhante ao que é abordado noutras UCs, como por exemplo em Inteligência Artificial. O problema está disponível para submissão no Mooshak:
Essencialmente o problema já foi abordado nas téoricas e até os slides explicam como fazer :)