PROVA DE IA

Pasta de Buscas

Busca IDA:
 Utilizada para encontrar soluções em espaços de estados.
 É um algoritmo completo. Sempre encontra uma solução, caso exista.
 É ideal para problemas em que a estrutura de espaço não é conhecida
ou o espaço de estados é muito grande para ser completamente
explorado.
Definições:
É uma combinação entre a busca iterativa (IDA) e o algoritmo A*.
- Utiliza uma heurística para estimar os custos dos caminhos e realiza uma
busca iterativa aumentando progressivamente o limite de profundidade a cada
iteração até encontrar uma solução.
- Estima o custo para alcançar a solução a partir de um determinado estado. E
utiliza uma função que estima o custo do caminho até o estado atual.
 Essa estimativa deve ser admissível, ou seja, nunca superestimar o
custo real do caminho.
 Essas estimativas são combinadas para determinar a ordem de
expansão dos nós.

Estrutura:
É necessário utilizar uma estrutura de dados como uma pilha ou fila para
armazenar os estados visitados.
A complexidade da IDA depende da heurística e da quantidade de estados
possíveis. Pode ser mais eficiente que a busca A*
 A busca IDA mantém apenas o caminho atual na memória durante a
busca, consumindo menos espaço que outras buscas.
Desvantagens:
- Caso a heurística usada na busca for inconsistente (superestima o custo),
pode levar ao mau desempenho, visto que irá explorar nós desnecessários.
- Em alguns casos a IDA pode repetir a expansão de nós. Isso ocorre
principalmente em situações em que o nó objetivo possui múltiplos caminhos
para alcançá-lo.
Exemplo IDA:
Para implementar a IDA, estabelecemos um limite de profundidade para a
busca. Em cada iteração, chamamos uma função de busca em profundidade
limitada, que explora os nós até atingir o limite. Se encontrar o objetivo, termina
e busca e retorna o resultado, senão, incrementa o limite e repete o processo.

BUSCA EM PROFUNDIDADE ITERATIVA

 Não utiliza uma função heurística para estimar o custo.
 Realiza uma busca em profundidade sucessiva com limites crescentes
até encontrar uma solução.
 A busca IDA é uma extensão sua.
São utilizados para explorar espaços de solução e permitem a descoberta de
soluções para problemas complexos, por meio de uma pilha para controlar a
ordem de expansão dos nós. Diferente da busca de profundidade, a limitada
possui um limite máximo de profundidade atribuído pelo usuário que o impede
de continuar infinitamente em um ramo sem encontrar uma solução ou
retroceder para explorar outros.

BUSCA EM PROFUNDIDADE
 Explora o espaço de estados a partir de um estado inicial, avançando o
mais profundamente possível antes de retroceder e explorar outras
opções.

 A partir do nó inicial, o algoritmo segue pela primeira aresta encontrada

e continua explorando o caminho até encontrar um nó sem arestas não
visitadas. Faz o backup e explora outros caminhos não visitados.
Sua funcionalidade consiste em explorar ao máximo possível um caminho,
voltar e depois fazer a mesma coisa em outros. Para que seja possível, é
utilizado a estrutura em pilha em LIFO (último a entrar, primeiro a sair).
Para implementar um algoritmo de busca é necessário criar uma função de
busca com o grafo ou a estrutura, um nó que dará início e a lista dos nós
que já foram visitados. O nó inicial deverá ser colocado na lista para que
não haja uma exploração repetida e para que nenhum nó fique de fora.
Caso seja um algoritmo de profundidade em ciclos, é possível que entre em
um ciclo infinito e seja necessário tomar medidas adicionais para controlar
os ciclos.
 BUSCA EM LARGURA
 Explora o espaço de estados de forma ampla, expandindo todos os nós
vizinhos antes de avançar para os nós adjacentes.

 Explora os nós vizinhos antes de continuar a expansão. Visita todos os

nós a uma distância fixa do ponto inicial antes de se mover para próxima
camada de nós.
A busca em largura é um algoritmo que realiza a exploração em grafos a
partir da raiz, seguindo para os vizinhos e voltar para encontrar o próximo,
como por exemplo faríamos para encontrar a rota mais curta entre duas
cidades. Com ele é possível encontrar rotas mais curtas ou ver se um grafo
está todo conectado. Para explorar, deve-se começar em uma fila vazia e
inserir uma raiz e definir como visitada, seguindo pelos vértices para os
vizinhos e marcando os que foram ou não visitados, até que a fila fique
vazia. A complexidade do BFS se dá pela relação entre o número de
vértices e o número de arestas.

