Aula Prática #10 - Árvores de Suporte de Custo Mínimo
(aulas de 18/05 e 22/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: 1 de Junho (submeter no Mooshak de DAA) [último dia antes da época de exames]
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ítulo "9 - Grafos: Árvores de Suporte de Custo Mínimo")
- Vídeos: (vídeo #22)
Exercício 1) Uma primeira implementação de árvores de suporte de custo mínimo
Implemente e submeta uma solução para o problema [DAA 037] Sardas.
Dicas:
- Neste problema temos de encontrar a árvore de suporte de custo mínimo que liga as sardas.
- Para saber a distâcia da sarda \((x_1, y_1)\) a \((x_2, y_2)\), basta usar \(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)
- Tanto pode usar o algoritmo de Prim, como o algoritmo de Kruskal. Uma sugestão é implementar ambos e verificar que dão a mesma resposta.
- Tendo em conta os limites, não é necessário usar estruturas de dados especializadas, e "qualquer" implementação pasa (mesmo que seja quadrática no tempo e no espaço) passa.
- Use doubles para os seus cálculos para não perder precisão (e imprima pelo menos com 3 casas decimais).
Exercício 2) Completando uma árvore de suporte de forma eficiente
Implemente e submeta uma solução para o problema [DAA 038] Fibra ótica.
Dicas:
- Neste problema tem de completar uma árvore de suporte de custo mínimo que já foi começada. É possível adaptar quer o algoritmo de Prim, quer o algoritmo Kruskal adaptando para que comece já com um conjunto de nós existente. Consegue perceber como?
- Antes de imprimir tem de ordenar as arestas que adicionou (pode usar a API da sua linguagem)
- Para ter accepted necessita de uma implementação melhor que \(\mathcal{O}(|V|^2)\). A sugestão é usar Prim com filas de prioridade/sets (como foi feito com o Dijkstra na aula #10) ou Kruskall com disjoint-sets como implementação de union-find como explidada nas teóricas, o que lhe dá em ambos os casos uma complexidade final de \(\mathcal{O}(|E| \log |V|)\).
- Se usar Java, use Input/Output rápido (é possível passar só com Scanner, mas podem existir 40 mil linhas de input)
Exercício extra) Implementando disjoint-sets (union-find)
Se quiser ter a certeza que implementa corretamente disjoint-sets aqui fica um pequeno problema extra que pede diretamente as operações fornecidas por uma estrutura de dados de union-find.
Implemente e submeta uma solução para o problema [DAA 039] Bolhas pandémicas.
Dicas:
- Implemente directamente o pseudo-código dado nos slides para union find, usando path compression e union-by-rank (se usar só uma destas heurísticas também passará no tempo, mas se não usar nenhuma deverá exceder o tempo limite).
- Se usar Java, use Input/Output rápido (podem existir 100 mil linhas de input)
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 vem do CodeChef e tem natura algorítmica, como seria de esperar! Está disponível para submissão no Mooshak:
Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas, sabendo que este problema é mais complicado que os outros desta aula.