Algoritmos informados: melhor primeiro; A*; BnB.
📖 Leituras
- (Russell & Norvig): Secções 3.5 e 3.6 (3ª e 4ª edição) | Capítulo 4 (2ª edição)
Bibliografia
⚡ Ação: O que caracteriza o Melhor Primeiro (greedy best‑first)?
👉 Expande sempre o nó com menor valor heurístico h(n), tentando aproximar-se rapidamente do objetivo.
⚡ Ação: Porque é que o Melhor Primeiro (greedy best‑first) pode falhar em encontrar a solução ótima?
👉 Porque ignora o custo já percorrido e pode escolher caminhos aparentemente promissores mas mais longos.
⚡ Ação: O que significa h(n) na procura informada?
👉 É a estimativa do custo do caminho mais barato do estado atual até um estado objetivo.
⚡ Ação: Porque é que a heurística da distância em linha reta é útil no exemplo da Roménia?
👉 Porque está correlacionada com as distâncias reais das estradas, fornecendo uma estimativa razoável.
⚡ Ação: A procura Melhor Primeiro (greedy best‑first) é completa?
👉 É completa apenas em espaços de estados finitos. 0
⚡ Ação: Porque é que a procura Melhor Primeiro (greedy best‑first) pode ser muito rápida com uma boa heurística?
👉 Porque tende a expandir apenas estados próximos do objetivo, evitando explorar toda a árvore.
⚡ Ação: O que significa dizer que a heurística não pode ser calculada a partir da definição do problema?
👉 Que a heurística depende de conhecimento externo ao modelo formal, como mapas ou propriedades do domínio.
⚡ Ação: Porque é que a procura Melhor Primeiro (greedy best‑first) é chamada “gananciosa”?
👉 Porque tenta sempre aproximar-se do objetivo no passo imediato, sem considerar consequências futuras.
⚡ Ação: Qual é a principal desvantagem da procura Melhor Primeiro (greedy best‑first)?
👉 Pode encontrar soluções muito piores do que a ótima.
⚡ Ação: O que representa f(n) no A*?
👉 f(n) = g(n) + h(n), estimando o custo total da solução passando por n.
⚡ Ação: O que significa uma heurística ser admissível?
👉 Que nunca sobrestima o custo real até ao objetivo.
⚡ Ação: Porque é que a admissibilidade garante otimalidade no A*?
👉 Porque impede que o algoritmo descarte caminhos que podem levar à solução ótima.
⚡ Ação: O que significa uma heurística ser consistente?
👉 Que satisfaz a desigualdade triangular: h(n) ≤ c(n,a,n') + h(n').
⚡ Ação: Porque é que a consistência evita reintroduzir estados na fronteira?
👉 Porque garante que a primeira vez que um estado é alcançado corresponde ao caminho ótimo até ele.
⚡ Ação: O que são “contornos” numa procura A*?
👉 Regiões do espaço de estados onde todos os nós têm f(n) ≤ um certo valor.
⚡ Ação: Porque é que os contornos do A* se alongam na direção do objetivo?
👉 Porque a heurística orienta a expansão para estados mais promissores.
⚡ Ação: Que nós são certamente expandidos pelo A?
👉 Todos os nós com f(n) < C, onde C* é o custo da solução ótima.
⚡ Ação: Porque é que o A* é considerado “otimamente eficiente”?
👉 Porque nenhum algoritmo que use a mesma heurística pode expandir menos nós sem perder otimalidade.
⚡ Ação: Porque é que o A* pode expandir muitos nós mesmo com heurísticas boas?
👉 Porque o número de estados com f(n) < C* pode ser exponencial.
⚡ Ação: O que faz o weighted A*?
👉 Usa f(n) = g(n) + W × h(n), dando mais peso à heurística.
⚡ Ação: Porque é que o weighted A* encontra soluções mais rapidamente?
👉 Porque foca a procura mais fortemente na direção do objetivo.
⚡ Ação: O weighted A* é ótimo?
👉 Não; encontra soluções dentro de um fator W do custo ótimo.
⚡ Ação: O que é uma heurística não admissível?
👉 Uma heurística que pode sobrestimar o custo real até ao objetivo.
⚡ Ação: Porque é que heurísticas não admissíveis podem ser úteis?
👉 Porque podem reduzir drasticamente o número de estados explorados.
⚡ Ação: O que é o “detour index”?
👉 Um fator multiplicativo aplicado à distância em linha reta para aproximar distâncias reais.
⚡ Ação: Qual é o principal problema do A* em termos de memória?
👉 Precisa guardar todos os estados na fronteira e na tabela de alcançados.
⚡ Ação: Como o IDA* resolve o problema de memória?
👉 Usa profundidade iterativa com limite em f(n), evitando armazenar todos os estados.
⚡ Ação: Porque é que o IDA* pode ter muitas iterações?
👉 Porque cada novo limite pode acrescentar apenas um estado ao contorno.
⚡ Ação: O que distingue o RBFS do IDA*?
👉 O RBFS mantém valores f “backup” para decidir quando reexpandir subárvores, usando memória linear.
⚡ Ação: Porque é que a heurística h(n) é aplicada ao nó e não apenas ao estado?
👉 Por tradição e consistência com f(n) e g(n), embora a heurística dependa apenas do estado e não da estrutura do nó.
⚡ Ação: O que significa dizer que uma heurística “correlaciona‑se” com o custo real?
👉 Significa que valores mais baixos da heurística tendem a corresponder a estados mais próximos da solução, tornando‑a útil para orientar a procura.
⚡ Ação: Porque é que o A* não expande imediatamente um estado objetivo quando ele aparece na fronteira?
👉 Porque só o expande quando tiver o menor valor f(n), garantindo que não existe outro caminho potencialmente mais barato.
⚡ Ação: O que acontece se a heurística for admissível apenas ao longo de um dos caminhos ótimos?
👉 O A* encontra esse caminho ótimo, mesmo que a heurística seja má noutros estados.
⚡ Ação: Porque é que heurísticas inconsistentes podem obrigar a reintroduzir estados na fronteira?
👉 Porque podem surgir caminhos alternativos com custo g(n) mais baixo, exigindo atualizar sucessores e reavaliar o estado.
⚡ Ação: O que significa dizer que o A* “poda” estados?
👉 Significa que evita expandir estados cujo valor f(n) é superior ao custo da solução ótima, eliminando-os sem os explorar.
⚡ Ação: Porque é que os contornos de g(n) são circulares, mas os de f(n) são alongados?
👉 Porque g(n) cresce uniformemente em todas as direções, enquanto f(n) incorpora h(n), que direciona a expansão para o objetivo.
⚡ Ação: O que significa um nó estar “no contorno do objetivo”?
👉 Que o seu valor f(n) é exatamente igual ao custo da solução ótima C*, podendo ser expandido antes da solução final.
⚡ Ação: Porque é que o A* pode expandir vários nós com f(n) = C* antes de encontrar o objetivo?
👉 Porque todos esses nós são candidatos a caminhos ótimos e o algoritmo não sabe qual deles conduz ao objetivo até os expandir.
⚡ Ação: Porque é que heurísticas mais informativas reduzem o número de nós com f(n) < C?
👉 Porque aproximam melhor o custo real, estreitando os contornos e reduzindo a área que o A precisa explorar.
⚡ Ação: O que caracteriza uma heurística “demasiado fraca”?
👉 Produz valores muito semelhantes para muitos estados, oferecendo pouca orientação e aproximando o A* do custo uniforme.
⚡ Ação: Porque é que o weighted A* pode ser visto como “semi‑ganancioso”?
👉 Porque aumenta o peso da heurística, aproximando-se do comportamento ganancioso, mas sem ignorar totalmente o custo g(n).
⚡ Ação: O que distingue bounded‑suboptimal search de bounded‑cost search?
👉 A bounded‑suboptimal garante uma solução dentro de um fator W do ótimo; a bounded‑cost exige apenas que o custo seja inferior a um limite C.
⚡ Ação: Porque é que o IDA* funciona particularmente bem no Puzzle 8?
👉 Porque os valores f(n) são inteiros e formam contornos discretos, permitindo progressão regular entre iterações.
Nova pergunta: 🎲
1.9.8