BUSCA DE CUSTO UNIFORME

 Foca em encontrar o caminho com o menor custo. Atribui um custo a

cada ação realizada e seleciona a ação com o menor custo para se
expandir.

BUSCA GULOSA ou Best-First:

 A expansão é direcionada pela heurística de cada nó. Encontra a

solução que esteja mais próxima do objetivo, mesmo não sendo a
melhor solução em termos de custo total.
 Baseada na estrutura de dados, fila de prioridade, na qual os nós são
inseridos de acordo com o valor que a função de heurística atribui a
eles. Os nós com a melhor estimativa de se aproximar da solução
desejada, são os primeiros a serem explorados.
Na busca gulosa, a fila é iniciada com o nó inicial e enquanto a fila não estiver
vazia, o nó de maior prioridade é removido. Caso o nó removido for o objetivo,
volte a fila, caso contrário, adicione os filhos ao novo nó expandido. A
prioridade é definida pelas informações da heurística. Uma de suas
características é reduzir a complexidade da busca, pois tem uma expansão
eficiente (dependendo da heurística) e rápida ao se comparar com outras
buscas.
- A Best-First tem uma complexidade do tempo linear em relação ao número
total de estados gerados. Enquanto a busca A* tem uma complexidade de
tempo exponencial em relação à profundidade da solução ótima.

BUSCA em A*
 Combina a busca gulosa e a busca de custo uniforme. Considera a
distância do nó atual ao nó objetivo, bem como o custo total até o
momento para chegar ao nó atual.
 A busca A* utiliza uma fila de prioridade, onde os nós são priorizados de
acordo com o valor da função de avaliação. Sempre que um nó é
expandido, seus nós vizinhos são adicionados à fila de prioridade,
respeitando a ordem de prioridade definida pela função de avaliação.
Seu desempenho depende dos fatores da heurística e do grafo, quanto
mais precisa a sua heurística, menos nós serão criados, tornando a
heurística mais eficaz.
- A quantidade de estados gerados durante a bsuca A* depende do número
de vezes que um estado já visitado é expandido novamente.
- Se a heurística foi admissível, que nunca superestima o custo real, a
busca é completa e ótima.
Características:
Completeness: Sempre encontrará uma solução se ela existir, mas
dependendo da heurística pode não ser a ótima.
Optimality: Quando é admissível, garante que encontre o caminho mais
curto, sendo ótima.
Eficiência: O desempenho depende da qualidade da heurística e da
complexidade do grafo. Caso use uma mais precisa, pode reduzir o número
de nós expandidos e sendo mais eficiente.
Espaço de memória: Armazena a árvore de busca, visto que mantém uma
lista de nós abertos e uma de nós visitados.

ALGORITMO RBFS (Recursive Best-First Search)

  Método utilizado para a realização de buscas em espaço de estados.
 Pode não encontrar a melhor solução em todos os casos.
- Mantém uma lista de nós ainda não explorados, ordenada em ordem
decrescente com base na heurística orientada pela quantidade de soluções
encontradas.
- Durante a busca, o algoritmo expande o nó com o maior valor heurístico na
lista de abertos. Caso um nó não tenha filhos não explorados, o algoritmo
retorna para seu pai e escolhe outro caminho.
Busca recursiva: Permite que o algoritmo explore várias soluções em paralelo,
escolhendo sempre o caminho mais promissor.
 Através de chamadas recursivas, exploramos diferentes alternativa de
trajeto até encontrarmos o melhor percurso que satisfaça todas as
restrições e minimize o tempo total de viagem.

HEURÍSTICAS:
A heurística é uma técnica utilizada para dar direcionamento nos algoritmos
de busca para solucionar certos problemas, tornando-a mais rápida e prática.
Sendo também uma função que estima o custo para alcançar a solução
desejada a partir de um determinado estado. Na busca recursiva Best-First,
as heurísticas são usadas para determinar qual nó deve ser explorado a
seguir.
 São avaliadas para cada possível movimento a partir do estado atual e o
nó com a menor estimativa de custo é escolhido para explorar primeiro.
Exemplos de heurísticas:
Heurística da distância Euclidiana:
 Geralmente usada em problemas de busca em um espaço de estados
com coordenadas. Estima a distância euclidiana direta entre o estado
atual e o estado objetivo, considerando as coordenadas desses pontos.
Heurística de distância de Manhattan:
 Calcula a soma das distancias horizontais e verticais desses dos pontos.
