Compare três instâncias do problema de alocação de salas: instância A (30 turmas, horários fixos), B (45…

Questão

Compare três instâncias do problema de alocação de salas: instância A (30 turmas, horários fixos), B (45 turmas, horários flexíveis) e C (20 turmas, restrições de equipamento). Identifique semelhanças e diferenças relevantes e proponha um algoritmo generalizado que trate todas as instâncias usando variáveis parâmetro; descreva como aplicar decomposição, generalização e reúso. Forneça assinatura e pseudocódigo explicando o papel das variáveis parâmetro.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Comparação: semelhanças — todas exigem mapear turmas a salas respeitando conflitos de horário; diferenças — número de turmas, flexibilidade de horários e restrições por equipamento influenciam complexidade e heurísticas. Assinatura proposta: alocar_salas(turmas, salas, restricoes, estrategia_heu). Decomposição: 1) validar entradas; 2) préprocessar compatibilidades (por turma ? salas conforme equipamento e capacidade); 3) gerar ordens de atribuição (por heurística: maior grau, mais restrições); 4) atribuir iterativamente (backtracking/greedy) aplicando estratégia_heu; 5) refinamento (swap/ajuste). Generalização: representar restricoes como estruturas parametrizáveis (funções teste_compatibilidade(turma,sala) e janela_horarios(turma)); passar estrategia_heu como parâmetro para escolher abordagem (greedy, local search, CP). Reúso: précomputar matriz compatibilidade turma×sala e reutilizá-la entre instâncias similares; armazenar soluções parciais e heurísticas calibradas. Pseudocódigo (resumido): alocar_salas(turmas,salas,restricoes,estrat): compat?precomputar_compat(turmas,salas,restricoes); ordem?estrat.ordenar(turmas,compat); solução?vazio; para t em ordem: candidatos?filtrar(salas, compat[t]); atribuir melhor candidato segundo estrat; se falha then backtrack/ajustar; retornar solução. Variáveis parâmetro: turmas, salas, restricoes, estrategia_heu controlam instâncias; compat e solução são estruturas internas reutilizáveis entre chamadas quando aplicável.

Explicação

A análise das semelhanças e diferenças entre as instâncias permite entender como as variáveis de entrada influenciam a complexidade do problema de alocação de salas. A proposta de um algoritmo generalizado com variáveis parâmetro facilita a adaptação do método a diferentes cenários, promovendo eficiência e flexibilidade. A decomposição, generalização e reúso de componentes garantem que soluções e estruturas possam ser reaproveitadas, otimizando o processo de alocação.

Raio-X da questão

Questões parecidas com resolução

• — Se o corredor entre as salas 4 e 5 estiver fechado, o visitante não pode receber um caminho antigo — explicou a…
• Uma estudante criou um programa para contar pontos em um jogo. Depois, percebeu que a mesma estrutura podia servir para…
• Projete a assinatura de um algoritmo que resolve várias instâncias de caminho mínimo: recebe um grafo e uma lista de…
• Projete a assinatura de um algoritmo generalizado chamado normalizar que aplica min–max scaling a um conjunto de…
• No pseudocódigo de uma função que processa dados, qual termo descreve as condições que devem ser verdadeiras antes da…
• Projete um algoritmo em pseudocódigo que receba como dado de entrada uma string binária s (composta por '0' e '1') e uma…

Todas as questões de Estratégias de solução de problemas - Generalização