Lista prática de revisão para a Prova 1

Explicação

A atribuição altera apenas o valor de head. Ela não executa free sobre nenhum nó. Como a única referência externa foi apagada, o programa também perde o caminho de acesso a A e, por consequência, a B.

Objetivo de aprendizagem: distinguir a mudança do valor de um ponteiro da liberação efetiva de memória.

Resposta esperada

Os dois blocos continuam alocados, mas ficam inacessíveis ao programa. Isso produz um vazamento de memória. Atribuir NULL ao ponteiro não libera os nós.

Explicação

São dois encadeamentos diferentes. Cada nó principal contém os dados de um aluno por valor e um ponteiro para o próximo nó principal. Dentro de Aluno, um ponteiro dá acesso à lista de notas. Cada nó dessa lista contém uma nota e um ponteiro para o próximo nó de notas.

Objetivo de aprendizagem: modelar uma lista de alunos com listas internas de notas, distinguindo dados armazenados por valor de ligações representadas por ponteiros.

Resposta esperada

typedef struct nodo_nota {
    int nota;
    struct nodo_nota *proximo;
} nodo_nota;

typedef struct Aluno {
    int ra;
    char nome[100];
    nodo_nota *notas;
} Aluno;

typedef struct nodo_principal {
    Aluno aluno;
    struct nodo_principal *proximo;
} nodo_principal;

aluno contém os dados do aluno dentro do nó principal. notas aponta para o primeiro nó da lista de notas desse aluno. Cada campo proximo aponta para um nó do mesmo tipo da struct que o contém. O vetor nome possui 100 posições, incluindo o espaço para o terminador '\0'.

Os nomes dos campos e o uso de typedef podem variar. A resposta deve preservar os dados, a inclusão de Aluno por valor e os tipos dos ponteiros de cada lista. As faixas de RA e nota descrevem os dados considerados no exercício e não exigem código de validação.

Explicação

Depois de free(removed), Q deixa de ser um objeto válido. Ler seu campo next nesse momento produz uso após liberação. O sucessor precisa ser recuperado e a cadeia precisa ser religada enquanto Q ainda existe.

Objetivo de aprendizagem: corrigir a ordem de uma remoção para evitar acesso após liberação.

Resposta esperada

node *removed = previous->next;
node *successor = removed->next;
previous->next = successor;
free(removed);

O acesso inválido era removed->next depois de free(removed). O trecho corrigido preserva P e R e libera somente Q.

Explicação

O último nó aponta para o primeiro. Por isso, a função compara o próximo nó de cursor com first. Em uma lista com um único nó, esse nó aponta para si e também é o último.

Objetivo de aprendizagem: implementar a condição de parada de um percurso circular, identificando o último nó pela ligação com o primeiro.

Resposta esperada

int deve_parar(const nodo *first, const nodo *cursor) {
    return cursor->proximo == first;
}

A função retorna 1 no último nó, inclusive na lista com um único nó, e 0 nos demais. A condição deve ser consultada após processar o nó atual e antes de avançar para o próximo.

Explicação

A quantidade variável não determina sozinha a estrutura. Reservar espaço para o volume máximo, guardar ligações adicionais, localizar pedidos e preservar a ordem após cancelamentos produzem custos diferentes. A decisão deve relacionar esses custos à prioridade adotada.

Objetivo de aprendizagem: justificar uma escolha de representação por requisitos de memória e operações, reconhecendo custos e condições que mudariam a decisão.

Resposta esperada

São aceitáveis as duas escolhas, desde que a justificativa seja coerente. Exemplos:

• Lista dinâmica encadeada: prioriza não reservar espaço para 20.000 pedidos quando existem poucos ativos. Após localizar um pedido e seu predecessor, sua remoção preserva a ordem sem deslocar os demais. Desvantagem: cada nó ocupa espaço adicional para a ligação, e localizar um código pode exigir percorrer toda a lista. Mudança: se o volume permanecesse próximo de 20.000, com poucos cancelamentos e muitos relatórios, um vetor poderia ser preferível.
• Lista estática: prioriza percorrer pedidos armazenados em sequência e evitar o espaço adicional de uma ligação por pedido. A capacidade de 20.000 acomoda o máximo informado. Desvantagem: reserva essa capacidade mesmo com poucos pedidos, e uma remoção que compacte o vetor preservando a ordem desloca os elementos seguintes. Mudança: se o volume passasse a ficar próximo de 20 na maior parte do tempo e a memória reservada fosse o principal limite, uma lista encadeada poderia ser preferível.

