DO 01 AO 80-58

Prévia do material em texto

Material de Estudo - Otimização Combinatória: Algoritmos de Aproximação e Heurísticas 
(Material 58) 
1. Em um projeto de otimização de rotas de entrega, qual dos seguintes algoritmos de 
aproximação é mais adequado para encontrar soluções aproximadas para o problema 
do caixeiro viajante (TSP)? 
a) Algoritmo de Dijkstra. b) Algoritmo de Kruskal. c) Algoritmo de Prim. d) Algoritmo 2-
aproximação para TSP métrico. e) Algoritmo de Ford-Fulkerson. 
Resposta: d) Algoritmo 2-aproximação para TSP métrico. 
Justificativa: O algoritmo 2-aproximação para TSP métrico garante que a solução encontrada 
seja no máximo duas vezes pior do que a solução ótima, oferecendo um bom compromisso 
entre qualidade da solução e tempo de execução. 
2. Em um projeto de design de redes de telecomunicações, qual das seguintes heurísticas 
é mais adequada para encontrar soluções aproximadas para o problema da árvore 
geradora mínima com restrições de grau (CMST)? 
a) Algoritmo guloso. b) Algoritmo genético. c) Algoritmo simulated annealing. d) Heurística de 
Esau-Williams. e) Algoritmo de busca tabu. 
Resposta: d) Heurística de Esau-Williams. 
Justificativa: A heurística de Esau-Williams é uma heurística construtiva específica para o CMST, 
que busca encontrar soluções de alta qualidade em tempo razoável. 
3. Em um projeto de alocação de recursos em nuvem, qual dos seguintes algoritmos de 
aproximação é mais adequado para encontrar soluções aproximadas para o problema 
de empacotamento de bins (Bin Packing)? 
a) Algoritmo first-fit decreasing (FFD). b) Algoritmo de Dijkstra. c) Algoritmo de Kruskal. d) 
Algoritmo de Prim. e) Algoritmo de Ford-Fulkerson. 
Resposta: a) Algoritmo first-fit decreasing (FFD). 
Justificativa: O algoritmo FFD é um algoritmo de aproximação simples e eficiente para o Bin 
Packing, que garante que a solução encontrada não seja pior do que 11/9 da solução ótima. 
4. Em um projeto de agendamento de tarefas em processadores paralelos, qual das 
seguintes heurísticas é mais adequada para encontrar soluções aproximadas para o 
problema de agendamento de máquinas paralelas (Parallel Machine Scheduling)? 
a) Algoritmo guloso. b) Algoritmo genético. c) Algoritmo simulated annealing. d) Heurística de 
lista. e) Algoritmo de busca tabu. 
Resposta: d) Heurística de lista. 
Justificativa: A heurística de lista é uma heurística simples e eficiente para o Parallel Machine 
Scheduling, que atribui tarefas aos processadores na ordem de uma lista predefinida. 
5. Em um projeto de design de layout de circuitos integrados, qual dos seguintes 
algoritmos de aproximação é mais adequado para encontrar soluções aproximadas 
para o problema de particionamento de grafos (Graph Partitioning)? 
a) Algoritmo de Kernighan-Lin. b) Algoritmo de Dijkstra. c) Algoritmo de Kruskal. d) Algoritmo 
de Prim. e) Algoritmo de Ford-Fulkerson. 
Resposta: a) Algoritmo de Kernighan-Lin. 
Justificativa: O algoritmo de Kernighan-Lin é um algoritmo de aproximação iterativo para o 
Graph Partitioning, que busca melhorar uma solução inicial através de trocas de nós entre as 
partições. 
6. Em um projeto de roteamento de veículos com janelas de tempo (VRPTW), qual das 
seguintes heurísticas é mais adequada para encontrar soluções aproximadas para o 
problema? 
a) Algoritmo guloso. b) Algoritmo genético. c) Algoritmo simulated annealing. d) Heurística de 
inserção. e) Algoritmo de busca tabu. 
Resposta: d) Heurística de inserção. 
Justificativa: As heurísticas de inserção são heurísticas construtivas que gradualmente 
constroem rotas de veículos, inserindo clientes em rotas existentes ou criando novas rotas. Elas 
são amplamente utilizadas para o VRPTW devido à sua eficiência e capacidade de lidar com 
restrições de janelas de tempo.