Geralmente usada em problemas de busca em grade, como um labirinto.
Heurística de contagem de peças fora do lugar:
 Geralmente usada em problemas de busca em que o estado objetivo é
um estado final pré-definido. Conta o número de peças que estão fora
do lugar em relação ao estado objetivo, fornecendo uma estimativa da
qualidade do estado atual.
busca recursiva best first:
Esse tipo de algoritmo de busca, procura as melhores soluções em problemas
mais complexos dando prioridades em caminhos com maior chance de ser o
caminho correto.
Por meio da heurística, o nó que tem a maior chance de prosseguir é
expandido, caso o nó não tenha filhos inexplorados, a heurística volta para
calcular outros caminhos. Para isso, deve ser definido um ponto inicial e final
para a heurística fazer os cálculos e é necessário criar uma função de
avaliação que será responsável por atribuir um valor para cada movimento até
o objetivo final. Na expansão de nós, cada possível passo, que seriam os nós
criados a partir do ponto principal, são calculados pela função de avaliação e
para calcular um novo caminho, conforme os passos são dados, os valores dos
custos são atualizados. Esse tipo de busca também tem um critério de parada
que não termina até chegar em seu objetivo final ou até passar por todos os
nós disponíveis, caso todos os caminhos já tenham sido testados, mas não
chegou ao objetivo final, significa que esse problema não tenha uma solução.

ESPAÇO DE ESTADO
 É uma representação formal de um problema. Consiste em um conjunto
de estados possíveis, ações que podem ser executadas em cada estado
e uma função de transição que especifica como o estado evolui quando
uma ação é realizada.
 É um modelo que descreve todas as possíveis configurações de um
problema ou sistema. Composto por um conjunto de estados e
transições, essa são determinadas por ações ou operações que
podemos executar em um determinado estado para chegar a outro
estado.
Representação:
- Conjunto de estados: Um espaço que contém todos os possíveis estados do
sistema ou problema em questão.
 Modelagem de estados: Identifica os elementos necessários para
descrever cada estado do problema. Exemplo: Utilização de uma matriz
3x3 para representar um tabuleiro de jogo da velha, com cada posição
podendo ser vazia, ocupada pelo jogador X ou pelo jogador O.

- Conjunto de operadores: Ações ou operações que podem ser aplicadas aos

estados do sistema para produzir novos estados.
  Modelagem de ações: Determinar as ações possíveis para cada estado,
incluindo suas pré-condições e efeitos. Exemplo: Cada ação
corresponde a colocar uma marca (X ou O) em uma posição vazia do
tabuleiro.

Função de transição: Determina a evolução do estado quando uma ação é

executada. Exemplo: Atualização do tabuleiro após cada jogada.

Representações de um espaço de estados:

Grafos: Onde os estados são representados como nós e as transições como
arestas.
Tabelas: Onde são representados os estados e as transições. Cada linha
representa um estado e suas colunas representam as possíveis ações.
Matrizes: Em alguns problemas, é possível representar o espaço de estados
como uma matriz. Onde as linhas e as colunas representam os estados e as
células representam as transições.
 Estratégias de busca: Busca em largura, profundidade e Heurística;
 PROVA DE IA

PASTA CONHECIMENTOS:

Sistemas Baseados em Conhecimento

O que é SBC? É uma área de IA que envolve o desenvolvimento de sistemas

que podem tomar decisões e resolver problemas complexos a partir do uso de
conhecimento humano.

 O conhecimento pode ser adquirido de especialistas humanos ou

extraído de base de dados e literatura especializada.
Um SBC é capaz de tomar decisões, resolver problemas e fornecer
recomendações com base em seu conhecimento específico.

Arquitetura de um SBC: S 1° motor de inferência – Coração do SBC. Realiza o

