Tutorial: Procuras Construtivas

Algoritmos Cegos › 📖 Leitura 👓 Procura Cega 👓 Algoritmos Aspirador › 💻 Parte 1 💻 Parte 2 Puzzle 8 › ✏️ Profundidade ✏️ Iterativa ✏️ Largura 💻 Testar Partição › ✏️ Profundidade ✏️ Largura 💻 Testar Damas › ✏️ Profundidade ✏️ Largura 💻 Testar Algoritmos Informados › 📖 Leitura 👓 Procura Informada Puzzle 8 › ✏️ Melhor Primeiro ✏️ A-star ✏️ BnB 💻 Testar

📄 Ver slides (PDF)

⚡ Ação: O que caracteriza um problema de procura?

👉 Um problema de procura exige que o agente encontre uma solução através de uma sequência de ações que o leve de um estado inicial até um estado objetivo.

⚡ Ação: Porque é que os algoritmos cegos são chamados de não informados?

👉 Porque não utilizam qualquer informação adicional além da definição do problema; não têm conhecimento sobre que ações são melhores.

⚡ Ação: O que significa dizer que um estado é indivisível?

👉 Significa que o algoritmo trata o estado como uma unidade completa, sem decomposição interna ou estrutura adicional.

⚡ Ação: Em que condições o agente consegue validar se um estado é objetivo?

👉 Quando existe uma função teste ou um conjunto de estados finais que permite verificar se o estado satisfaz o objetivo.

⚡ Ação: Porque é que os algoritmos cegos precisam de explorar estados seguintes?

👉 Porque não têm informação sobre qual ação é melhor, sendo necessário explorar para descobrir um caminho até ao objetivo.

⚡ Ação: O que significa o ambiente ser completamente observável?

👉 Significa que o agente consegue ver todo o estado do ambiente, como no exemplo do labirinto onde vê todas as bifurcações.

⚡ Ação: O que implica o ambiente ser determinístico?

👉 Implica que cada ação leva sempre ao mesmo estado seguinte, sem aleatoriedade.

⚡ Ação: Porque é que um ambiente sequencial exige uma sequência de ações?

👉 Porque o agente precisa de tomar várias decisões ao longo do tempo para atingir o estado final.

⚡ Ação: O que significa o ambiente ser estático?

👉 Significa que o ambiente não muda enquanto o agente delibera sobre as ações a tomar.

⚡ Ação: Porque é que o ambiente deve ser discreto num problema de procura?

👉 Porque o número de estados e ações deve ser finito para permitir a procura.

⚡ Ação: O que deve responder a definição do objetivo?

👉 Deve indicar claramente o que se pretende atingir, sem envolver grandezas a maximizar ou minimizar.

⚡ Ação: Qual a diferença entre definir o objetivo por função teste ou por conjunto de estados finais?

👉 A função teste verifica se um estado é final; o conjunto de estados finais lista explicitamente todos os estados que satisfazem o objetivo.

⚡ Ação: O que representa o estado inicial?

👉 Representa a situação atual do agente e deve pertencer ao espaço de estados.

⚡ Ação: O que são ações possíveis num problema de procura?

👉 São as decisões que o agente pode tomar a partir de um estado, definindo como pode progredir.

⚡ Ação: Quando é que não existe um problema de procura?

👉 Quando não existem decisões a tomar; nesse caso o agente apenas segue o estado sem alternativas.

⚡ Ação: O que faz o modelo de transição?

👉 Dado um estado e uma ação, devolve o estado resultante dessa ação.

⚡ Ação: O que pode acontecer se uma ação não for aplicável a um estado?

👉 O modelo de transição deve devolver um estado que represente impossibilidade, que não deve ser considerado sucessor.

⚡ Ação: Como se define o custo de uma ação?

👉 Através de uma função que atribui um valor numérico ao custo de passar de um estado para outro.

⚡ Ação: O que é a função sucessores?

👉 É a função que devolve todos os estados alcançáveis a partir de um estado aplicando cada ação possível.

⚡ Ação: Para que serve definir o espaço de estados explicitamente?

👉 Para compreender a dimensão do problema e garantir que todos os estados possíveis estão bem definidos.

⚡ Ação: O que são restrições num problema de procura?

👉 São condições que eliminam estados ou soluções que não interessam ou que não conduzem ao objetivo.

⚡ Ação: Como podem as restrições melhorar a procura?

👉 Eliminando estados inúteis cedo, reduzindo o espaço de procura e o tempo necessário.

⚡ Ação: O que é o processo de abstração?

👉 É omitir detalhes irrelevantes para manter o problema tratável, mantendo apenas o essencial.

⚡ Ação: Porque é importante ver o problema de vários pontos de vista?

👉 Para garantir que a especificação está correta e que o problema modelado corresponde ao que se pretende resolver.

⚡ Ação: Porque devemos começar pelas perguntas mais fáceis ao definir um problema?

👉 Porque ajudam a clarificar o essencial e facilitam a tomada de decisões nas partes mais complexas.

⚡ Ação: Quando é útil definir custos diferentes para ações?

👉 Quando o desempenho do agente depende do custo total da solução, permitindo distinguir soluções ótimas.

⚡ Ação: Porque é que demasiados detalhes tornam o problema proibitivo?

👉 Porque aumentam exponencialmente o espaço de estados, tornando a procura impraticável.

⚡ Ação: O que significa um caminho num problema de procura?

👉 É uma sequência de estados ligados por ações sucessivas.

⚡ Ação: Como se relacionam sucessores e modelo de transição?

👉 A função sucessores pode ser construída aplicando o modelo de transição a todas as ações possíveis.

⚡ Ação: Quando é preferível definir sucessores em vez de ações e modelo de transição?

👉 Quando as ações são complexas e é mais simples listar diretamente os estados seguintes.

⚡ Ação: Como é representado um estado no problema do aspirador?

👉 Como um triplo contendo a posição do agente e a situação (suja/limpa) de cada uma das duas casas.

⚡ Ação: Qual é o objetivo no problema do aspirador?

👉 Ter ambas as casas limpas, independentemente da posição do agente.

⚡ Ação: Como é representado o espaço de estados no Puzzle 8?

👉 Como um triplo de triplos contendo uma permutação dos números 0 a 8, onde 0 representa o espaço vazio.

⚡ Ação: Que restrição simples pode ser aplicada ao Puzzle 8?

👉 Impedir movimentos inversos consecutivos, como esq seguido de dir.

⚡ Ação: Como é representado um estado no problema das 8 damas?

👉 Como um tuplo de 8 valores, cada um indicando a linha onde a dama dessa coluna está colocada.

⚡ Ação: Que restrição impede que duas damas se ataquem?

👉 Não podem estar na mesma linha, nem na mesma coluna e diagonal.

⚡ Ação: O que define o estado inicial no problema da partição?

👉 Um conjunto de números por colocar, com os conjuntos da esquerda e direita vazios.

⚡ Ação: Qual é o objetivo no problema da partição?

👉 Colocar todos os números de forma que a soma dos dois lados seja igual.

⚡ Ação: Porque se coloca sempre o maior número primeiro na partição?

👉 Porque os números pequenos encaixam mais facilmente e isso reduz estados redundantes.

⚡ Ação: O que são os dados da instância no problema da partição?

👉 O conjunto inicial de números a dividir, que não precisa de ser duplicado na árvore de procura.

Nova pergunta: 🎲

◀ Passo anterior Próximo passo ▶