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

• Dadas três instâncias do problema de distribuição de kits de informática a escolas (A:10 kits, rede lenta, técnico…
• Proponha uma decomposição em subtarefas e um esboço de pseudocódigo para automatizar um algoritmo que agenda horários de…
• Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e conflitos de…
• Você deve projetar um algoritmo para atribuir horários de aulas em uma escola. As variáveis principais são turma…
• Projete um algoritmo generalizado para escalonar tarefas de diferentes instâncias (estudo, trabalho, manutenção) que use…
• Projete um algoritmo generalizado que receba várias instâncias de planejamento de tarefas domésticas (cada instância…

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