Árvores de busca

Exemplo: um robô em um labirinto

• Imagine um robô que precisa encontrar a saída de um labirinto.
• Ele pode se mover em quatro direções: cima, baixo, esquerda e direita (exceto quando há uma parede).
• Modelagem do problema

Exemplo: um robô em um labirinto

O robô pode começar indo para a direita

Exemplo: um robô em um labirinto

Caminho bloquado

Portanto, é preciso voltar atrás para procurar outra opção

Exemplo: um robô em um labirinto

Como conhecemos a estrutura do labirinto, podemos calcular todas essas opções antes que o robô se mova

Exploração da árvore de busca

• Se desenvolvemos toda a árvore de estados, podemos identificar a sequência de ações que leva à saída do labirinto.
• Existem diferentes estratégias para expandir a árvore de forma “inteligente”:
• Objetivo 1: encontrar a solução explorando o menor número possível de estados.
• Objetivo 2: encontrar as melhores soluções (por exemplo, com menos ações ou menor custo).

Uma abordagem genérica

• Os algoritmos que veremos são genéricos: em vez de um robô em um labirinto, podemos resolver vários tipos de problemas: um cubo de Rubik, uma busca de rota entre duas cidades...
• O que precisamos modelar
• Estados: representação do mundo, jogo ou problema.
• Ações: conjunto de ações possíveis em cada estado.
• Transições: capacidade de calcular o efeito de uma ação no estado do mundo.

Idéias de base

• Um problema pode ser modelado como um espaço de estados.
• Inclui um conjunto de estados.
• Estados: todas as configurações possíveis.
• Ações: para cada estado, um conjunto de ações disponíveis.
• Função de transição: associa a cada par (estado, ação) um novo estado resultante.
• Teste de objetivo: identifica quais estados são estados finais.
• Objetiv: encontrar uma sequência de ações que leve do estado inicial até um estado objetivo.
• Alguns problemas, existe uma função de custo associada a cada par (estado, ação).
• Objetivo: encontrar uma sequência de ações de custo mínimo que leve do estado inicial até um estado objetivo.

Exemplo: viagem pela Romênia

• Estados: a pessoa está em uma cidade.
• Estado inicial: a pessoa está em Lugoj.
• Modelagem do problema
• Ações: mover-se para uma cidade vizinha.
• Teste de objetivo: o estado objetivo é único: estar em Bucharest.
• Custo do problema
• Custo: a distância entre as cidades.
• Objetivo: encontrar o caminho com menor custo total até Bucharest.

Exemplo: jogo dos 15

• Estados: todas as grades 3×3 com os números {1, …, 8} e uma casa vazia.
• Estado inicial: uma configuração
• Ações: mover a casa vazia para cima, baixo, esquerda ou direita
• Peças estão em ordem crescente.
• Custo do problema
• Custo: cada movimento = 1.
• Objetivo: encontrar a sequência mínima de movimentos para chegar ao estado final.

Origem:

Alvo:

Árvore de busca

• Na prática, não representamos todos os estados possíveis
• Em vez disso, construímos uma árvore de busca.
• Nós: representam os estados.
• Raiz: o estado inicial.
• A partir da raiz, exploramos os sucessores de cada nó aplicando todas as ações possíveis.
• Folhas: estados sem sucessores (sem ações disponíveis).
• É importante evitar reexplorar estados já visitados.
• Isso impede repetições e torna a busca mais eficiente.

Árvore de busca - exemplo

Análise da árvore de busca

• Número total de estados: tamanho do espaço de estados possível.
• Fator de ramificação: número de ações disponíveis em um estado (pior caso).
• Profundidade da árvore: número de ações entre o estado inicial e um estado objetivo (pior caso).
• Número de folhas / estados objetivo: quantos estados finais existem.

Exemplo: jogo dos 15

• Número total de estados: 9! = 362.880
• (na prática, 9!/2 pois metade dos estados não é solucionável)
• Fator de ramificação: 4 (máximo de movimentos possíveis).
• Profundidade da árvore: infinita se não evitarmos repetições de estados.
• Foi demonstrado (Reinefeld, IJCAI 1993) que soluções ótimas podem exigir até 31 movimentos.
• Número de folhas: 1 único estado objetivo.

Comparação des modelagens

• Travessia do rio — versão 1
• Personagens: três missionários e três canibais.
• Estado do mundo: identidade de cada missionário e canibal em cada lado do rio.
• Ações disponíveis: 21 ações possíveis.
• Travessia do rio — versão 2
• Estado do mundo: número de missionários e canibais em cada lado do rio.
• Ações disponíveis: 5 ações possíveis:
• Na versão 2, o fator de ramificação é muito menor que na versão 1.
• Se generalizarmos para k missionários e k canibais:
• A versão 2 mantém o mesmo número de ações.
• A versão 1 cresce conforme k aumenta.
• Vídeo da solução (para curiosos):
https://www.youtube.com/watch?v=laLS8gHzROg

Raciocínio Retroativo (Backward Chaining)

