Aula prática 07: decisões, caminhos e podas

Explicação

Os dois caminhos terminam no mesmo lugar, mas produzem possibilidades diferentes. A posição e a posse da pulseira precisam fazer parte do estado para decidir se a porta pode ser usada. Se a busca tratar os dois estados como iguais, pode descartar o caminho com pulseira e perder a solução. O percurso pode ser guardado separadamente se o jogo precisar exibir a rota.

Objetivo de aprendizagem: reconhecer que um estado precisa conter todas as informações que alteram as próximas escolhas, mesmo quando dois caminhos chegam ao mesmo lugar.

Resposta esperada

Regra fixa: a porta dos Bastidores só abre com pulseira. Registrar apenas “posição = Corredor” confundiria dois estados com próximas escolhas diferentes.

Explicação

A raiz ainda não contém escolhas. Cada sala produz um estado parcial; escolher um objeto completa uma tentativa. A subárvore de Estúdio inclui esse nó e suas duas continuações. As quatro folhas mostram o resultado de cada plano, permitindo verificar quais caminhos atingem o objetivo.

Objetivo de aprendizagem: interpretar nós como estados, ligações como decisões e folhas como tentativas completas que podem ter resultados diferentes.

Resposta esperada

flowchart TD
    root["Nenhuma escolha: raiz"] -->|Estúdio| studio["Estúdio"]
    root -->|Oficina| workshop["Oficina"]
    studio -->|Lanterna UV| studio_light["Estúdio + Lanterna UV: código"]
    studio -->|Chave| studio_key["Estúdio + Chave: falha"]
    workshop -->|Lanterna UV| workshop_light["Oficina + Lanterna UV: falha"]
    workshop -->|Chave| workshop_key["Oficina + Chave: código"]

A subárvore de Estúdio contém Estúdio, Estúdio + Lanterna UV e Estúdio + Chave. As quatro folhas são planos completos: dois encontram o código e dois falham. Uma busca por qualquer código pode parar ao encontrar a primeira folha bem-sucedida.

Explicação

A ainda tem uma vaga. Sua pontuação atual não é solução, mas também não prova que o ramo inteiro falhará, então a busca testa a próxima carta. B já soma 7 de ataque e 5 de defesa. C soma 9 de ataque, mas só 3 de defesa; como não restam vagas, nenhuma continuação pode corrigir a falta de defesa.

Objetivo de aprendizagem: distinguir um estado parcial ainda aberto, uma solução completa e um estado completo sem solução, sem resolver antecipadamente os descendentes.

Resposta esperada

Continuar o ramo A não garante que ele contenha uma solução; apenas evita descartá-lo sem justificativa. Os estados B e C encerram caminhos da árvore, mas só B é uma solução.

Explicação

A busca esgota a subárvore da Galeria antes de tentar a Oficina. Ao voltar de um caminho sem saída, restaura o caminho anterior; não mantém o Corredor ou o Arquivo como parte da nova tentativa.

Objetivo de aprendizagem: rastrear a busca em profundidade e perceber que desfazer uma escolha restaura o caminho ativo antes da próxima tentativa.

Resposta esperada

A rota guardada é Entrada → Oficina → Saída. Como o objetivo é encontrar uma rota, a busca pode parar nesse ponto.

Explicação

O consumo atual é 7, acima do limite 6. Como as próximas escolhas não diminuem o consumo, toda continuação conserva a violação. A única forma de testar outra combinação é desfazer uma escolha já feita.

Objetivo de aprendizagem: justificar uma poda por inviabilidade com uma restrição que nenhuma escolha futura consegue reparar.

Resposta esperada

Pode podar por inviabilidade: 4 + 3 = 7 > 6, e nenhuma continuação reduz esse total. Para testar outro ramo, a busca desfaz a última escolha e retorna ao estado anterior. Podar descarta continuações do estado inviável; desfazer restaura o estado de trabalho.

Explicação

Restam 7 − 2 = 5 unidades de peso. O Scanner fornece 6/3 = 2 pontos por unidade; a Câmera fornece 4/4 = 1. Por ter maior densidade, o Scanner entra primeiro: trocar espaço dele por espaço da Câmera não aumentaria o valor fracionário. Assim, o melhor preenchimento fracionário usa o Scanner inteiro e 2/4 da Câmera. Toda seleção 0-1 também é permitida nesse modelo ampliado, então seu ótimo não pode ficar abaixo do melhor valor real do ramo.