Sem uma estrutura auxiliar de busca, localizar um pedido pelo código pode exigir examinar todos os pedidos em ambas as representações. Apenas “a quantidade varia” não justifica a escolha. O cancelamento completo na lista encadeada não tem custo constante quando é necessário buscar o pedido.

Explicação

A diferença central está na ordem de acesso. Na fila, a saída respeita a chegada. Na pilha, a saída começa pela entrada mais recente. O mesmo conjunto de itens pode produzir ordens de remoção diferentes nas duas estruturas.

Objetivo de aprendizagem: explicar as políticas de fila e pilha e relacioná-las a usos práticos.

Resposta esperada

A impressão usa fila, com política FIFO, primeiro a entrar, primeiro a sair. “Desfazer” usa pilha, com política LIFO, último a entrar, primeiro a sair.

Outro uso de fila é atender requisições na ordem de chegada. Outro uso de pilha é conferir delimitadores aninhados, pois a abertura mais recente precisa ser fechada primeiro. Outros exemplos corretos com justificativa equivalente também atendem ao exercício.

Explicação

A pilha conserva as aberturas ainda pendentes. Para cada fechamento, verifique se a pilha está vazia, consulte a abertura mais recente com pega_topo e confira o par. Depois, remova a abertura com desempilha. A ausência dessa abertura, um tipo incompatível ou uma abertura restante ao final tornam a expressão inválida. Uma falha de alocação também retorna 0.

Objetivo de aprendizagem: implementar o balanceamento pela interface de uma pilha e de classificadores fornecidos, com liberação da memória.

Resposta esperada

int expressao_balanceada(char *expressao) {
    pilha_caracteres *pilha = cria_pilha();

    if (pilha == NULL) {
        return 0;
    }

    int resultado = 1;

    for (size_t indice = 0; expressao[indice] != '\0'; ++indice) {
        char simbolo = expressao[indice];

        if (eh_abertura(simbolo)) {
            if (!empilha(pilha, simbolo)) {
                resultado = 0;
                break;
            }
            continue;
        }

        if (eh_fechamento(simbolo)) {
            if (pilha_vazia(pilha)
                || !par_correspondente(pega_topo(pilha), simbolo)) {
                resultado = 0;
                break;
            }
            desempilha(pilha);
        }
    }

    if (resultado == 1 && !pilha_vazia(pilha)) {
        resultado = 0;
    }

    destroi_pilha(pilha);
    return resultado;
}

Explicação

O laço processa uma tarefa por turno. Consulte a tarefa com pega_primeira_tarefa e a retire com desenfila. O tempo executado é o menor entre o limite do turno e o trabalho restante. Esse valor aumenta o relógio e reduz o trabalho da cópia local. Se a tarefa continuar pendente, enfila recebe essa cópia atualizada.

Uma tarefa concluída gera uma única linha e não retorna à fila. Uma tarefa incompleta entra depois de todas as que já aguardavam, preservando a ordem FIFO das retiradas. Mesmo com uma única tarefa, a mesma regra funciona: ela retorna ao final até concluir. A fila vazia encerra o laço sem imprimir.

Objetivo de aprendizagem: implementar Round Robin pela interface de uma fila, reinserindo tarefas incompletas e registrando seus instantes de conclusão.

Resposta esperada

void processa_round_robin(fila_tarefas *fila, int limite_turno_ms) {
    int tempo_decorrido_ms = 0;

    // Atenda uma tarefa por turno enquanto houver trabalho pendente.
    while (!fila_esta_vazia(fila)) {
        tarefa tarefa_atual = pega_primeira_tarefa(fila);
        desenfila(fila);
        int tempo_executado_ms = limite_turno_ms;

        // Evite consumir o turno inteiro quando a tarefa termina antes.
        if (tarefa_atual.tempo_restante_ms < tempo_executado_ms) {
            tempo_executado_ms = tarefa_atual.tempo_restante_ms;
        }

        tempo_decorrido_ms += tempo_executado_ms;
        tarefa_atual.tempo_restante_ms -= tempo_executado_ms;

        // Registre a conclusão uma única vez, sem reinserir a tarefa.
        if (tarefa_atual.tempo_restante_ms == 0) {
            imprime_conclusao_tarefa(tarefa_atual.id_tarefa,
                                    tempo_decorrido_ms);
        }
        // Coloque o trabalho restante depois das tarefas que aguardam.
        else {
            enfila(fila, tarefa_atual);
        }
    }
}

