Please enable JavaScript.
Coggle requires JavaScript to display documents.
Aula 03 - Resolução de Problemas de Busca, Definições importantes,…
Aula 03 - Resolução de Problemas de Busca
Definições importantes
Objetivo
Propriedade abstrata (em intenção)
ex: condição de xeque-mate no xadrez
Conjunto de estados finais do problema (em extensão)
ex: estar em Recife
Solução
"Não é o estado final. É o caminho percorrido"
Caminho (sequência de ações) que leva do estado inicial a um estado final (objetivo)
Custo da busca
Custo Total
=
+
Custo do caminho
corresponde a
execução da solução
Pode depender (de acordo com o tipo de problema) da escolha do usuário
ex: custo em jogo dos 8 números é sempre unitário (igual a 1 movimento/turno)
ex: custo do caminho em uma viagem depende do usuário (pode ser o número de cidades visitadas, km rodados, tempo de viagem, etc)
Função custo de caminho diferente gera solução diferente
Custo de busca
corresponde a
busca da solução
custo computacional
tempo e memória
Quando possui espaço de estados grande
conflito entre determinar
a
melhor solução
em termos de custo do caminho
em termos de custo do computacional
Árvore de busca
obs: a árvore não existe de fato
é apenas uma representação para facilitar a compreensão do problema
Onde os estados são nós e as operações são arcos
ajuda a entender melhor o funcionamento do algoritmo
"A
execução
do algoritmo de busca pode ser representada como uma árvore de busca"
Espaço de estados
Conjunto de todos os estados alcançáveis
inclui estado inicial e estado(s) final(is)
Critérios de avaliação das Estratégias de Busca
Exemplos de métodos
Busca exaustiva (cega)
Busca heurística (informada)
Completude
a estratégia
sempre encontra uma solução
quando existe alguma?
Qualidade
(optimality)
a estratégia encontra
a melhor solução
quando existem diferentes soluções?
ex: solução de menor custo de caminho
Custo do tempo
quanto tempo
gasta para encontrar a 1ª solução?
Custo de memória
quanta memória
é necessária para realizar a busca?
Um problema de busca em IA pode ser definido em termos de
Um estado inicial
Um conjunto de ações (ou operadores)
que permite passar de um estado para outro
Um teste de término
Verifica se um dado estado é o
objetivo
Objetivo = um ou mais estados finais
Custo de caminho
Função que associa um custo a cada caminho possível
Cada
ação
tem um
custo associado
Solucionando o problema
Formulação do problema e do objetivo
Processo manual
"Quais os estados e ações a considerar?"
"Qual é (e como representar) o objetivo?"
Busca
Processo automático
Processo que gera/analisa sequências de ações para alcançar um objetivo
Execução
Processo que pode ser manual ou automático
Algoritmo de Geração e Teste
Informações importantes
Esse é um algoritmo geral, todos os outros são instâncias desse algoritmo
Esse é um algoritmo para gerar árvores, não fazer o caminhamento
Fronteira
do espaço de estados
É uma estrutura de dados usada pelo algoritmo
Lista que contém nós (estados) que serão expandidos
ex: o nó inicial e os filhos dele
Cada nó é uma estrutura de dados que contém 4 componentes
o estado (configuração) correspondente ao nó
o caminho percorrido a partir do nó raiz (inicial)
a ação aplicada ao pai para gerar o nó
para evitar loops
ex: não deixar que o pai do nó também seja filho dele
o custo do nó desde a raiz
g(n)
Inicialmente a
fronteira
contém apenas o nós inicial do problema
Os algoritmos com que estamos trabalhando trabalham de forma offline
ou seja, não realizam busca em tempo real
simulam ações (não as executam de fato)
ex: simula ida a determinada cidade
Algoritmo
Selecionar
o primeiro nó (estado) da fronteira do espaço de estados
SE a fronteira está vazia, o algoritmo termina com
falha
Testar
se o nó selecionado é um estado final (objetivo)
SE sim, então retorna o nó (a busca termina com
sucesso
)
Gerar
um novo conjunto de estados aplicando ações ao estado selecionado
Inserir
os nós gerados (na etapa 3) na
fronteira
é executado de acordo com a estratégia de busca usada
volta para o passo 1