Objetivo de aprendizagem: calcular um teto seguro para um estado parcial pela relaxação fracionária, sem confundir a fração usada na prova com uma escolha válida da mochila.

Resposta esperada

O limite superior é 13 pontos: 5 já obtidos com Gancho, mais 6 com Scanner inteiro e $(2/4)\times4=2$ com metade da Câmera. O Scanner ocupa 3 das 5 unidades livres; as 2 restantes só entram no teto como fração da Câmera. Nenhuma continuação 0-1 pode superar o ótimo fracionário, mas 13 não é uma seleção válida, pois a Câmera real não pode ser dividida.

Explicação

Em maximização, um ramo só pode melhorar o incumbente se seu teto ultrapassar 10. O ramo A ainda permite uma melhora segundo o limite, mesmo que seu valor atual seja 5. Os ramos B e C podem conter seleções válidas, mas seus tetos já impedem uma pontuação maior que 10.

Objetivo de aprendizagem: comparar o limite superior de cada ramo com o incumbente para decidir uma poda sem perder uma melhora possível.

Resposta esperada

O teto 13 do ramo A não prova que exista uma seleção 0-1 de valor 13. Se o objetivo fosse listar todas as seleções ótimas, um ramo que só permite empatar, como C, precisaria continuar elegível.

Explicação

Encontrar uma rota resolve a busca por existência. A mesma descoberta não informa se há outras rotas ou se a pontuação é máxima. Para listar todas as rotas válidas, um teto de pontuação não autoriza a poda: mesmo rotas com menos de 10 pontos precisam ser encontradas. Nesse objetivo, a busca deve explorar todos os ramos que ainda possam conter rotas válidas. O ramo pendente também pode superar 10 pontos, portanto a melhor pontuação ainda não foi provada.

Objetivo de aprendizagem: relacionar o critério de parada ao objetivo da busca: encontrar uma solução, listar todas ou provar a melhor.

Resposta esperada

1. Pode parar: a rota encontrada já é válida.
2. Não pode parar: é preciso explorar todos os ramos que ainda possam conter rotas válidas. O teto 13 não muda essa decisão, pois a pontuação não importa para listar todas. Não se pode podar um ramo por seu teto, mas um ramo comprovadamente inviável pode ser descartado.
3. Não pode parar: o teto 13 ainda permite uma rota melhor que 10. A prova de otimalidade exige explorar ou podar com segurança todos os ramos restantes.

Explicação

Cada decisão duplica os estados do nível anterior, pois nenhuma escolha elimina opções posteriores. As histórias completas ficam no último nível, mas a equipe também precisa considerar os estados parciais que levam até elas.

Objetivo de aprendizagem: contar tanto os estados parciais quanto as folhas para medir o tamanho da árvore potencial.

Resposta esperada

Há 1 estado na raiz, depois 2, 4 e 8 estados. O total é 1 + 2 + 4 + 8 = 15 estados, dos quais 8 são histórias completas.

Explicação

Com uma decisão binária adicional, o número de histórias completas sem poda dobra. Um limite seguro pode ser pouco informativo e não permitir nenhuma poda. Nesse caso, a equipe ainda visita a árvore inteira e calcula o limite nos estados encontrados.

Objetivo de aprendizagem: reconhecer o pior caso exponencial e considerar o trabalho por estado ao estimar o tempo da busca.

Resposta esperada

A promessa é falsa. No pior caso, nenhum limite permite podar: há $2^n$ histórias completas e $2^{n+1}-1$ estados no total. Como calcular o limite de cada estado pode percorrer até $n$ decisões, um limite conservador para o tempo é $O(n2^n)$. A poda reduz o trabalho nas versões em que descarta ramos, sem garantir esse ganho em todas elas.

Explicação

As duas versões têm a mesma pilha e o mesmo vetor de trabalho. A diferença está no que permanece salvo depois de visitar uma folha: a versão A substitui uma cópia, enquanto a B acumula todas. Percorrer em profundidade não impede o crescimento da memória usada para armazenar resultados.

Objetivo de aprendizagem: distinguir a memória do caminho ativo da memória usada para guardar resultados e reconhecer quando armazenar todas as soluções torna o espaço exponencial.

Resposta esperada

Com três decisões, coexistem no máximo quatro níveis de chamada, contando a chamada inicial. Para $n$ decisões, há $2^n$ histórias completas. A pilha e o vetor de trabalho ocupam $O(n)$ memória em ambas as versões.