• Diagramas de decisão são a base visual para o Backward Chaining em Sistemas Especialistas. O motor de inferência tenta "provar" o nó raiz navegando para as folhas.
• O Processo de Redução
1. Comece com uma meta (Hipótese).
2. Encontre regras cuja conclusão satisfaça a meta.
3. As premissas dessas regras tornam-se novas sub-metas.
4. Repita até encontrar fatos conhecidos (Folhas da árvore).

Lógica Proposicional

Lógica Proposicional

Formalismo da Lógica Proposicional

Exemplos

• "Se estamos em Brasília, então há sol":
  Brasília → sol
• No Sudoku, a variável \( x^{i,j}_k \) representa: "a célula (j,k) contém o valor i".
• Se a primeira célula da primeira linha contém 1, então não há nenhum 1 em nenhum outra lugar dessa linha:
  \( x^{1,1}_1 \to (\neg x^{2,1}_1 \wedge ... \wedge x^{9,1}_1 ) \)

Semântica e Tabelas-Verdade

Problema exemplo

"Em um reino antigo, o rei coloca um prisioneiro diante de duas celas, que podem conter um tigre ou uma princesa.

O prisioneiro deve entrar em uma cela: se houver um tigre, ele é devorado; se houver uma princesa, ele é libertado e se casa com ela.

Há placas nas portas com pistas, e o rei afirma que uma delas diz a verdade e a outra mente."

Pistas nas portas

• Dica-porta 1: “Há uma princesa nesta cela e um tigre na outra.”
• Dica-porta 2: “Há uma princesa em uma das celas e há um tigre em uma das celas.”

Problema lógico

• Sabendo que uma frase é verdadeira e a outra é falsa, qual porta você escolheria?

Modelagem

Podemos modelar de diferentes formas

• Variáveis: t1, t2 representam “há um tigre na cela 1 / cela 2”.
• Variáveis: p1, p2 representam “há uma princesa na cela 1 / cela 2”.
• Problema: isso complica a resolução, pois exige 2⁴ = 16 linhas na tabela-verdade e ainda é necessário impor que não pode haver tigre e princesa na mesma cela.
• Podemos usar apenas t1 e t2.
• Princesa: é representada por ¬t1 e ¬t2.

Formalização das portas

• Dica-porta 1:“Há uma princesa nesta cela e um tigre na outra” ϕ= ¬t1 ∧ t2
• Dica-porta 2:“Há uma princesa em uma cela e há um tigre em uma cela” ϕ₂ = (¬t1 ∨ ¬t2) ∧ (t1 ∨ t2)

Condição lógica do problema

• Uma placa diz a verdade e a outra mente:
• ϕ = ϕ₁ ↔ ¬ϕ₂

Definições lógicas do problema

• ϕ₁ = ¬t1 ∧ t2
• ϕ₂ = (¬t1 ∨ ¬t2) ∧ (t1 ∨ t2)
• ϕ = ϕ₁ ↔ ¬ϕ₂

único modelo onde o tigre está em uma cela e a princesa na outra

Algoritmos de raciocínio lógico e CNF

• Forma Normal Conjuntiva (CNF): os algoritmos de lógica usam CNF (Conjunctive Normal Form).
• Toda fórmula proposicional pode ser transformada em uma CNF equivalente (com os mesmos modelos).
• Literal: uma variável sozinha ou sua negação.
• Exemplos: x, ¬y (x ∨ ¬y não é um literal).
• Cláusula: disjunção (OU) de literais.
• Exemplos: ¬y, x ∨ ¬y (x ∧ ¬y não é cláusula)
• Uma interpretação satisfaz uma cláusula se satisfaz pelo menos um literal (pois é uma disjunção).
• CNF: conjunção (E) de cláusulas.
• Uma fórmula CNF tem uma ou várias cláusulas ligadas por ∧.
• Uma interpretação satisfaz uma CNF se satisfaz todas as cláusulas (pois é uma conjunção).

SAT Solver

• Um algoritmo que recebe uma CNF e decide se ela é satisfatível.
• Ou seja, verifica se existe ao menos um modelo que satisfaz a fórmula.
• Se existir, o solver também pode retornar esse modelo.

Transformação em CNF

• Eliminação de dupla negação
• ¬¬ϕ ≡ ϕ
• Leis de De Morgan
• ¬(ϕ₁ ∨ ϕ₂) ≡ ¬ϕ₁ ∧ ¬ϕ₂
• ¬(ϕ₁ ∧ ϕ₂) ≡ ¬ϕ₁ ∨ ¬ϕ₂
• Distributividade
• ϕ₁ ∨ (ϕ₂ ∧ ϕ₃) ≡ (ϕ₁ ∨ ϕ₂) ∧ (ϕ₁ ∨ ϕ₃)
• ϕ₁ ∧ (ϕ₂ ∨ ϕ₃) ≡ (ϕ₁ ∧ ϕ₂) ∨ (ϕ₁ ∧ ϕ₃)
• Transformação para CNF
• A aplicação sucessiva dessas regras permite transformar qualquer fórmula em uma CNF equivalente.
• Atenção: essa transformação pode gerar uma fórmula exponencialmente maior que a original.
• Existe uma técnica mais avançada que mantém tamanho linear: transformação de Tseitin.
• Validação das regras
• Essas equivalências podem ser provadas usando tabelas-verdade.

