Resolução de Problemas
Grupo:
Roselis Fraga
José Vianney M. de Alencastro Junior
Wanderley Pessoa
Agentes de Resolução de Problemas
Sem informação sobre problema além de sua definição
Baseado em objetivos
Descobrir sequencia de ações para estado objetivo
Busca – Problema como entrada e como saída a solução.
Execução
Resolução de Problemas por meio de Busca
Agentes de Resolução de Problemas
Busca
Resolução de Problemas por meio de Busca
Agentes de Resolução de Problemas
� Problema e soluções bem definidosComponentes:• Estado inicial
Em(Recife)
• Função sucessor
<ação,sucessor>
Resolução de Problemas por meio de Busca
{<Ir(Vitória),Em(Vitória)>,<Ir(Gravatá),Em(Gravatá)>,<Ir(Caruaru),Em(Caruaru)>}
Agentes de Resolução de Problemas
� Problema e soluções bem definidos
� Espaço de Estados
Espaço inicial + Função sucessorTodos estados acessíveisForma Grafo (Nós= estados ; Arcos = ações)
� Caminho
Sequencia de estados conectados por ações
Resolução de Problemas por meio de Busca
Agentes de Resolução de Problemas
� Problema e soluções bem definidos
• Teste Objetivo
{Em(Caruaru)}
“xeque-mate”
• Função Custo de Caminho/Custo do Passo
� Atribui custo numérico a cada caminho/Passo
� Medida de desempenho
� Solução ótima (Menor custo caminho)
Resolução de Problemas por meio de Busca
Agentes de Resolução de Problemas
� Formulação de Problemas
• Abstração
� Omissão de aspectos do mundo real
� Abstrair estados
� Abstrair ações
� Execução mais fácil que problema original
Resolução de Problemas por meio de Busca
Exemplos de Problemas
� Miniproblemas
Ilustrar e exercitar métodos de resolução de problemas.
Comparar desempenho de algoritmos
Resolução de Problemas por meio de Busca
Exemplos de Problemas - Miniproblemas
Quebra Cabeça de 8 Peças
Resolução de Problemas por meio de Busca
Exemplos de Problemas - Miniproblemas
• Estados : Especifica posição de peças e espaço vazio• Estado inicial: Qualquer estado pode ser o inicial• Função Sucessor: Gera estados válidos a partir das
ações (Espaço vazio se desloca para...).• Teste Objetivo: Verifica o estado• Custo de Caminho: Cada passo custa 1,
custo caminho = Número de passos x 1
Resolução de Problemas por meio de Busca
Exemplos de Problemas - Miniproblemas
• Problema pertence a classe NP-Completa• (N²)!/2• Tabuleiro 3x3 = 181.440 estados acessíveis• Tabuleiro 5x5 = 1025 estados acessíveis
Resolução de Problemas por meio de Busca
Exemplos de Problemas – Mundo Real
Roteamento – Viagens aéreas
� Definido: Posições específicas e transições ao longo de ligações entre as posições.
� Estados: Posição (aeroporto)
� Estado inicial/objetivo: Especificado pelo problema
� Função sucessor: retorna os estados resultantes de tomar qualquer voo.
� Teste de objetivo: Estamos no destino especificado?
� Custo de caminho: custo monetário, tempo de espera, tempo de voo, da hora do dia, do tipo de poltrona etc.
Resolução de Problemas por meio de Busca
Exemplos de Problemas – Mundo Real
PCV- Problema do caixeiro Viajante
� Percurso mais curto, menor custo
� Circuito Hamiltoniano
� Planejar viagens , movimentos de máquinas para perfuração de furos em placas de circuitos etc.
� NP- difícil e NP- Completo
Resolução de Problemas por meio de Busca
Exemplos de Problemas – Mundo Real
Circuito Hamiltoniano
Resolução de Problemas por meio de Busca
Exemplos de Problemas – Mundo Real
PCV- Problema do caixeiro Viajante
Resolução de Problemas por meio de Busca
n Rotas por segundo
(n - 1)! Cálculo total
5 250 milhões 24 insignificante
10 110 milhões 362 880 0.003 seg
15 71 milhões 87 bilhões 20 min
20 53 milhões 1.2 x 1017 73 anos
25 42 milhões 6.2 x 1023 470 milhões de anos
Em busca de Soluções
Resolução do problemas: busca no espaço de estados
Técnicas: Arvore de busca Explícita / grafo de busca
Raiz da arvore de busca = nó de busca (estado inicial)
Resolução de Problemas por meio de Busca
Em busca de Soluções
Resolução de Problemas por meio de Busca
• Estado inicial• Estado Objetivo
Em busca de Soluções
Representação de um Nó na arvore
Estado: o estado no espaço de estados correspondente
Nó-pai: O nó na árvore de busca que gerou esse nó
Ação: A ação que foi aplicada ao pai para gerar o nó.
Custo do caminho: custo do caminho desde o estado inicial até esse nó.
Profundidade: O número de passos ao longo do caminho.
Resolução de Problemas por meio de Busca
Em busca de Soluções – Busca em extensão
Resolução de Problemas por meio de Busca
Em busca de Soluções – Medição do Desempenho
Saída: falha ou uma solução
• Aspectos usados para avaliar desempenho de algoritmo
Completeza: Oferece Garantia de um solução quando existir?
Otimização: Encontra uma solução ótima. (menor custo)
Complexidade de tempo: Qual tempo leva?
Complexidade de Espaço: Quanto memória é utilizada. (Recursos físicos)
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)
Busca em Extensão (Busca em Arvore)
Nó raiz expandido primeiro e em seguida todos os sucessores e assim por diante
FIFO: Nós visitados primeiros são expandidos primeiros
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca em Extensão (Busca em Arvore)
Complexidade exponencial -> O(bd+1)Onde-> b = 10 = quantidade de sucessores. (cada estado tem b sucessores)
d = profundidade
Maior Problema: Requisito de memória
Problemas de complexidade exponencial Não podem ser resolvidos por métodos sem informação.
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca de Custo Uniforme
Expande o nó com caminho de custo mais baixo
Se todos custos forem iguais se comportará como busca em extensão.
Não se importa com o número de passos do caminho mais sim com seu custo total
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca em Profundidade
Expande até o nó mais profundo
Quando um nó não tem filhos ele é removido (+Raza)
LIFO: Os últimos a serem expandidos serão os primeiros a serem removidos.
Pouco uso de memória: armazena único caminho + nós não expandidos.
Não é completa: Pode fazer a escolha errada e ficar paralisada ao desce um caminho muito longo (infinito).
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca em Profundidade
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca em Profundidade LIMITADA (Caso especial)
Resolve o problema de arvores ilimitadas na busca de profundidade.
Limite de profundidade L
Incompleta: se o objetivo mais raso estiver além do limite.
Esse incompletude é amenizada quando se conhece o problema.
Complexidade de tempo e espaço são - > O(bL)
Resultados: Falha | Valor de corte | Solução
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca em Aprofundamento Interativo em Profundidade
Resolve o problema do objetivo está abaixo do limite de profundidade.
Aumenta gradualmente o limite L até encontrar o objetivo.
Acontece quando o L alcança a profundidade do nó objetivo mais raso.
Combina os benefícios da busca em profundidade(pouca memória) com a busca em extensão(completo).
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca em Aprofundamento Interativo em Profundidade
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca Bidirecional
Buscas simultâneas :
Uma direta a partir do estado inicialOutra Inversa a partir do objetivo
Para quando as duas se encontram
A complexidade é da ordem de
O(bd/2+bd/2) que é muito menor que O(bd)
Onde b = quantidade de sucessoresd = profundidade
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca Bidirecional
É implementada fazendo com que cada parte verifique cada nó antes de ser expandido.
Verifica se o nó está na borda da outra arvore. (Solução)
Exemplo: Problema profundidade 6
A solução do pior caso será quando tiverem expandido todos os nós, exceto 1, da profundidade d=3.
Resolução de Problemas por meio de Busca
Estratégias de busca sem informação (Cega)Busca Bidirecional
A
Dificuldade em alguns casos: Fazer a busca inversa, achar os predecessores. EX: Xadrez – estado objetivo “xaque-mate”
Em casos como o quebra cabeça de 8 partes, a busca inversa é semelhante a direta.
Resolução de Problemas por meio de Busca
Comparação entre estratégias de busca sem informação (Cega)
Resolução de Problemas por meio de Busca
Como Evitar estados repetitivos
Não desperdiçar tempo e recursos expandindo estados que já foram expandidos.
Alguns problemas são susceptíveis a estados repetitivos como o quebra cabeça de blocos deslizantes e localização de rotas.
Evita ciclos – arvore de busca infinitas
Solução: Podar estados repetitivos tornando a arvore finita
Comparar o nó a ser expandidos com os já expandidos
Resolução de Problemas por meio de Busca
Como Evitar estados repetitivos
Algoritmos que esquecem sua história estão condenadas a repeti-la
Se o algoritmo se lembrar de todo estado que já visitou ele será visualizado como uma exploração direta do grafo de espaço de estados.
Resolução de Problemas por meio de Busca
Como Evitar estados repetitivos
Algoritmo da BUSCA-EM-GRAFO
lista fechadaEstrutura de dados inclusa em algoritmo BUSCA-EM-ARVORE.
Lista abertaA borda de nós não expandidos.
Em problema com muitos estados repetido é mais eficiente que o busca em arvore.
Requisitos de tamanho e espaço proporcionalmente ao espaço de estados. O(bd)
Resolução de Problemas por meio de Busca
Busca com informações parciais
• Utilizado para solucionar problemas, quando o conhecimento dos estados ou ações são incompletos.
• Este método se divide em três tipos distinto de solução.
Resolução de Problemas por meio de Busca
Busca com informações parciais
1 – PROBLEMAS SEM SENSORES
• Também chamado de problema de conformidade,consiste em:
• Se o agente não tem nenhum sensor, então elepoderá estar em um dentre vários estados iniciaispossíveis, e cada ação poderá portanto levar a umdentre vários estados sucessores possíveis
Resolução de Problemas por meio de Busca
Busca com informações parciais
1 – PROBLEMAS SEM SENSORES
Resolução de Problemas por meio de Busca
Busca com informações parciais
1 – PROBLEMAS SEM SENSORES
O agente pode fazer a repressão do mundo para o estado desejado, mesmo que ele não saiba onde começar, ou seja, o agente deve raciocinar sobre conjuntos de estados que poderia alcançar, em vez de estados isolados.
Resolução de Problemas por meio de Busca
Busca com informações parciais
1 – PROBLEMAS SEM SENSORES
• Seu funcionamento é da seguinte forma:
• O estado inicial é um estado de crença, e cada ação faz omapeamento de um estado de crença para outro estadode crença.
• Um caminho agora conecta diversos estados de crença euma solução é um caminho que leva a um estado decrença, cujos membros são todos estados objetivos.
Resolução de Problemas por meio de Busca
Busca com informações parciais
2 – PROBLEMA DE CONTINGÊNCIA
• Se o ambiente for parcialmente observável ou se as açõesforem incertas, as percepções do agente fornecerãonovas informações depois de cada ação. Cada percepçãopossível define uma contingência que deve ser planejada.
• Um problema é chamado adverso se a incerteza écausada pelas ações de outro agente.
Resolução de Problemas por meio de Busca
Busca com informações parciais
2 – PROBLEMA DE CONTINGÊNCIA
• Para solucionar esse problema, usamos frequentemente aforma de uma árvore, onde cada ramo poderá seracessado.
• Às vezes permitem soluções puramente sequências.
Resolução de Problemas por meio de Busca
Busca com informações parciais
3 – PROBLEMA DE EXPLORAÇÃO
• Quando os estados e as ações do ambiente sãodesconhecidos, o agente deve atuar para descobri-los. Osproblemas de exploração podem ser visualizados comoum caso extremo de problemas de contingência
Resolução de Problemas por meio de Busca
BUSCA HEURÍSTICA (ESTRATÉGIAS DE BUSCA COM INFORMAÇÕES)
• Uma estratégia de busca com informação, queutiliza o conhecimento específico do problemapara encontrar soluções de modo mais eficiente.
• É uma busca cega com algum guia ou orientação.
Resolução de Problemas por meio de Busca com informação e Exploração
Resolução de Problemas por meio de Busca com informação e Exploração
OS PROBLEMAS DE IA EMPREGAM HEURÍSTICAS,BASICAMENTE, EM DUAS SITUAÇÕES:
• Um problema pode não ter uma solução exatapor causa das ambiguidades inerentes na suaformulação ou pela disponibilidade dos dados.Exemplos: Diagnóstico médico, Sistemas devisão.
• Um problema pode ter uma solução exata, maso custo computacional para encontrá-la podeser proibitivo.Exemplo: Jogo de xadrez.
Resolução de Problemas por meio de Busca com informação e Exploração
As heurísticas podem falhar.
• Uma heurística é apenas uma conjecturainformada sobre o próximo passo a ser tomadona solução de um problema;
• A heurística é baseada na experiência e naintuição;
• Uma heurística pode levar um algoritmo debusca a uma solução subótima ou, inclusive,levá-lo a não conseguir encontrar uma solução;
Resolução de Problemas por meio de Busca com informação e Exploração
Porção do espaço de estados para o jogo-da-velha
9
8
7
.
.
.
N0 de caminhos = 9!
Resolução de Problemas por meio de Busca com informação e Exploração
Os primeiros três níveis do espaço de estados do jogo-da-velha reduzidos por simetria.
3 movimentos iniciais:
•Para o canto
•Para o centro de um lado
•Para o centro da grade
A heurística do “maior número de vitórias” aplicada aosprimeiros filhos do jogo-da-velha.
Resolução de Problemas por meio de Busca com informação e Exploração
Resolução de Problemas por meio de Busca com informação e Exploração
Espaço de estados reduzido heuristicamente para o jogo-da-velha.
BUSCA HEURÍSTICA (ESTRATÉGIAS DE BUSCA COM INFORMAÇÕES)
• Busca pela melhor escolha é uma especialização doalgoritmo geral busca em árvore ou busca emgrafo, no qual um nó é selecionado para expansãocom base em uma função de avaliação f(n).
• Busca do melhor caminho - pode ser derivada deum refinamento da busca em largura.Refina este princípio calculando uma estimativaheurística para cada candidato e escolhe paraexpansão o melhor candidato de acordo com estaestimativa.
• Busca em largura - sempre escolhe para expansãoos menores caminhos-candidatos (isto é, os nósextremos menos profundos da busca).
Resolução de Problemas por meio de Busca com informação e Exploração
BUSCA GULOSA PELA MELHOR ESCOLHA
• Tenta expandir o nó mais próximo à meta, nasuposição de que isso provavelmente levará a umasolução rápida.
• Desse modo, ela avalia nós usando apenas afunção heurística: f(n) = h(n).
• Exemplo: encontrar a melhor rota (rota mais curta)de uma cidade a outra, num mapa.
• h(n) = distância em linha reta entre as cidades e acidade-meta.
Resolução de Problemas por meio de Busca com informação e Exploração
Resolução de Problemas por meio de Busca com informação e Exploração
Exemplo: Localização de rotas na Romênia, usando a heurística de distância em linha reta (hDLR) Objetivo: Bucharest(Bucareste)
176
100
Um mapa rodoviário simplificado de parte da Romênia .
Resolução de Problemas por meio de Busca com informação e Exploração
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
BUSCA A*: MINIMIZANDO O CUSTO TOTAL
• Avalia nós combinando g(n), o custo para alcançar cadanó, e h(n), o custo para ir do nó até o objetivo: f(n) = g(n)+ h(n).
• Tendo em vista que g(n) fornece o custo de caminhodesde o nó inicial até o nó n, e que h(n) é o custoestimado do caminho de custo mais baixo desde n até oobjetivo, temos: f(n) = custo estimado da solução decusto mais baixo passando por n.
Resolução de Problemas por meio de Busca com informação e Exploração
Resolução de Problemas por meio de Busca com informação e Exploração
Exemplo: Localização de rotas na Romênia, usando a Busca A*
Objetivo: Bucharest (Bucareste)
Um mapa rodoviário simplificado de parte da Romênia.
176
100
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Exemplo – Passo a Passo ...
Estágios em uma busca A* por Bucareste. Os nós estão rotulados f = g + h. Os valores de h são distâncias em linha reta para Bucareste.
Desempenho do A*
• A análise do caráter ótimo de A* é direta se for usada com BUSCA-EM-ÁRVORE: A* será ótima se h(n) for uma heurística admissível.
• Consequência mais importante da consistência (também chamada monotonicidade) é: A* usando BUSCA-EM-GRAFO é ótima se h(n) é consistente.
BUSCA A*: MINIMIZANDO O CUSTO TOTAL
Resolução de Problemas por meio de Busca com informação e Exploração
CONSISTÊNCIA
• Uma heurística h(n) é consistente se, para todo nón e todo sucessor n, de n gerado por qualquer açãoa, o custo estimado de alcançar o objetivo a partirde n não é maior que o custo do passo de sechegar a n’ somando ao custo estimado dealcançar o objetivo a partir de n’.
Resolução de Problemas por meio de Busca com informação e Exploração
BUSCA HEURÍSTICA LIMITADA PELA MEMÓRIA
• O caminho mais simples para reduzir requisitos dememória de A* é adaptar a ideia deaprofundamento iterativo ao contexto de buscaheurística, resultando no algoritmo A* deaprofundamento iterativo (AIA*)
Resolução de Problemas por meio de Busca com informação e Exploração
FUNÇÕES HEURÍSTICAS
Resolução de Problemas por meio de Busca com informação e Exploração
Como escolher uma boa função heurística h?
• h depende de cada problema particular.
• h deve ser admissível
– não superestimar o custo real da solução
• Exemplo: jogo dos 8 números
– um número pode mover-se de A para B se A é adjacente a B e B está vazio
– busca exaustiva:
• solução média em 22 passos
• fator de ramificação médio: 3
• ≈ 322 estados possíveis
• ≈ 9!/2 (controlando os estados repetidos)
Resolução de Problemas por meio de Busca com informação e Exploração
• Função h2 (n)
– o espaço de estados gerado é menor ⇒
– o algoritmo acha mais rapidamente a solução.
• Exemplo:
Muito Obrigado!