• Versão A: guarda uma cópia de $n$ escolhas por vez. A memória total é $O(n)$.
• Versão B: guarda $2^n$ cópias de $n$ escolhas. A coleção ocupa $\Theta(n2^n)$ memória, que domina a pilha e o vetor de trabalho.

Assim, a busca em profundidade economiza memória no percurso, mas não reduz o espaço necessário quando o próprio objetivo é manter todas as histórias completas.

Explicação

Como os deslocamentos não reduzem o consumo, uma rota que ultrapassa a energia disponível não pode voltar a ser válida enquanto as escolhas anteriores permanecerem fixas. Para maximizar pontuação, um limite superior seguro pode descartar até uma combinação parcial válida quando nenhuma continuação supera a melhor resposta completa conhecida.

Objetivo de aprendizagem: escolher a técnica de busca pelo resultado exigido e pela justificativa de poda disponível, considerando também tempo e memória.

Resposta esperada

Enumerar todas as combinações válidas e comparar pontuações também encontra o ótimo, mas a segunda missão permite usar a poda por limite para evitar ramos desnecessários.

Nas duas missões, as podas podem reduzir o tempo em certas entradas, sem eliminar o pior caso de muitos estados. Sob a implementação em profundidade descrita, a pilha, o caminho ativo e a cópia de uma resposta ocupam $O(n)$ memória auxiliar para $n$ decisões, sem guardar toda a árvore. Calcular limites acrescenta trabalho por estado na segunda missão.

Explicação

Sem incumbente, ainda não há valor com o qual comparar os tetos. A primeira tentativa segue Turbo, Pneus e Nitro. Incluir os três excede a capacidade; rejeitar Nitro produz a primeira configuração completa e válida, com 13 pontos. Só então esse valor se torna o incumbente. O teto é seguro porque soma todos os pontos ainda disponíveis sem impor a restrição de espaço; assim, não subestima nenhuma continuação real.

Na árvore abaixo, P é o espaço usado, V é a pontuação atual e U é o teto. Os números nas ligações indicam a ordem da busca. O incumbente B nasce no passo 4 e permanece em 13 nos passos seguintes.

flowchart TD
    root["P=0, V=0, U=19. B=nenhum"]
    with_turbo["P=3, V=8, U=19"]
    without_turbo["P=0, V=0, U=11. Poda"]
    with_tires["P=5, V=13, U=19"]
    without_tires["P=3, V=8, U=14"]
    invalid_three["P=9, V=19, U=19. Inviável"]
    first_solution["P=5, V=13, U=13. B=13"]
    invalid_nitro["P=7, V=14, U=14. Inviável"]
    turbo_only["P=3, V=8, U=8. Completa"]

    root -->|1 Incluir Turbo| with_turbo
    with_turbo -->|2 Incluir Pneus| with_tires
    with_tires -->|3 Incluir Nitro| invalid_three
    with_tires -->|4 Rejeitar Nitro| first_solution
    with_turbo -->|5 Rejeitar Pneus| without_tires
    without_tires -->|6 Incluir Nitro| invalid_nitro
    without_tires -->|7 Rejeitar Nitro| turbo_only
    root -->|8 Rejeitar Turbo| without_turbo

Objetivo de aprendizagem: rastrear a criação do incumbente e combinar ramificação, limite superior e inviabilidade para provar que uma configuração válida é ótima.

Resposta esperada

1. Antes da primeira solução: não existe incumbente. A raiz tem teto 19, e os ramos com Turbo e com Turbo + Pneus também têm teto 19; a busca continua por eles. Incluir Turbo e Pneus leva a espaço 5 e valor 13. Tentar incluir Nitro excede a capacidade, pois 3 + 2 + 4 = 9 > 5. Ao rejeitar Nitro, a configuração completa Turbo + Pneus é válida e passa a ser o primeiro incumbente, de 13 pontos.
2. Com Turbo e sem Pneus: o teto 8 + 6 = 14 supera o incumbente 13, então o ramo precisa continuar. Incluir Nitro excede a capacidade, pois 3 + 4 = 7 > 5. Rejeitar Nitro encerra com 8 pontos e não altera o incumbente.
3. Sem Turbo: o teto otimista 5 + 6 = 11 não supera o incumbente 13, então o ramo pode ser podado por limite, mesmo que Pneus e Nitro não caibam juntos.

Nenhum ramo restante pode superar 13 pontos. Portanto, Turbo + Pneus é uma configuração ótima. O incumbente foi encontrado durante a busca, antes da poda por limite.