Please enable JavaScript.
Coggle requires JavaScript to display documents.
Inteligencia computacional (Resolução de Problemas por meio de Buscas…
Inteligencia computacional
Definição
Em meados de 1956, em Dartmouth College (USA), o termo IA
foi cunhado por Marvin Minsky, Nathaniel Rochester e Claude
Shannon.
• Durante a conferência, foi apresentado um programa de
raciocínio lógico “capaz de pensar” para demonstrar teoremas
matemáticos (SANTOS, 2014).
Embora não haja um definição precisa do que é inteligência, a
Inteligência Artificial pode ser definida como sendo uma área
de estudo dentro de ciência da computação que busca
sistematizar tarefas intelectuais.
IA não é “substituta” da inteligência humana, mas sim uma
ferramenta de apoio.
Teste de Turing
Como não havia (e ainda não há) uma definição precisa do que é
inteligência, Alan Turing propôs em 1950, um teste para verificar
se uma máquina é inteligente.
O teste consiste de três indivíduos separados (sem contato direto)
conversando por meio de uma interface (computador, por
exemplo):
Um interrogador humano que irá questionar
Um computador (interrogado).
Outro humano (interrogado).
O objetivo do computador é enganar o interrogador (humano)
de modo que ele não consiga saber quem é humano ou a
máquina.
Se ele conseguir enganar o interrogador, então ele é
inteligente; do contrário, não.
hipóteses (fraca x forte)
IA fraca: as máquinas podem agir com inteligência?
Problema na definição da pergunta: o que é agir com
inteligência?
Teste de Turing: inteligente como um ser humano.
IA forte: as máquinas podem realmente pensar?
Uma máquina que passa pelo Teste de Turing estaria realmente
pensando? Ou estaria somente simulando o pensamento?
Máquinas com consciência.
• ciência dos próprios estados mentais e ações.
estado mental: capacidade de atenção, memória, fala,
linguagem, orientação temporal, espacial e pessoal
histórico
1943 – Warren McCulloch e Walter Pitts
Modelo de neurônio artificial
IA Conexionista: modelagem da inteligência através da
simulação dos componentes do cérebro.
Neurônios e suas conexões
Redes Neurais
Teste de Turing proposto em 1950
“Computing Machineri and Intelligence
1956 – Allen Newell e Herbert Simon
• LT: Logic Theorist; GPS: Solucionador geral de problemas
IA Simbólica: qualquer sistema (máquina ou humano) que exibe
inteligência opera manipulando estruturas de dados compostas
por símbolos.
1956 – John McCarthy, Marvin Minsky et al
Surgimento da área de “Inteligência Artificial”.
1958 – John McCarthy
Linguagem LISP – manipulação simbólica
Pós 1980 – IA como ciência
IA passa a se fundamentar mais em teorias existentes, do que
em “teorias mirabolantes”
Fundamentos matemáticas e computacionais
Pós 1995 – Agentes inteligentes
Construção de agentes: percepção + raciocínio + ação
Resolução de Problemas por meio de Buscas
Um algoritmo de busca é uma sequência de passos, partindo de um
estado inicial até encontrar um objetivo (meta).
É um agente (tudo que é capaz de perceber por meio de
sensores e agir por meio de atuadores) orientado a
objetivo.
É uma abordagem genérica para resolver problemas.
Não é necessário conhecer todos as possibilidades do
problema
Para sair de Ibirama e ir até Florianópolis não é necessário
conhecer todas as possíveis rotas, mas sim as rotas diretamente
conectadas a Ibirama
Formulação do problema
A modelagem de um problema é constituída de quatro itens:
Estado inicial: ex: tabuleiro 8puzzle desorganizado.
Função sucessor S(x): retorna um conjunto de estados, dado um
estado inicial.
Possíveis jogadas do 8puzzle a partir de um estado.
Teste de objetivo: verifica se o estado atual é o estado objetivo (meta)
Se o tabuleiro do 8puzzle está ordenado, então é meta.
Custo do caminho: é a soma das distâncias, números de ações
executadas, etc.
Profundidade da árvore.
Solução é a sequência de transições de estados a partir do
estado inicial até o estado meta.
Solução ótima é a que possui menor custo.
Os quatro principais critérios para escolha são:
COMPLETUDE
• o algoritmo sempre encontra a solução quando ela existir?
OTIMALIDADE
• o algoritmo sempre encontra a solução ótima (custo)?
COMPLEXIDADE DE TEMPO
• quanto tempo o algoritmo leva para encontrar a solução?
COMPLEXIDADE DE MEMÓRIA
• quanta memória é necessária para executar a busca?
Geralmente são medidos em grafo (quantidade de arestas e
vértices) ou árvore de estados.
Os parâmetros usados para o cálculo da complexidade
Fator de ramificação (b)
Número máximo de sucessores que qualquer estado pode
gerar.
Profundidade (d)
Profundidade da árvore
Comprimento máximo (m)
Comprimento máximo de qualquer caminho no espaço de
estados.
Buscas Cegas
Busca em largura
• Expande o nó raiz, expande os sucessores do raiz (na mesma
profundidade da árvore); até encontrar o meta (se houver).
Estrutura de dados utilizada é do tipo FIFO (fila).
É completo (se houver solução)
É ótimo se o custo for o número de transições de estados :
A complexidade de tempo e espaço é alta, pois é necessário
armazenar todos os estados.
Busca em profundidade
O pseudocódigo é muito semelhante ao da busca em largura,
as principais diferenças são:
Estrutura de dados utilizada é uma pilha (LIFO).
Recebe como parâmetro a profundidade máxima da árvore
Gera os sucessores em profundidade, ou seja, não expande
todos os nós de um mesmo nível (profundidade).
Se a profundidade m for menor do que p aonde se encontra o
meta, então não é completa.
Armazena menos nós em memória do que a busca em
largura (apenas os estados do caminho atual).
É mais rápida (processamento) do que em largura, pois
armazena menos nós.
Busca em profundidade
iterativa
É a busca em profundidade que fica incrementando a
profundidade da árvore até que o estado meta seja encontrado
(se houver).
Em relação a busca em largura e profundidade ela é melhor,
pois gera menos sucessores para cada nível de profundidade
da árvore e sempre vai encontrar a solução (se houver).
Buscas Heurísticas
Alguns problemas podem ser insolúveis utilizando apenas
métodos de buscas cegas.
Usando métodos de buscas cegas para resolver o problema
8puzzle com nível de dificuldade médio e difícil, não é possível
encontrar solução.
As buscas heurísticas são uma extensão das buscas cegas
com o uso de informações (estimativa de custo de um dado
estado até o meta).
Em virtude disso, são mais eficientes do que as buscas cegas
Adotando uma boa heurística é possível resolver o problema
8puzzle para estados com nível de dificuldade médio e difícil.
A ideia básica (geração de sucessores) básica permanece a
mesma com um adicional da função de avaliação.
Essa função irá determinar, com base na heurística adotada,
qual será o próximo sucessor a ser escolhido
A heurística é uma estimativa de custo h(n) de um dado estado
até um estado meta.
No problema 8puzze, uma das heurísticas adotadas foi o
número de peças fora do lugar em relação ao estado meta.
Heurísticas são ditas admissíveis quando nunca
superestimam o custo real.
Para elaborar heurísticas iniciais, recomenda-se fazer o uso
de versões relaxadas do problema
heurística mencionada anteriormente desconsidera o fato
de que não é possível mover as peças que não estão
adjacentes, por exemplo
Uma heurística h2 domina outra heurística h1 quando h2 > h1.
Nesse caso ela é melhor.
Para o problema 8puzzle a distância de Manhattan é melhor do
que somente contar as peças fora do lugar
Busca Gulosa
A busca gulosa utiliza como função de avaliação apenas a
heurística.
Assim, ela sempre vai escolher o sucessor com melhor
heurística (mais próxima de zero, que é o meta)
Se não houver poda, ela não é completa
Não é ótima, pois não olha o custo passado. Tenta alcançar o
somente olhando para frente.
Busca A*
A única diferença entre a A* e a gulosa é a função de
avaliação.
A função de avaliação utilizada pelo A* leva em
consideração o custo passado.
Em virtude disso, ela é completa e é ótima, se a heurística
for admissível
Buscas locais
Em alguns problemas não é necessário armazenar o
caminho, isto é, o caminho é irrelevante.
Basta que o algoritmo de busca atinja o estado meta
Esses algoritmos são conhecidos como algoritmos de busca
local.
Seu funcionamento ocorre com baste apenas no nó atual, não
mantendo registro dos anteriores.
Podem encontrar soluções razoáveis em espaços grandes
ou infinitos – contínuos –
Subida da Montanha
Premissa básica é “escalar” sempre – melhor sucessor.
Não é ótima, pois se finalizar antes, as soluções não serão
ótimas.
A função objetivo que define o próximo sucessor
Portanto, o próximo estado é gerado a partir dos sucessores
do atual.
O sucessor é escolhido por intermédio da função objetivo f(n)
f(n)=custo exato (se conhecido)
f(n)=h(n)-heuristica
O principal problema dessa abordagem é que nem sempre o
melhor resultado é o esperado.
máximos/mínimos locais:
pico/vale mais alto/baixo que os sucessores porém ainda
menor/maior do que o estado meta
platôs
melhores sucessores com f(n) igual ao f(atual)
não consegue evoluir
O busca subida na montanha não é completa, pois pode
terminar antes de encontrar a solução (vale/pico) .
Por outro lado, ao comparar sua complexidade de tempo e de
memória com A*, ela é melhor, pois não armazena em
memória os estados anteriores, e por isso é mais eficiente.
Subida da Montanha com
Reinicio Aleatório
É uma extensão da subida na montanha, ao encontrar um
máximo/mínimo local ou platô, a busca é reiniciada com um
estado aleatório.
Vantagem em relação a anterior é que, se o problema for
solúvel, eventualmente a solução será encontrada, portanto, é
completo.
A complexidade de tempo e de processamento continuam as
mesmas em relação a subida da montanha sem reinicio
aleatório.
Definição de Problema de Satisfação por
Restrição (PSR)
Nem sempre é uma boa estratégia usar métodos de buscas
tradicionais para resolver problemas.
n-queen
problema de coloração de mapas
problemas de quebra-cabeça
Uma das característica comum entre esses problemas são as
restrições, que são fatores determinantes dos valores que os
estados podem assumir.
Esse tipo de problema é classificado como problema de
satisfação de restrições (PSR)
Um PSR consiste em:
Conjunto de variáveis que assume valores respeitando o
domínio
Conjunto de restrições que determinam os valores que
as variáveis podem assumir.
Estado é definido por uma atribuição de valores a alguma
ou todas as variáveis.
Não pode violar as restrições.
Função de avaliação especifica o quão bom é um
conjunto de atribuições de valores a uma determinada
variável
Grafo de Restrições
Representa um CSP binário
Cada restrição relaciona duas variáveis
Nodos são variáveis e os arcos são restrições
Características das restrições
As restrições podem ser classificadas como:
Unárias (restringe valor de uma variável): Tasmania deve ser
verde.
Binárias (restringe valores de duas variáveis): Problema das nrainhas.
N-árias: palavras cruzadas.
Domínio das variáveis
O domínio da variável pode ser discreto ou contínuo
Discreto: valores finitos dentro de um intervalo.
• Ex: quantidade de funcionários em uma empresa.
Contínuo: valores infinitos dentro de um intervalo.
Ex: altura de uma pessoa
Elaboração de heurísticas para PSR
Uma maneira de encontrar boas heurísticas para PSR pode-se
observar algumas das questões.
Qual é a ordem para testar as variáveis?
Ordem crescente do tamanho do domínio da variável
(heurística de variável mais restrita ou valores
remanescentes mínimos).
valores
remanescentes mínimos (VRM)
Também conhecida como heurística variável mais restrita.
Seleciona a variável que pode assumir o menor número de valores é
legais, ou a que descarta o menor número possível para as variáveis
restantes.
Seleciona a variável que tem mais chances de causar falha, com a
finalidade de podar a árvore.
Supondo que inicialmente seja atribuído WA = vermelho, NT =
verdade.
• Aplicando a heurística mencionada, a próxima região a ser colorida,
seria SA = azul, pois o único valor válido para ela é azul.
Usar a heurística de grau (variável envolvida no maior número
de restrições em variáveis não atribuídas).
de grau
O problema da VRM é que ela não ajuda a determinar qual será a
primeira cor a ser escolhida
A heurística de grau resolve esse problema: tenta reduzir o fator de
ramificação da árvore, selecionando a variável que está envolvida no
maior número de restrições.
SA é a variável com mais restrições.
1 more item...
Em que ordem testar os valores?
Valores que restringem menos as atribuições futuras
(heurística de valor menos restritivos)
valor
menos restritivo
Heurística utilizada para selecionar o valor a ser atribuído a
variável.
Seleciona os valores que excluem o menor número possível
de escolha para os vizinhos
Suponha que WA = vermelho e NT = verde, a próxima variável
a ser atribuída seria Q, e o restante está em branco. Qual valor
atribuir a ela?
Escolhas válidas:
Q = vermelho
Q = verde
Escolher azul iria invalidar as cores para AS. Nesse caso, a melhor
escolha seria azul (restringe menos o domínio das outras variáveis).
Backtracking
Alguns PSR podem ser resolvidos com algoritmos de buscas
vistos até agora (profundidade, largura).
Um dos problemas ao tomar esse tipo de abordagem, é que
esses algoritmos ignoram um fator importante: a
comutatividade.
Um problema comutativo é dito comutativo se a ordem as ações
tomadas não alteram o resultado final
Ex: levar um canibal e um missionário até uma borda é a
mesma coisa que levar um missionário e um canibal até a
borda.
O backtracking – busca por retrocesso – é um dos algoritmos
mais básicos para PSR, que resolve o problema da
comutatividade.
A ideia básica do backtracking – busca por retrocesso – é
efetuar uma busca em profundidade para uma variável de
cada vez (ignorando suas ordens de atribuições de valores).
Ex: no problema de coloração de mapa proposto, os primeiros
sucessores poderia ser WA = azul, WA = vermelho. Por outro lado,
não poderia ser WA = verde e SA = azul.
Se uma variável não possuir valores válidos a serem atribuídos,
então é efetuado o retrocesso (poda).