Para A(5), B(2), C(4) e limite_turno_ms = 3, a saída é B 5, A 10 e C 11, uma linha por tarefa concluída. O último instante é 5 + 2 + 4 = 11 ms, igual à soma do trabalho inicial. A função termina com a fila vazia e mantém seu descritor válido.

Explicação

A regra de escolha define o que significa “melhor agora”. Manter essa escolha pode impedir um resultado final melhor, então a garantia depende de uma prova de que a decisão não impede obter uma solução ótima. Um contraexemplo refuta a garantia universal, mas não encontrar contraexemplos nos casos testados não a comprova.

Um argumento de troca é uma forma de prova: mostrar que uma solução ótima pode aceitar a escolha gulosa sem perder viabilidade nem piorar seu valor. Também é necessário justificar que resolver otimamente o restante completa uma solução ótima e que esse raciocínio vale para todas as decisões seguintes.

Objetivo de aprendizagem: distinguir evidência de testes de prova de otimalidade e explicar como uma troca segura, combinada à solução ótima do restante, justifica escolhas gulosas.

Resposta esperada

Um algoritmo guloso escolhe, a cada passo, a melhor opção viável segundo uma regra definida e mantém essa decisão, sem voltar atrás para testar outras escolhas. Isso, por si só, não garante a melhor solução final.

É necessário demonstrar que cada escolha preserva pelo menos uma solução ótima e que uma solução ótima do problema restante, combinada com essa escolha, produz um ótimo do problema original. Um argumento de troca pode justificar a primeira propriedade: substituir uma escolha de uma solução ótima pela escolha gulosa sem violar restrições nem piorar o objetivo. A prova precisa valer para qualquer entrada permitida e sustentar todas as decisões até o término. Acertar os exemplos testados não substitui essa demonstração.

Explicação

Cada unidade de peso deve receber o maior benefício ainda disponível. Se uma solução usa material de razão menor enquanto sobra material de razão maior, substituir a mesma quantidade de peso aumenta o benefício. A possibilidade de usar frações permite realizar essa troca até a capacidade ou a disponibilidade se esgotar.

B, E, G e C somam 16 unidades de peso. A unidade restante recebe F. As razões são todas diferentes, então não existe empate que permita outra distribuição ótima de quantidades.

Objetivo de aprendizagem: aplicar e justificar a escolha por benefício/peso na mochila fracionária, obtendo a distribuição ótima.

Resposta esperada

Ordene por razão decrescente: B, E, G, C, F, D, A. Use cada material até esgotar sua disponibilidade ou a capacidade restante.

• B, E, G e C: 100% de cada um.
• F: 25%, equivalente a uma unidade de peso.
• D e A: 0%.

Peso: 2 + 5 + 3 + 6 + 1 = 17. Benefício: 20 + 45 + 24 + 42 + 6 = 137.

A distribuição é ótima pelo argumento de troca entre unidades de peso. As razões estritamente diferentes tornam única a distribuição ótima das quantidades, embora a ordem de apresentar os materiais possa variar.

Explicação

Contar atividades e somar suas durações são objetivos diferentes. Um término cedo pode favorecer a quantidade de atividades, mas também pode bloquear uma atividade longa que ocuparia mais tempo.

Objetivo de aprendizagem: refutar uma regra gulosa quando o objetivo muda de quantidade de atividades para tempo total ocupado.

Resposta esperada

Um contraexemplo possível é:

A = [0, 2)
B = [2, 4)
C = [0, 9)

A regra escolhe A e B e rejeita C. Seu tempo ocupado é 4. A seleção {C} é viável e ocupa 9. Como 9 > 4, a regra não garante o objetivo proposto. Outros contraexemplos que respeitem as condições também são válidos.

Explicação

A programação dinâmica usa respostas de problemas menores para resolver o problema completo. Para encontrar a melhor solução, é preciso que as melhores respostas desses problemas menores possam ser combinadas para chegar à melhor resposta do problema completo. Essa propriedade é chamada de subestrutura ótima.

Guardar uma resposta ajuda quando o mesmo cálculo aparece novamente: basta consultar o resultado guardado. Porém, isso não diminui a quantidade de problemas menores diferentes que precisam ser resolvidos nem o trabalho necessário para resolver cada um.