Funcionamento dos solvers SAT

• DPLL: a maioria dos solvers SAT usa o algoritmo DPLL (Davis–Putnam–Logemann–Loveland).
• Princípio básico do DPLL
• Escolher uma variável \(x_i\) e atribuir um valor de verdade (ex: 1).
• Cláusulas que contêm \(x_i\) são satisfeitas e podem ser removidas.
• Cláusulas que contêm \(\neg x_i\) são simplificadas:
  ex: \(x_1\) ∨ \(x_2\) ∨ \(\neg x_i\) viram \(x_1\) ∨ \(x_2\)
• Se surgir uma cláusula vazia (todos os literais falsos), há uma decisão incoerente \(\to\) backtracking
• O algoritmo volta atrás (backtracking) e tenta \(x_i\) = 0.
• Se 0 também gerar incoerência, a fórmula não é satisfatível (não existe modelo).
• Caso contrário, o processo continua até atribuir valores para todas as variáveis.

Simplificações durante o processo

• Propagação unitária: se existe uma cláusula unitária (ex: x ou ¬y), ela força valores nas demais cláusulas.
• Ex: x = 1 e y = 0 são propagados automaticamente.
• Literals puros: se uma variável aparece sempre com a mesma polaridade (ex: apenas x e nunca ¬x), pode-se atribuir valor diretamente.
• Ex: x = 1 satisfaz todas as cláusulas onde x aparece.

Relação do DPLL com busca em árvore

• DPLL compartilha pontos em comum com a busca em árvore (tree search).
• Estados: conjunto de variáveis com valores atribuídos ou não.
• Ações: atribuir um valor (0 ou 1) a uma variável.
• Estados objetivo: todas as variáveis estão atribuídas e todas as cláusulas são satisfeitas.
• Existem heurísticas para escolher variáveis de forma inteligente.
• Objetivo: encontrar rapidamente uma solução ou detectar inconsistências cedo.
• O uso de CNF torna o problema mais estruturado para o algoritmo.
• Técnicas como propagação unitária e eliminação de literais puros aceleram a resolução.
• Outras otimizações mais avançadas também são usadas em solvers modernos.
• Essas técnicas tornam o DPLL muito mais eficiente do que uma busca em árvore simples.

Sistemas Especialistas

Como um computador pode resolver integrais de cálculo?

• O Problema: Integrais não são resolvidas por força bruta, mas por transformações.
• A Estratégia: Redução (complexidade) Quebrar um problema difícil em sub-problemas mais fáceis.

Diagramas AND-OR

Um diagrama de decisão é fundamentalmente uma estrutura AND-OR que representa a decomposição de um problema em uma árvore:

• Nós OR: Representam diferentes métodos para resolver o mesmo problema (Se o Método A OU o Método B funcionar, o problema está resolvido).
• Nós AND: Representam sub-problemas que precisam ser resolvidos simultaneamente (Para resolver X, preciso resolver Y E Z).

        Meta Principal: Resolver Integral(f(x))
        ├── OR: Substituição de Variável
        └── OR: Integração por Partes
            └── AND: Escolher 'u'
            └── AND: Escolher 'dv'
        

• O Conhecimento: O mundo é descrito por fatos e regras.
• O Objetivo: Dedução. Usar o que sabemos para derivar novas conclusões logicamente irrefutáveis dentro do sistema.
• Quadro: Sistemas de Produção.

Ideia Central

• Representar o conhecimento humano via regras lógicas.
• Separar o Conhecimento (regras) do Motor de Inferência (algoritmo).
• Explicabilidade: O sistema pode dizer exatamente qual regra usou para chegar ao resultado.

O Sistema de Produção

Consiste em três componentes principais:

1. Memória de Trabalho (Fatos)
2. Base de Regras (Conhecimento: SE -> ENTÃO)
3. Motor de Inferência (O Executor)
        

Encadeamento Progressivo (Forward Chaining)

Como deduzir fatos novos?

O sistema parte dos fatos conhecidos e aplica as regras para adicionar novos fatos à memória até que um objetivo seja alcançado ou não haja mais regras para disparar.

Exemplo de Regra:

IF  'o animal tem penas' 
THEN 'o animal é uma ave'
        

Isso é um exemplo de Dedução Orientada a Dados.

Encadeamento Regressivo (Backward Chaining)

A ideia fundamental: "Para provar uma hipótese, prove as premissas que a tornam verdadeira."

O sistema começa com uma pergunta (ex: "O animal é um pinguim?") e busca na base de regras o que seria necessário para que isso fosse verdade, transformando premissas em novos sub-objetivos.

Resolução de Conflitos

O que fazer quando múltiplas regras podem ser disparadas ao mesmo tempo?

• Especificidade: Regras mais complexas (mais condições) ganham de regras genéricas.
• Recência: Usar os fatos que entraram na memória por último.
• Prioridade: Ordem definida pelo especialista.