raciocínio lógico e a tomada de decisão. Aplica as regras de inferência como
encadeamento progressivo ou regressivo para chegar a conclusões ou
recomendações.
2° Base de conhecimento – Onde informações importantes são armazenadas.
Contém as regras, fatos, exemplos e casos utilizados pelo SBC para tomar
decisões.
3° Interface de usuário – Meio pelo qual os usuários interagem com o SBC.
Imput/output. Pode ser gráfica ou textual (comando).
4° Mecanismo de aquisição de conhecimento – Permite que o SBC aprenda e
incorpore novos conhecimentos. Permite que o SBC evolua e se mantenha
atualizado.
5° Mecanismo de explicação – Fornece uma explicação para as decisões ou
recomendações feitas pelo SBC.
6° Mecanismo de conhecimento incerto – Utilizado quando o conhecimento
disponível é impreciso ou incerto. Permite que o SBC tome decisões mesmo
quando a informação é incompleta ou ambígua.
Sistemas especialistas e convencionais: Para lidar com incertezas, utilizam
técnicas como a lógica fuzzy e a teoria dos conjuntos.
Linguagem de representação de conhecimento: Sistemas convencionais –
Utilizam JAVA ou C++ (Dados armazenados em variáveis) para representar
conhecimento. Sistemas especialistas – Utilizam uma linguagem de produção
(regras If-Then, com condições definidas e ações)
Conhecimento: Sistemas convencionais – Fornecido pelos programadores.
Sistemas especialistas – Fornecido por especialistas com regras e exemplos.
Enquanto os sistemas convencionais seguem um conjunto de regras
codificadas, os SBC são capazes de aprender e aplicar conhecimentos
específicos de forma mais adaptativa e inteligente.

Características do SBC:

 Captura e representação do conhecimento;

 Inferência e raciocínio;
 Aprendizado e adaptação.

Benefícios do SBC:

 Consistência e padronização;
 Velocidade e eficiência;
 Redução de erros;
 Preservação e disseminação do conhecimento.

Um dos benefícios da integração de técnicas de aprendizado de máquina em

SBC é a capacidade de lidar com dados não estruturados e a adaptação do
sistema.

Limitações do SBC

 Limitação na obtenção e representação do conhecimento;

 Dificuldade na adaptação a mudanças;
 Interpretação subjetiva;
 Dependência de especialistas.
Fases do processo de desenvolvimento de um Sistema Especialista

 Software que simula a inteligência humana em um domínio específico.

 Identificação do problema;
 Análise de requisitos;
 Aquisição de conhecimento;
 Representação do conhecimento (De forma estruturada e lógica);
 Implementação;
 Teste e avaliação.

AULA IA.

Arvore de decisão da IA
 Recebe valores falsos e verdadeiros

HLM
 Geração de informações por seres humanos.
 Human Language Model

IA – Definição, Representação e raciocínio

Inferência é o processo de tirar conclusões lógicas a partir de premissas e
regras.
Na IA, o conhecimento é a informação e compreensão que um sistema
computacional possui sobre o mundo, assim, é importante para realizar tarefas
complexas.
Diagnosticar doenças:

 Um sistema IA para um médico precisa ter conhecimento de anatomia,

doenças etc.
Escrever textos:

 O sistema precisa de conhecimento em gramática, síntese, vocabulário

e estilos.
Jogar jogos:

 Jogar Xadrez, regras, peças e criatividade.

O conhecimento pode ser adquirido de diversas maneiras.
Aprendizado automático:

 Análise de grande conjunto de dados, para novo conhecimento.

Engenharia de conhecimento:

 Especialistas podem codificar manualmente redes semânticas, lógica

formal, frames etc.
Interações com ambiente:

 Receber feedback, explorar o mundo físico.

Representação de conhecimento:

 Processo de codificar o conhecimento de forma que possa ser entendida

e processada pelo computador.

Formas:
Rede semânticas:

 Conjunto de objetos relacionados entre eles (cachorro, gato) e executar

ações.

Lógica formal:
 Inferências e conjuntos de regras. “Todos os mamíferos são
vertebrados”.
 ∀ x (mamíferos) (x) —> Vertebrados (x))

Frame:
 Categorias e estereótipos.

Raciocínio da IA
 Usa o conhecimento para chegar em novas conclusões.

Raciocínio Dedutivo:
  Começa com uma premissa geral e usa a lógica para chegar a uma
conclusão específica.
 Geral: Todos os humanos são mortais
 Específica: Aristóteles é humano.
 Dedução: Aristóteles é mortal.

Raciocínio Indutivo:
 Começa com específica e depois generaliza para chegar à conclusão.

 "Se todos os cisnes que vimos até agora são brancos, então todos os
cisnes são brancos."

Raciocínio Abdutivo:
 Começa com uma observação e usa a hipótese para explicar.

 "Observamos que o céu está escuro, então podemos abduzir

(deduzir) que está nublado."

Exercício:
Um sistema de IA para jogar xadrez precisa decidir qual o melhor movimento a
ser feito em uma determinada posição. Qual o tipo de raciocínio o sistema de
IA pode usar para tomar essa decisão?
R: Dedutivo e Abdutivo (Geral - Observação – Específico)