No problema do troco, por exemplo, uma tabela pode ter uma posição para cada valor até o valor pedido. Um valor escrito com poucos dígitos pode exigir uma tabela com milhões de posições. Por isso, guardar resultados não garante, por si só, tempo polinomial em relação ao tamanho da entrada.

Objetivo de aprendizagem: reconhecer quando a programação dinâmica pode encontrar a melhor solução e por que evitar cálculos repetidos não garante um algoritmo eficiente.

Resposta esperada

Não. Guardar resultados evita refazer cálculos, mas não corrige uma regra que encontra a solução errada. É preciso que as respostas dos problemas menores permitam construir a melhor solução do problema completo e que o algoritmo faça isso corretamente.

Mesmo sem repetir cálculos, o algoritmo pode demorar muito se houver muitos problemas menores diferentes ou se cada um exigir muito trabalho. Portanto, guardar resultados não garante que qualquer problema seja resolvido de forma eficiente.

Explicação

No serviço A, todas as respostas precisam estar prontas, e a tabela pode ser consultada em cada atendimento. No serviço B, mesmo uma única consulta pode repetir cálculos: combinações diferentes de moedas podem deixar o mesmo valor restante.

A memoização começa pelo valor pedido e calcula as respostas conforme precisa delas. Partindo de 120 e retirando essas moedas, os valores restantes são sempre múltiplos de 6. Uma tabulação de 0 a 120 também preencheria os outros valores. Se a memoização usar um vetor com uma posição para cada valor, ela ainda reserva esse espaço, mesmo sem calcular todas as posições.

Objetivo de aprendizagem: comparar tabulação e memoização considerando quais respostas precisam ser calculadas e quando serão reutilizadas.

Resposta esperada

A: a tabulação é adequada porque todas as respostas são necessárias. A tabela é preenchida uma vez e consultada nos atendimentos seguintes.

B: a tabulação evita repetir cálculos durante a consulta, mas pode preencher posições que não serão usadas. A memoização é interessante quando só parte das respostas é necessária, como neste caso. Se quase todas forem necessárias, a tabulação pode ser mais simples e evitar chamadas recursivas. Ter apenas uma consulta não significa que nenhum cálculo será repetido.

Explicação

Para um restante de 59, a consulta é last_coin[59]. O valor guardado nessa posição indica quanto retirar do restante. Após a subtração, o novo restante indica qual posição consultar em seguida.

Objetivo de aprendizagem: usar o vetor da última moeda para recuperar um troco com a menor quantidade de moedas e conferir o resultado.

Resposta esperada

Restante 59: moeda 9, novo restante 50
Restante 50: moeda 29, novo restante 21
Restante 21: moeda 4, novo restante 17
Restante 17: moeda 17, novo restante 0

Moedas: 9, 29, 4 e 17. Soma: 59. Quantidade: 4. Apresentar essas moedas em outra ordem não muda o troco, mas as consultas ao vetor seguem a sequência mostrada.

Explicação

Ao testar uma moeda, ela é retirada do valor pedido. Se o restante puder ser formado, a quantidade necessária é a resposta já calculada para esse restante mais uma moeda. Se essa quantidade for menor que a melhor encontrada, os dois vetores são atualizados. Em um empate, a escolha anterior é mantida.

Para formar 4, duas moedas de 2 funcionam, mas uma moeda de 4 usa menos moedas. Para formar 5, usar a moeda 2 deixa 3, e usar a moeda 3 deixa 2. As duas opções usam duas moedas no total. Como a moeda 2 foi testada primeiro, ela é mantida. A moeda 4 deixa 1, que não pode ser formado.

Objetivo de aprendizagem: preencher a tabela do troco com a menor quantidade de moedas, registrando a última moeda e respeitando a regra de empate.

Resposta esperada

Posições:    0,  1, 2, 3, 4, 5
min_coins:   0,  ∞, 1, 1, 1, 2
last_coin:   0, -1, 2, 3, 4, 2

Para o valor 5, testar as moedas 2 e 3 resulta em duas moedas nos dois casos. A moeda 4 não permite completar o troco, pois deixa um restante de 1. Portanto, min_coins[5] = 2 e last_coin[5] = 2.

Explicação

A tabulação começa com F(0) e, se houver uma segunda posição, F(1). Cada valor seguinte usa as duas respostas anteriores, já guardadas no vetor.

Como o vetor pertence a quem chama a função, as respostas continuam disponíveis após seu término. A tabela pode ser montada uma vez e usada em várias consultas.

