RESOLUÇÃO DE PROBLEMAS EM AI

Prévia do material em texto

- -1
INTELIGÊNCIA ARTIFICIAL APLICADA A 
JOGOS DIGITAIS
RESOLUÇÃO DE PROBLEMAS EM 
INTELIGÊNCIA ARTIFICIAL
- -2
Olá!
Nesta aula, você irá:
1. Definir e caracterizar problemas na área de Inteligência Artificial.
2. Estruturar e exemplificar problemas de acordo com a sua área de interesse.
Para solucionar problemas através de técnicas de Inteligência Artificial, vamos começar definindo de forma
precisa os elementos que constituem o problema e sua solução. Um problema pode ser definido, formalmente,
por quatro componentes:
Para explicar os componentes anteriores, vamos utilizar alguns problemas como exemplo, primeiro, um
problema bem simples:
João está na estação Central do metrô no Rio de Janeiro. Ele precisa ir para o Flamengo. Considere que João só
pode ser locomover de metrô.
Se conhecermos bem o metrô do Rio, ou tivermos seu mapa, saberemos que somente um dos três sentidos nos
leva corretamente para o Flamengo, mas vamos fingir que não sabemos.
- Zona Norte. Próxima estação: Universidade X
- Zona Sul. Próxima estação: Pres. Vargas
- Pavuna. Próxima estação: Cidade Nova
- -3
Definindo o problema, através dos seus componentes:
Estado inicial: Ponto de partida do problema, no nosso caso poderia ser descrito como Em(Central). 
- -4
Uma descrição das ações possíveis que estão disponíveis. Dado um estado particular x,Função sucessor: 
SUCESSOR(x) retorna um conjunto de pares ordenados <ação, sucessor>, em que cada ação é uma das ações
válidas no estado x e cada sucessor é um estado que pode ser alcançado a partir de x aplicando-se a ação. No
nosso caso, se utilizarmos, por exemplo, o estado Em(Central), a função sucessor retomaria:
<Ir(Zona Norte), Em(Praça Onze)>, <Ir(Zona Sul), Em(Pres. Vargas)>, cir(Pavuna), Em(Cidade Nova)> ;
Juntos, o estado inicial e a função sucessor (quando aplicada a todos os estados) definem implicitamente o
espaço de estados do problema: o conjunto de todos estados possíveis a partir do estado inicial.
Determina se um estado é um estado objetivo. Às vezes, podem haver vários estadosTeste de objetivo: 
objetivos possíveis, no nosso caso o estado objetivo é único, Em(Flamengo). Às vezes, também pode ser que o
estado objetivo não seja necessariamente um conjunto de um ou mais estados explicitamente enumerados, pode
ser uma propriedade abstrata. Por exemplo, no xadrez, o objetivo é alcançar um estado chamado "xeque-mate",
onde o rei do oponente está sob ataque e não consegue escapar.
- -5
Atribui um custo numérico a cada caminho. Um caminho no espaço de estados é umaCusto do caminho: 
sequência de estados conectados por uma sequência de ações, por exemplo: <Ir(Zona Sul), Em(Pres. Vargas), <Ir
(Zona Sul), Em(Uruguaiana)>, <Ir(Zona Sul), Em(Carioca)>, <Ir(Zona Sul), Em(Cinelândia)>
O custo poderia ser a soma das distâncias em Km entre uma estação e outra.
- -6
Atenção
Os elementos precedentes definem um problema e podem ser reunidos em uma única estrutura de dados, que é
fornecida como entrada para um algoritmo de resolução de problemas.
Solução do Problema:
A solução do problema é um caminho desde o estado inicial até um estado objetivo. A qualidade da solução é
medida pela função de custo do caminho, uma solução ótima tem o menor custo de caminho dentre todas as
soluções possíveis.
A solução ótima para o problema do metrô seria:
<Ir(Zona Sul), Em(Pres. Vargas)>, <Ir(Zona Sul), Em(Uruguaiana)>, <Ir(Zona Sul), Em(Carioca)>, <Ir(Zona Sul),
Em(Cinelândia)>, <Ir(Zona Sul), Em(Glória)>, <Ir(Zona Sul), Em(Catete)>, <Ir(Zona Sul), Em(Largo do Machado)
>, <Ir(Zona Sul), Em(Flamengo)>.
Só para ilustrar, outra solução, que obviamente não seria ótima:
Ir(Zona Norte), Em(Praça Onze)>, <Ir(Zona Sul), Em(Central)>, <Ir(Zona Sul), Em(Pres. Vargas)>, <Ir(Zona Sul),
Em(Uruguaiana)>, <Ir(Zona Sul), Em(Carioca)>, <Ir(Zona Sul), Em(Cinelândia)>, <Ir(Zona Sul), Em(Glória)>, <Ir
(Zona Sul), Em(Catete)>, <Ir(Zona Sul), Em(Largo do Machado)>, <Ir(Zona Sul), Em(Flamengo)>.
Vamos agora a outro exemplo de problema mais interessante para nós, um jogo/desafio mental:
- -7
Você possui duas jarras de água, uma com capacidade de 4 litros e outra de 3 litros, ambas estão inicialmente
vazias. Como obter 2 litros de água na jarra de 4 litros? Você deve sempre encher ou esvaziar as jarras de forma
completa e pode transferir água de uma jarra para outra.
Para esse problema, tente definir o estado inicial, o teste de objetivo, todas as funções sucessor a partir do estado
inicial, e a solução ótima. Vamos representar cada estado por dois números, o primeiro é a quantidade de água
na jarra de 4 litros (x) e o segundo é a quantidade de água na jarra de 3 litros (y), assim: (x, y).
Depois compare com as respostas que seguem:
Estado inicial: (0,0)
Teste de objetivo: (2,0)
Função sucessor:
Estado inicial (0,0)
<Enche jarra de 4, (4,0)>, <Enche jarra de 3, (0,3)>
Estado (4,0)
<Esvazia jarra de 4, (0,0)>, <Enche jarra de 3, (4,3)>, <Transfere4para3, (1,3)>
Estado (0,3)
<Esvazia jarra de 3, (0,0)>, <Enche jarra de 4, (4,3)>, <Transfere3para4, (3,0)>
Estado (4,3) <Esvazia jarra de 4, (0,3)>, <Esvazia jarra de 3, (4,0)>
Estado (1,3)
<Esvazia jarra de 4, (0,3)>, <Esvazia jarra de 3, (1,0)>, <Enche jarra de 4, (4,3)>, <Transfere3para4, (4,0)>
Estado (3,0)
<Esvazia jarra de 4, (0,0)>, <Enche jarra de 4, (4,0)>, <Enche jarra de 3, (3,3)>, <Transfere4para3, (0,3)>
Estado (1,0)
- -8
<Esvazia jarra de 4, (0,0)>, <Enche jarra de 4, (4,0)>, <Enche jarra de 3, (1,3)>, <Transfere4para3, (0,1)>
Estado (3,3)
<Esvazia jarra de 4, (0,3)>, <Esvazia jarra de 3, (3,0)>, <Enche jarra de 4, (4,3)>,
<Transfere3para4, (4,2)>
Estado (0,1)
< Esvazia jarra de 3, (0,0)>, <Enche jarra de 3, (0,3)>, < Enche jarra de 4, (4,1)>,
<Transfere3para4, (1,0)>
Estado (4,1)
<Esvazia jarra de 4, (0,1)>, < Esvazia jarra de 3, (4,0)>, <Enche jarra de 3, (4,3)>, <Transfere4para3, (2,3)>
Estado (4,2)
<Esvazia jarra de 4, (0,2)>, < Esvazia jarra de 3, (4,0)>, <Enche jarra de 3, (4,3)>, <Transfere4para3, (3,3)>
Estado (0,2)
<Esvazia jarra de 3, (0,0)>, < Enche jarra de 4, (4,2)>, <Enche jarra de 3, (0,3)>, <Transfere3para4, (2,0)> Estado
objetivo!
Solução do Problema
<Enche jarra de 3, (0,3)>,
<Transfere3para4, (3,0)>,
<Enche jarra de 3, (3,3)>,
<Transfere3para4, (4,2)>,
<Esvazia jarra de 4, (0,2)>,
<Transfere3para4, (2,0)>
- -9
Exemplos de Problemas
Miniproblemas:
• Servem para ilustrar, exercitar ou comparar métodos de solução de problemas.
• Geralmente, possuem descrição concisa e exata.
Problemas no mundo real
• Problemas cujas soluções preocupam as pessoas e são importantes para a humanidade.
• Tendem a não apresentar uma descrição consensual.
O que vem na próxima aula
Na próxima aula, você estudará sobre os assuntos seguintes:
• O conceito de busca em espaço de estados.
• Os tipos e subtipos de buscas (cegas e heurísticas).
• Os métodos de busca.
•
•
•
•
Saiba mais
Para saber mais sobre os tópicos estudados nesta aula, pesquise na internet sites, vídeos e
artigos relacionados ao conteúdo visto. Se ainda tiver alguma dúvida, fale com seu professor
online utilizando os recursos disponíveis no ambiente de aprendizagem.
Conheça o site de jogos de lógica plastelina.net ( ).www.plastelina.net
•
•
•
http://www.plastelina.net/
- -10
CONCLUSÃO
Nesta aula, você:
• Conheceu o problema das jarras, o problema das 8 rainhas, o problema do quebra-cabeças de 8 peças, os 
problemas de roteamento e de tour, o problema do caixeiro viajante, os problemas relacionados a jogos 
de computador, o problema da pesquisa na internet e outros problemas relacionados à indústria.
• Aprendeu que um problema deve ser dividido em 4 componentes: estado inicial, função sucessor, teste 
de objetivo e custo do caminho; aprendeu também que para IA os problemas se dividem em mini-
problemas e problemas do mundo real.
• Percebeu que os problemas necessitam de um tratamento preciso e detalhado para se alcançar uma 
determinada solução.
• Compreendeu quepodem existir várias soluções para um problema e que a solução ótima é aquela que 
tem o caminho de menor custo.
• Analisou o problema das jarras, identificando os componentes do problema.
•
•
•
•
•
	Olá!
	
	O que vem na próxima aula
	CONCLUSÃO