📄 Ver slides (PDF)
⚡ Ação: O que é a fronteira numa árvore de procura?
👉 É o conjunto de estados gerados mas ainda não expandidos.
⚡ Ação: O que significa expandir um estado?
👉 Aplicar todas as ações possíveis ao estado atual para gerar os seus sucessores.
⚡ Ação: O que distingue a procura em árvore da procura em grafo?
👉 A procura em grafo testa se um estado já foi gerado antes de o adicionar à fronteira, evitando repetições.
⚡ Ação: Porque é que caminhos redundantes podem ser removidos?
👉 Porque não pioram a solução e reduzem o espaço de procura.
⚡ Ação: Como se evita gerar estados iguais ao pai ou avô?
👉 Verificando se o sucessor coincide com um ascendente e removendo-o.
⚡ Ação: Qual é a vantagem de usar uma hash table na procura em grafo?
👉 Permite testar rapidamente se um estado já foi gerado.
⚡ Ação: O que acontece se a hash table “esquecer” estados antigos?
👉 Alguns estados podem ser revisitados, aumentando o tempo, mas sem alterar o resultado final.
⚡ Ação: Que problema surge em espaços de estados com ações reversíveis?
👉 A existência de muitos ciclos e caminhos redundantes.
⚡ Ação: Como se evita ciclos de tamanho 2?
👉 Impedindo movimentos que retornem imediatamente ao estado anterior.
⚡ Ação: Porque é que verificar todos os ascendentes evita ciclos no mesmo ramo?
👉 Porque garante que nenhum estado já visitado nesse caminho é repetido.
⚡ Ação: O que significa um algoritmo ser completo?
👉 Significa que encontra uma solução sempre que ela existir.
⚡ Ação: O que significa um algoritmo ser ótimo?
👉 Que retorna sempre a solução de menor custo.
⚡ Ação: Como se mede a complexidade temporal?
👉 Em número de nós gerados.
⚡ Ação: Como se mede a complexidade espacial?
👉 Em número de estados mantidos em memória.
⚡ Ação: O que representa o parâmetro b?
👉 A ramificação máxima, ou seja, o número máximo de sucessores de um nó.
⚡ Ação: O que representa o parâmetro d?
👉 A profundidade da solução mais próxima.
⚡ Ação: O que representa o parâmetro m?
👉 A profundidade máxima da árvore de procura.
⚡ Ação: Porque é que medir tempo em segundos não é adequado?
👉 Porque depende do computador e da linguagem usada; o número de nós gerados é independente dessas variáveis.
⚡ Ação: Porque é que a profundidade máxima pode ser infinita?
👉 Porque ações reversíveis podem gerar caminhos arbitrariamente longos.
⚡ Ação: Porque é útil estimar b, d e m?
👉 Para prever a ordem de grandeza da complexidade dos algoritmos.
⚡ Ação: O que caracteriza a procura em largura?
👉 Expande primeiro os estados gerados há mais tempo, nível a nível.
⚡ Ação: Que estrutura de dados usa a procura em largura?
👉 Uma fila FIFO.
⚡ Ação: Quando é feito o teste de objetivo na procura em largura?
👉 Normalmente no momento da geração.
⚡ Ação: Porque é que a procura em largura é completa?
👉 Porque explora todos os estados por ordem crescente de profundidade.
⚡ Ação: Em que condições a procura em largura é ótima?
👉 Quando todas as ações têm o mesmo custo.
⚡ Ação: Qual é a complexidade espacial da procura em largura?
👉 O(b^d), que é normalmente proibitiva.
⚡ Ação: O que acontece se limitarmos o tamanho da fronteira?
👉 O algoritmo deixa de ser completo.
⚡ Ação: O que distingue o custo uniforme da largura?
👉 O custo uniforme expande o estado com menor custo acumulado.
⚡ Ação: Porque é que o custo uniforme garante otimalidade?
👉 Porque expande sempre o estado mais barato na fronteira.
⚡ Ação: Porque é que o custo uniforme sofre dos mesmos problemas de memória que a largura?
👉 Porque mantém todos os estados gerados na fronteira.
⚡ Ação: O que caracteriza a procura em profundidade?
👉 Expande o estado gerado mais recentemente, o mais profundo na fronteira.
⚡ Ação: Que estrutura de dados usa a profundidade?
👉 Uma pilha LIFO.
⚡ Ação: Porque é que a profundidade pode não ser completa?
👉 Porque pode ficar presa em ramos infinitos ou ciclos.
⚡ Ação: Qual é a grande vantagem da profundidade?
👉 A complexidade espacial baixa, apenas O(b·m).
⚡ Ação: O que faz a profundidade limitada?
👉 Impede gerar sucessores para além de um limite pré-definido.
⚡ Ação: Porque é que a profundidade limitada pode falhar?
👉 Porque a solução pode estar para além do limite escolhido.
⚡ Ação: Como funciona a procura iterativa?
👉 Executa profundidade limitada com limites crescentes até encontrar solução.
⚡ Ação: Porque é que a procura iterativa é completa?
👉 Porque eventualmente testa todos os níveis até à profundidade da solução.
⚡ Ação: Porque é que a procura iterativa repete trabalho?
👉 Porque os estados dos níveis intermédios são gerados várias vezes.
⚡ Ação: Como funciona a procura bidirecional?
👉 Realiza duas procuras, uma a partir do estado inicial e outra a partir do estado final, parando quando se encontram.
⚡ Ação: Qual é a grande vantagem da procura bidirecional?
👉 Reduz a complexidade temporal para O(b^(d/2)).
⚡ Ação: Porque é que a procura bidirecional exige mais memória?
👉 Porque precisa de manter ambas as árvores de procura em memória.
⚡ Ação: Em que problemas a procura bidirecional não é aplicável?
👉 Nos problemas em que o estado final não é conhecido, como 8 damas e partição.
Nova pergunta: 🎲
1.9.8