Objetivo de aprendizagem: montar uma tabela de Fibonacci em um vetor recebido, permitindo consultar os resultados sem refazer os cálculos.

Resposta esperada

void build_fibonacci_table(uint64_t table[], unsigned int table_size) {
    if (table_size > 0) table[0] = 0;
    if (table_size > 1) table[1] = 1;

    // Reuse the previous answers to fill the remaining table positions.
    for (unsigned int index = 2; index < table_size; index++) {
        table[index] = table[index - 1] + table[index - 2];
    }
}

Explicação

Os três seguem a ordem de busca em profundidade. A diferença está no motivo para abandonar uma tentativa: P não abandona nenhuma antecipadamente, Q descarta as que não podem cumprir as regras, e R também descarta as que não podem melhorar a resposta encontrada.

Objetivo de aprendizagem: distinguir a ordem em que a busca visita os estados dos motivos usados para descartar tentativas.

Resposta esperada

• P: busca em profundidade sem poda. Visita toda a árvore, sem descartar tentativas antecipadamente.
• Q: backtracking. Abandona tentativas que não podem cumprir as regras e volta para testar outras alternativas.
• R: branch-and-bound. Também usa um limite de pontuação para descartar tentativas que não podem superar a melhor solução encontrada.

Explicação

O estado descreve a situação atual do personagem. Saber em qual sala ele está permite identificar as portas disponíveis. A energia restante determina se ele pode atravessá-las. Atravessar uma porta muda essas duas informações.

Objetivo de aprendizagem: explicar estado, ação e transição usando a mudança de sala e o gasto de energia de um personagem.

Resposta esperada

Estado: a sala em que o personagem está e sua energia restante. Ação: atravessar uma porta disponível, desde que ele tenha pelo menos uma unidade de energia.

Antes de atravessar: (entrada, energia 2). Depois: (corredor, energia 1). Essa mudança é uma transição porque a ação leva o personagem de um estado a outro, alterando a sala e a energia restante.

Explicação

Cada estado descreve o tabuleiro e de quem é a vez. Uma jogada coloca o símbolo desse jogador em uma casa vazia e cria outro estado. A raiz representa o tabuleiro atual, e cada filho dela representa uma das jogadas que a IA pode fazer agora.

Ao chegar ao fim de uma partida, a busca identifica vitória, derrota ou empate do ponto de vista da IA. Esses resultados ajudam a avaliar as jogadas anteriores. Porém, é preciso considerar de quem é a vez em cada etapa: a IA escolhe o que a favorece, e o adversário pode escolher o que a prejudica.

Um tabuleiro ainda incompleto pode dar pistas, como uma ameaça de vitória, mas essas pistas não garantem que uma jogada seja a melhor. Da mesma forma, encontrar um caminho vitorioso não basta: ele pode depender de um erro do adversário. A escolha precisa considerar também as outras respostas que o adversário pode dar.

Objetivo de aprendizagem: explicar como uma busca representa as jogadas e as possíveis respostas do adversário.

Resposta esperada

1. O tabuleiro e de quem é a vez. É preciso saber quais casas estão vazias ou ocupadas por X e O e qual jogador fará a próxima jogada.
2. Colocar o símbolo do jogador da vez em uma casa vazia, desde que a partida ainda não tenha terminado. Depois, a vez passa ao outro jogador.
3. Em geral, não. O estado parcial pode mostrar ameaças e oportunidades, mas, sem analisar as próximas jogadas ou ter outra justificativa, não basta para afirmar qual jogada é a melhor. A resposta do adversário pode mudar o resultado.
4. Os resultados finais permitem avaliar a quais consequências cada jogada da raiz pode levar. A IA prefere vitória a empate e empate a derrota. Para comparar os filhos da raiz, precisa considerar as escolhas dos dois jogadores ao longo de cada ramo, identificando o melhor resultado que consegue garantir contra as respostas do adversário.
5. Não. Um caminho que termina em vitória pode depender de o adversário jogar mal. Ele pode escolher outra resposta e impedir essa vitória. Portanto, a existência desse caminho não prova que a primeira jogada dele seja a melhor.

Explicação

Um nó é folha quando não tem filhos na árvore mostrada. W e Z não têm filhos porque as tentativas já estavam completas. V não tem filhos porque a busca descartou suas próximas escolhas. Portanto, um nó pode ser folha mesmo que ainda faltassem escolhas para completar o estado.

