📄 Ver slides (PDF)
⚡ Ação: O que distingue uma procura informada de uma procura cega?
👉 A procura informada utiliza informação heurística adicional para orientar a procura, enquanto a procura cega usa apenas a definição exata do problema.
⚡ Ação: O que representa a heurística h(n)?
👉 Uma estimativa da distância do estado atual até à solução mais próxima.
⚡ Ação: Porque é que a heurística não pertence à definição do problema?
👉 Porque é informação adicional usada apenas para guiar a procura, não faz parte da especificação formal do problema.
⚡ Ação: O que significa uma heurística ser otimista?
👉 Significa que nunca sobrestima o custo real até à solução.
⚡ Ação: Porque é importante que a heurística seja otimista?
👉 Para garantir que algoritmos como o A* retornam soluções ótimas.
⚡ Ação: Qual é a heurística sugerida para o problema do aspirador?
👉 O número de casas sujas.
⚡ Ação: Qual é a heurística sugerida para o Puzzle 8?
👉 O número de peças fora da posição final.
⚡ Ação: Porque é que a heurística das 8 damas não é útil?
👉 Porque dá o mesmo valor para qualquer estado com o mesmo número de damas colocadas, não distinguindo estados promissores.
⚡ Ação: Porque é que a heurística da partição também não é útil?
👉 Porque não distingue estados que podem ou não conduzir à solução, apesar de ser admissível.
⚡ Ação: O que têm em comum os problemas das 8 damas e da partição relativamente às heurísticas?
👉 Não têm um estado final conhecido, dificultando a construção de heurísticas eficazes.
⚡ Ação: Qual é a regra de expansão do algoritmo melhor‑primeiro?
👉 Expande o estado com menor valor heurístico h(n).
⚡ Ação: Porque é que o melhor‑primeiro pode falhar?
👉 Porque apenas vê o custo da próxima ação.
⚡ Ação: O que acontece no melhor‑primeiro quando vários estados têm o mesmo valor heurístico?
👉 O algoritmo pode expandir qualquer um deles, sem critério adicional.
⚡ Ação: Porque é que o melhor‑primeiro funciona melhor em procura em grafo do que em árvore?
👉 Porque evita gerar repetidamente estados já vistos.
⚡ Ação: No exemplo do Puzzle 8, qual foi o primeiro estado escolhido após a expansão inicial?
👉 O estado com heurística igual a 1, por ser o menor valor na fronteira.
⚡ Ação: Qual é a principal limitação do melhor‑primeiro?
👉 Não considera o custo acumulado g(n), apenas a heurística.
⚡ Ação: Porque é que o melhor‑primeiro é considerado ganancioso?
👉 Porque vê o que melhora no curto prazo, tenta sempre aproximar‑se do objetivo, mesmo que isso não leve à solução ótima.
⚡ Ação: O que acontece no exemplo do aspirador quando se usa melhor‑primeiro em árvore?
👉 São gerados muitos estados repetidos, porque não há controlo de duplicados.
⚡ Ação: Porque é que o melhor‑primeiro pode gerar muitos estados iguais?
👉 Porque não distingue entre estados com poucas ou muitas ações já realizadas.
⚡ Ação: Qual é a vantagem do melhor‑primeiro quando a heurística é muito boa?
👉 Consegue orientar a procura rapidamente para a solução.
⚡ Ação: O que define o valor f(n) no A*?
👉 f(n) = g(n) + h(n), combinando custo percorrido e heurística.
⚡ Ação: O que significa a heurística ser admissível?
👉 Nunca sobrestima o custo real até à solução.
⚡ Ação: O que significa a heurística ser consistente?
👉 Que a diferença entre heurísticas de estados vizinhos não excede o custo da ação entre eles.
⚡ Ação: Porque é que a admissibilidade é essencial para o A*?
👉 Porque garante que o algoritmo encontra a solução ótima.
⚡ Ação: Porque é que o A* tem problemas de memória?
👉 Porque mantém todos os estados gerados na fronteira.
⚡ Ação: O que faz o A* pesado?
👉 Multiplica a heurística por um peso W, alterando a prioridade dos estados.
⚡ Ação: O que acontece quando W=0 no A* pesado?
👉 O algoritmo torna‑se equivalente ao custo uniforme.
⚡ Ação: O que acontece quando W é muito elevado?
👉 O algoritmo aproxima‑se do melhor‑primeiro.
⚡ Ação: Porque é que o A* pesado perde otimalidade?
👉 Porque a heurística multiplicada pode ultrapassar o valor real.
⚡ Ação: Como funciona o A* limitado?
👉 Mantém apenas um número máximo de estados na fronteira, apagando os de pior valor.
⚡ Ação: O que limita cada iteração do IDA*?
👉 O valor máximo permitido para f(n).
⚡ Ação: Como é escolhido o limite seguinte no IDA*?
👉 É o menor valor de f(n) que ultrapassou o limite anterior.
⚡ Ação: Porque é que o IDA* não tem problemas de memória?
👉 Porque utiliza procura em profundidade iterativa.
⚡ Ação: O que é o lower bound no BnB?
👉 O valor f(n) = g(n) + h(n), assumindo heurística admissível.
⚡ Ação: O que é o upper bound no BnB?
👉 O custo da melhor solução encontrada até ao momento.
⚡ Ação: Quando é feito um corte no BnB?
👉 Quando o lower bound de um estado é maior ou igual ao upper bound.
⚡ Ação: Porque é que o BnB pode entrar em ramos infinitos?
👉 Porque usa profundidade e pode processar um estado pior, quando tinha em estados superiores melhores alternativas.
⚡ Ação: Como evitar ramos infinitos no BnB?
👉 Usando uma versão iterativa com limites crescentes no upper bound.
⚡ Ação: O que significa relaxar um problema?
👉 Criar uma versão mais simples do problema original, cuja solução serve como heurística.
⚡ Ação: Como é relaxado o problema do aspirador?
👉 Ignorando a necessidade de o aspirador estar na casa suja para a limpar.
⚡ Ação: Como é relaxado o Puzzle 8 na heurística alternativa?
👉 Permitindo que as peças se movam livremente na horizontal e vertical até ao destino final.
⚡ Ação: Porque é que heurísticas não admissíveis podem ser úteis?
👉 Porque podem guiar a procura mesmo sem garantir otimalidade.
⚡ Ação: Que característica pode ser usada como heurística não admissível nas 8 damas?
👉 O número de casas não atacadas nas colunas ainda sem damas.
Nova pergunta: 🎲
1.9.8