Objetivo de aprendizagem: reconhecer as partes de uma árvore de busca e distinguir uma tentativa completa de uma tentativa interrompida por poda.

Resposta esperada

• Raiz: nó inicial, sem pai. É S.
• Nó intermediário: possui pai e filhos. É U.
• Subárvore: um nó com seus descendentes. A subárvore de U contém U, W e Z.
• Ramo: um caminho de escolhas, como S -> U -> W.
• Folha: nó sem filhos na árvore representada. Aqui, W, Z e V são folhas.

Não. W e Z representam estados completos, mas V ainda era um estado incompleto quando foi podado. Como a busca não gerou filhos para V, ele também é uma folha na árvore mostrada. Ser folha depende de não ter filhos nessa árvore, e não de representar um estado completo.

Explicação

Mesmo acrescentando os dois lotes restantes, o total chega apenas a 7 + 2 + 1 = 10. Deixar algum deles de fora só diminui esse total. Portanto, nenhuma combinação consegue atender ao pedido.

Objetivo de aprendizagem: justificar uma poda mostrando que nenhuma das escolhas restantes consegue cumprir uma exigência do problema.

Resposta esperada

Sim, pode podar. Mesmo usando tudo o que resta, o total é 10, abaixo das 12 unidades necessárias. Não é preciso testar cada combinação: se nem os dois lotes juntos completam o pedido, escolher menos lotes também não vai completar.

Explicação

Os 17 pontos correspondem apenas às escolhas já feitas. Como a tentativa ainda está incompleta, essa pontuação não basta para decidir pela poda: as próximas escolhas podem acrescentar pontos.

Para podar por pontuação, seria preciso mostrar que o ramo não pode superar os 22 pontos já encontrados. O teto de 28 pontos não permite essa conclusão, pois é maior que 22. Isso também não garante encontrar uma solução de 28 pontos, nem mesmo uma solução melhor que 22; apenas significa que esse limite não descarta a possibilidade de melhora.

Objetivo de aprendizagem: distinguir os pontos de uma tentativa incompleta, seu limite de pontuação e a melhor pontuação realmente obtida.

Resposta esperada

Continuar explorando os descendentes do estado atual. O teto de 28 pontos supera a melhor pontuação encontrada, de 22 pontos, então não há motivo para podar por esse limite. Os 17 pontos atuais não justificam a poda porque a tentativa ainda está incompleta. Continuar a busca não garante encontrar uma solução melhor, porém é cedo demais para desistir.

Explicação

Para valer a pena continuar, a tentativa precisa ter chance de superar 18 pontos. Poder cumprir as regras não basta se ela não puder melhorar a resposta. Um limite acima de 18 ainda permite essa chance, mas não garante que exista uma solução melhor.

Objetivo de aprendizagem: comparar o limite de uma tentativa com a melhor pontuação encontrada, sem confundir um limite calculado com um resultado obtido.

Resposta esperada

• A: continuar, pois o limite 21 é maior que 18. Isso não garante chegar a 21 nem encontrar uma solução melhor.
• B: podar, pois a tentativa não pode passar de 17, abaixo dos 18 já encontrados.
• C: podar, pois a tentativa pode, no máximo, empatar com 18. Não é necessário listar os empates.

Explicação

No primeiro problema, encontrar uma escala válida já é suficiente. No segundo, uma escolha de serviços pode caber no orçamento e ainda ter menos pontos que outra. O limite de pontuação permite descartar tentativas que não podem melhorar a resposta, mesmo que possam cumprir o orçamento.

Objetivo de aprendizagem: escolher a técnica considerando se basta encontrar uma solução válida ou se é preciso encontrar a melhor, e quais ramos podem ser descartados.

Resposta esperada

1. Backtracking: pode podar uma tentativa que já colocou a mesma pessoa em dois turnos no mesmo horário. Acrescentar outros turnos não corrige esse conflito. A busca pode parar quando encontrar a primeira escala completa válida ou quando verificar que nenhuma é possível.
2. Branch-and-bound: pode podar uma tentativa que já passou do orçamento, pois acrescentar serviços não reduz o custo. Também pode podar quando o limite de pontuação não supera a melhor solução completa já encontrada. A busca termina quando todos os ramos que poderiam melhorar a resposta tiverem sido explorados ou descartados com uma justificativa válida.

Testar todas as combinações válidas também permitiria encontrar a maior pontuação no segundo problema. O branch-and-bound usa o limite fornecido para evitar explorar tentativas que não podem melhorar a resposta.