Inteligencia Artificial

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL
João Luís Tavares da Silva
2INTELIGÊNCIA ARTIFICIAL
SUMÁRIO Esta é uma obra coletiva organizada por iniciativa e direção do CENTRO SUPERIOR 
DE TECNOLOGIA TECBRASIL LTDA – 
Faculdades Ftec que, na forma do art. 5º, 
VIII, h, da Lei nº 9.610/98, a publica sob sua 
marca e detém os direitos de exploração 
comercial e todos os demais previstos em 
contrato. É proibida a reprodução parcial 
ou integral sem autorização expressa e 
escrita.
CENTRO UNIVERSITÁRIO UNIFTEC
Rua Gustavo Ramos Sehbe n.º 107. 
Caxias do Sul/ RS 
REITOR
Claudino José Meneguzzi Júnior
PRÓ-REITORA ACADÊMICA
Débora Frizzo
PRÓ-REITOR ADMINISTRATIVO
Altair Ruzzarin
DIRETORA DE EDUCAÇÃO A DISTÂNCIA (EAD)
Lígia Futterleib
Desenvolvido pela equipe de Criações para o 
ensino a distância (CREAD)
Coordenadora e Designer Instrucional 
Sabrina Maciel
Diagramação, Ilustração e Alteração de Imagem
Julia Oliveira
Revisora
Luana dos Reis
SISTEMAS DE INFORMAÇÃO INTELIGENTES 3
Conceitos Básicos 5
Dado-Informação-Conhecimento 6
Representação do conhecimento 9
Estados e busca heurística 10
Lógica 10
Regras de produção 12
Frames e scripts 13
Redes semânticas 14
Computação Evolutiva 17
Síntese 18
RESOLUÇÃO DE PROBLEMAS 20
Formulação do problema 23
Técnicas de resolução 25
Busca competitiva 40
Síntese 47
SISTEMAS ESPECIALISTAS 50
Síntese 63
ALGORITMOS GENÉTICOS 66
Princípios básicos 69
Síntese 81
APRENDIZAGEM AUTOMÁTICA 83
Aprendizagem supervisionada 86
Redes neurais artificiais 93
Síntese 108
AGENTES INTELIGENTES E SISTEMAS MULTIAGENTES 111
Síntese 147
Referências 150
3INTELIGÊNCIA ARTIFICIAL
SISTEMAS DE 
INFORMAÇÃO 
INTELIGENTES
Esta disciplina tem como objetivo introduzir 
os alunos no contexto de Inteligência Artificial, 
compreendendo seus conceitos teóricos e 
aplicando-os a problemas reais.
4INTELIGÊNCIA ARTIFICIAL
Iniciamos pela apreciação de Russel e Norvig sobre a In-
teligência Artificial:
“We call ourselves Homo sapiens – man the wise – because our 
intelligence is so important to us. For thousands of years, we have 
tried to understand how we think; that is, how a mere handful 
of matter can perceive, understand, predict, and manipulate a 
world far larger and more complicated than itself. The field of 
artificial intelligence, or AI, goes further still: it attempts not 
just to understand but also to build intelligent entities” (Russel 
& Norvig, 2004).
Se você ainda não entendeu esta apreciação, copie e cole 
o parágrafo no Google Translator para ter uma ideia de uma 
pequena parte da IA em ação.
Agora, podemos recuar um pouco no tempo e descobrir 
que construir entidades inteligentes não é um campo novo na 
história da humanidade. Por exemplo, o brilhante matemático 
e astrônomo Gerbert d’Aurillac (945-1003), que subiu ao trono 
papal como Silvestre II em 999 D.C., constrói um oráculo na 
forma de uma cabeça mecânica em bronze, provável ancestral 
dos modernos robôs (LaGrandeur, 2013).
Depois que Blaise Pascal cria a Pascalene, primeira má-
quina de calcular em 1642, e Leibniz inclui a multiplicação e 
a divisão (1673), surgem brinquedos mecânicos simulando a 
vida através dos chamados autômatos, como por exemplo, o 
pato mecânico de Jacques de Vaucanson (1738). 
Independente da tecnologia, a curiosidade sobre o fun-
cionamento da vida sempre motivou o homem a buscar uma 
forma de imitação da criação. O advento eletrônico estimula 
o conhecimento humano e os computadores já surgem com 
perspectivas inteligentes. Embora os primeiros computadores, 
a válvula eletrônica, tenham surgido na década de 1940; já em 
1950 Marvin Misky e Deam Edmonds, alunos de Harvard, 
constroem o primeiro computador de rede neural, o SNARC 
https://translate.google.com.br/?hl=pt-BR
5INTELIGÊNCIA ARTIFICIAL
(Stochastic Neural Analog Reinforcement 
Calculator) e no mesmo ano, Alan Turing 
publica seu seminal artigo na “Compu-
tational Machinery and Intelligence”, 
onde ele questiona sobre a inteligência 
dos computadores e apresenta seu famoso 
Teste de Turing (Russel & Norvig, 2004).
Conceitos Básicos
 Definir inteligência é uma tarefa 
árdua e a Medicina, Psicologia e Ciências 
Cognitivas têm desvelado total esforço e 
energia ao longo de décadas nesta tarefa. 
Desde a ideia da faculdade ou capacidade 
de aprender e compreender, culminan-
do nas inteligências múltiplas (Howard 
Gardner) e coletivas (Émile Durkheim, 
Pierre Lévy, entre outros).
Russel e Norvig definem a Inteligên-
cia Artificial segundo duas tendências 
básicas: baseado no pensamento e raciocí-
nio onde o objetivo é desenvolver sistemas 
que pensam como seres humanos ou que 
pensam racionalmente; e, baseado no 
comportamento, onde o objetivo é de-
senvolver sistemas que atuam como seres 
humanos ou que atuam racionalmente.
 Neste sentido, os conceitos variam 
conforme a abordagem adotada. Na Ta-
bela 1, a dimensão horizontal representa 
a atividade de Pensar e Agir, enquanto 
a dimensão vertical determina se estas 
atividades são imitação dos seres huma-
nos ou uma metáfora de comportamento 
racional.
Tabela 1. Abordagens conceituais sobre 
Inteligência Artificial
Como seres humanos Racionalmente
Pe
ns
an
do
“Um esforço novo e interessante 
para fazer os computadores 
pensarem (…) máquinas com 
mentes, no sentido total e literal” 
(Haugeland, 1985).
“A 'automatização' de atividades 
que associamos ao pensamento 
humano, atividades como a 
tomada de decisões, a resolução 
de problemas, o aprendizado…” 
(Bellman, 1978).
“Inteligência Artificial é o estudo 
das faculdades mentais através do 
uso de modelos computacionais” 
(Charniak e McDermott, 1985).
“É o estudo das computações 
que tornam possível perceber, 
raciocinar e agir” (Winston, 1992).
“Uma máquina é inteligente 
se ela é capaz de solucionar 
uma classe de problemas que 
requerem inteligência para serem 
solucionados por seres humanos” 
(McCarthy e Hayes, 1987). 
Ag
in
do
“É o estudo de como fazer os 
computadores realizarem tarefas 
em que, no momento, as pessoas 
são melhores” (Rich & Night, 
1990).
“A arte de criar máquinas que 
executam funções que exigem 
inteligência quando executadas 
por pessoas” (Kurzweil, 1990).
“Inteligência Artificial é a parte 
da ciência da computação que 
compreende o projeto de sistemas 
computacionais que exibam 
características associadas, quando 
presentes no comportamento 
humano, à inteligência” (Barr & 
Feigenbaum, 1981).
6INTELIGÊNCIA ARTIFICIAL
Para que os métodos de Inteligência Artificial possam ser 
utilizados para resolver um determinado problema, é impor-
tante considerar:
• a necessidade de que a solução para o problema em questão 
requeira a incorporação de conhecimento especializado sobre 
o domínio da aplicação;
• qual o tipo de conhecimento envolvido e quais as principais 
ideias a serem consideradas;
• a identificação das fontes do conhecimento a serem utilizadas 
e, como essas fontes podem ser acessadas;
• qual a melhor forma de representar o conhecimento e como 
realizar o processo de aquisição e representação deste co-
nhecimento.
Em geral, problemas cuja soluções demandem uma sequên-
cia de passos rígidos e bem definidos não são adequados para 
serem resolvidos com recursos de IA. Nestes casos deve-se 
pensar na possibilidade de codificação da solução, utilizando 
alguma técnica tradicional e alguma linguagem de programação 
orientada a objetos ou mesmo estruturada.
Dado-Informação-Conhecimento
Quais são os aspectos conceituais relacionados?
Dado:
 » isolado;
 » independente do contexto;
 » fatos (símbolo, texto, figura).
 » Armazenados em sistemas de processamento de dados:
• databases;
• arquivos (imagens, texto).
Informação:
 » dado combinado;
 » dado em contexto;
 » dado estruturado, (exemplo: por tópico);
 » catálogo (diretórios).
Conhecimento:
 » individual (humano);
 » informação baseada em interpretação, cognição, experiência.
7INTELIGÊNCIA ARTIFICIAL
Dado 
É um conjunto de fatos distintos e objetivos, relativos aos 
eventos (Davenport e Prusak, 1998). Uma sequênciade letras e 
números, figuras, palavras sem contexto (Wiig, 1993). Valores 
obtidos de sensores (Siemieniuch et al., 1999). Resumindo, um 
conjunto de elementos brutos, sem significado, desvinculado 
da realidade, de interpretação e contexto.
Informação
É um elemento cuja existência independe de atividades 
interpretativas, de entidades subjetivas (Dretske, 1981). São 
dados com significado, relevância e propósito (Drucker, 1999) 
ou contextualizados para fornecer uma solução em situações 
de decisão. Também se definem como dados aos quais foram 
atribuídos um contexto (Wiig,1993; Siemieniuch er al.,1999).
Conhecimento
O conhecimento inclui, mas não está limitado, às descri-
ções, hipóteses, conceitos, teorias, princípios e procedimentos 
que são úteis ou verdadeiros. O conhecimento distingue-se da 
mera informação porque está associado a uma intencionalida-
de. Consiste em verdades e crenças, perspectivas e conceitos, 
julgamentos e expectativas, metodologias e know-how. O co-
nhecimento é acumulado, organizado, integrado e armazenado 
para aplicações específicas (Wiig, 1993).
Sabedoria
Se estendermos a noção contextual do próprio conheci-
mento, atinge-se um estado da mente humana caracterizada 
por uma profunda compreensão e insight. A “sabedoria” é, 
frequentemente, mas não necessariamente, acompanhada por 
um extensivo conhecimento formal.
8INTELIGÊNCIA ARTIFICIAL
Dado
Informação
Conhecimento
Sabedoria
Aprendizagem de situações históricas para 
previsão de catástrofes ou soluções.
Usado conforme o contexto:
• especulador no mercado futuro de frutas;
• município atingido por uma cheia;
• companhia de distribuição de energia elétrica;
• operadores de agências de viagem.
Uma tempestade (fora de época) atingiu o 
estado de Pernambuco.
100 ml de água
Tabela 2. Pirâmide da hierarquia de representação
9INTELIGÊNCIA ARTIFICIAL
Representação do conhecimento
Computadores conhecem apenas a linguagem binária. A 
comunicação com os usuários é constantemente traduzida por 
compiladores. Como um artefato com vocabulários e linguagem 
tão reduzidos pode compreender o funcionamento do mundo?
Para que uma entidade “artificial” consiga determinar 
as consequências de um ato pelo pensamento ao invés de sua 
realização, é preciso substituir o objeto ou fenômeno real por 
uma representação adequada.
Portanto, a Representação de Conhecimento (RC) nada 
mais é do que uma aplicação da disciplina de Linguagens 
Formais para expressar de forma eficiente os conhecimentos 
de especialistas para serem acessados por usuários de um sis-
tema inteligente. É um conjunto de combinações sintáticas e 
semânticas que nos possibilitam descrever uma determinada 
aplicação. A representação sintática define os símbolos que po-
dem ser usados na representação do conhecimento e as maneiras 
como estes símbolos podem ser conseguidos. A representação 
semântica, por outro lado, determina qual significado está 
incorporado naqueles símbolos representados pela sintaxe.
Qualquer que seja a forma de representação do conheci-
mento, esta deve dispor de algum mecanismo computacional 
que possa processar o conhecimento representado. Quais são 
os principais mecanismos de representação do conhecimento 
para máquinas artificiais?
• Estados e busca heurística.
• Lógica.
• Regras de produção.
• Frames e scripts.
• Redes semânticas.
• Computação evolutiva.
• Redes neurais artificiais.
10INTELIGÊNCIA ARTIFICIAL
Estados e busca heurística
A representação por estados de busca constrói estrutura 
de grafos onde o conhecimento específico do problema está 
na escolha do próximo nó a ser expandido. Uma função de 
avaliação estima o custo do caminho do nó atual até o objetivo 
(conhecida como heurística). A partir da estrutura construída, 
algoritmos percorrem o grafo usando várias técnicas de cami-
nhamento, exemplificado na Figura 1.
Figura 1: Exemplo de árvore de busca simples
QUAL É O MELHOR PERCURSO
ITU --> UBA
I
C
S
S
S
U
130km
80km
180km
180km
150km
230km
160km
100km
90km
100km
Lógica
A lógica matemática é usada para representar o conhe-
cimento através de sentenças. Estas sentenças seguem regras 
sintáticas e semânticas específicas a cada corpo de dedução. 
Uma lógica define o significado destas sentenças. A se-
mântica determina a “verdade” de cada sentença (lembram de 
Platão?) relativo a um mundo possível. Por exemplo, a semân-
tica para a aritmética especifica que a sentença “x + y = 4” é 
verdadeira no mundo em que x=2 e y=2, mas é falsa em outro 
mundo, onde x=1 e y=1 (Russel & Norvig, 2004). Assim, cada 
sentença deve ser verdadeira ou falsa em cada mundo possível.
Existem vários tipos de lógicas utilizadas para realizar 
deduções automáticas. Na lógica de predicados de primeira 
ordem, as proposições são formadas por predicados, argumen-
tos, quantificadores e variáveis. A lógica de primeira ordem é 
de grande importância para a representação do conhecimento 
11INTELIGÊNCIA ARTIFICIAL
e tem sido o instrumento mais utilizado para a formalização 
do conhecimento em IA.
Assim, o conhecimento é expresso na forma de sentenças 
que são provadas na forma de teoremas. Por exemplo, para 
provar o teorema “herbívoro(zebra)”, a partir das premissas:
• animal(zebra);
• vegetal(grama);
• come (zebra, grama);
Basta criar uma Regra de Inferência semântica que a teste 
em algum mundo possível (dados pelos três fatos acima):
• xy[animal(x) AND come (x, y) AND vegetal(y)  herbív
Na lógica, a manipulação de símbolos representando as 
entidades, relações, eventos de domínio de aplicação deve ser 
um processo de construção plausível (sound) de novas sentenças 
a partir de outras sentenças, conforme esquema na Figura 2 
(Russel & Norvig, 2004).
Figura 2: Exemplo da tradução entre entidades no mundo real 
com sua representação simbólica
12INTELIGÊNCIA ARTIFICIAL
Regras de produção
A tomada de decisão humana pode também ser moldada 
por meio de regras de condição do tipo SE-ENTÃO. As regras 
expressam relacionamentos lógicos e equivalentes de definições 
para simular o raciocínio humano. Um exemplo simples pode 
ser ilustrado pela afirmativa: 
• “SE está chovendo ENTÃO carregue uma sombrinha”.
Portanto, como comentado anteriormente, regras de pro-
dução são estruturas do seguinte tipo:
• SE <condições> ENTÃO <conclusões> FAÇA <ações>
Onde: SE é uma lista de condições a serem satisfeitas (an-
tecedente); ENTÃO é uma lista de conclusões; e FAÇA são 
as ações a serem executadas. Conclusões e ações são chamadas 
de consequentes.
Em um processo de inferência, cada uma das condições 
da “lista de condições” deve ser verificada. Caso todas sejam 
satisfeitas, as conclusões serão consideradas verdadeiras e as 
ações serão executadas.
Exemplo da análise de restritivos em instituições bancárias:
 SE
 tipo-restritivo = Ação de busca
 E pessoa analisada = Jurídica 
 E quantidade de ocorrências < 2
 ENTÃO
 Análise Restritivo = Não Relevante
13INTELIGÊNCIA ARTIFICIAL
Frames e scripts
O modelo de frames e scripts foi introduzido em 1975 na 
representação do conhecimento por Marvin Minsk (Russel & 
Norvig, 2004).
Um frame é um agrupamento de conhecimentos relevan-
tes a uma coisa, um indivíduo, uma situação ou um conceito 
(Minsky, 1975). Os frames integram conhecimento declarativo 
sobre objetos, eventos e conhecimento procedimental sobre 
como recuperar informações ou calcular valores. Um frame 
possui um nome que identifica o conceito por ele definido e 
consiste de um conjunto de atributos, chamados slots. 
Cada slot possui um nome que o identifica e um conjunto 
de atributos que apresentam propriedades que dizem respeito 
ao tipo de valores e às restrições de número que podem ser 
associadas a cada atributo. Essas propriedades são chamadas 
facetas. Um exemplo de representação está ilustrado na Figura 3.
Figura 3: Exemplo de representação usando Frames 
(Luger,2013)
14INTELIGÊNCIA ARTIFICIAL
Redes semânticas
As Redessemânticas representam o conhecimento através 
de modelos formulados como grafos:
• os nodos representam objetos (conceitos, ou situações);
• os arcos representam relações binárias entre objetos.
Originalmente, os nodos representam substantivos, adjeti-
vos, pronomes e nomes próprios. Os arcos representam verbos 
transitivos e preposições.
Indivíduos podem ser representados com nodos anônimos 
e indicando a inclusão destes indivíduos em sua respectiva 
classe. Permitem hierarquias de hereditariedade, através da 
transitividade da relação “é_um” (is_a). A Figura 4 exibe a 
modelagem da memória humana, segundo (Quillian, 1968).
Figura 4: Modelagem da memória humana, segundo (Quillian, 
1968).
Concept-1
Concept-2
Concept-3
Concept-4
Concept-4
15INTELIGÊNCIA ARTIFICIAL
Exemplo de representação para três diferentes definições 
da palavra “Planta”:
• Estrutura viva que não é um animal, geralmente possui 
folhas e alimenta-se de água, terra ou ar.
• Aparato usado para qualquer processo na indústria.
• Colocar (uma semente, uma planta, etc.) na terra – Verbo 
“Plantar”.
Representação gráfica:
16INTELIGÊNCIA ARTIFICIAL
As redes semânticas se originam de estruturas Objeto-A-
tributo-Valor que determinam os valores de certos atributos 
de um objeto: 
Por exemplo: representação de um carro da marca Fiat de 
cor verde:
Algumas extensões possíveis para as redes semânticas são as:
Objeto Atributo Valor
possui
has
é
is
Carro Marca
Cor
Fiat
Verde
possui é
é
possui
a. Relações de classificação: relações “é_um” (is_a).
b. Relações de pertinência: relações “é_parte_de” (is_part).
17INTELIGÊNCIA ARTIFICIAL
Combinando as estruturas Objeto-Atributo-Valor com as 
relações de classificação e pertinência, as redes semânticas 
modelam relações que podem representar o conhecimento do 
mundo. A Figura ilustra um extrato de conceito para alguns 
personagens conhecidos de desenho animado.
Computação Evolutiva
A computação evolutiva é um método probabilístico de 
busca para resolução de problemas (otimização), inspirada na 
teoria da evolução. A representação do conhecimento é feita 
através de conjuntos atributo-valor e o raciocínio é indutivo, 
durante uma fase de treinamento, dedutivo ou abdutivo durante 
a fase de aplicação, utilização.
No paradigma evolutivo, a aquisição do conhecimento é 
feita através de aprendizagem e é baseada na Natureza, onde 
seres mais adaptados ao ambiente sobrevivem e suas caracte-
rísticas genéticas são herdadas. A formalização básica é que 
o indivíduo representa a solução de um problema e o sistema 
faz evoluir um conjunto de indivíduos mais adaptados através 
de funções de cruzamento; e mutação através de sucessivas 
gerações.
18INTELIGÊNCIA ARTIFICIAL
Síntese
Neste primeiro contato com a área de Inteligência artificial, resumiu-se algumas técnicas prin-
cipais de representação do conhecimento. Baseado nos conceitos apresentados aqui e nas premissas 
iniciais de que uma máquina é inteligente se ela é capaz de solucionar uma classe de problemas que 
requerem inteligência para serem solucionados por seres humanos, esta unidade focou na forma como 
uma representação do mundo deve ser definida para que um artefato artificial consiga perceber os 
elementos de resolução de um problema complexo.
Ao mesmo tempo, algumas áreas principais foram apresentadas, as quais serão aprofundadas nos 
próximos encontros, sem abranger todos os temas da Inteligência artificial.
19INTELIGÊNCIA ARTIFICIAL
Execícios
• Baseado no conteúdo acima, construa exemplos de dado-informação-conhecimento mais próximos do seu cotidiano.
• Diferencie atributos e elementos em cada exemplo dos enunciados que você criou, que possam caracterizar o conhecimento, 
diferenciando-o de dado ou informação.
• Pesquise a definição clássica de conhecimento de Platão. Esta definição de Platão pode ser formalizada como proposições na 
concepção de Aristóteles? Descubra...
20INTELIGÊNCIA ARTIFICIAL
RESOLUÇÃO DE 
PROBLEMAS
Resolver problemas é a habilidade básica de 
um ser inteligente. Veremos como encontrar 
uma sequência de ações que atinja um 
objetivo, quando nenhuma ação isolada é 
capaz de fazê-lo.
21INTELIGÊNCIA ARTIFICIAL
“Para poder sobreviver, um organismo necessita ou blin-
dar-se (como uma árvore ou um marisco) e ‘esperar pelo me-
lhor’, ou então desenvolver métodos para escapar de possíveis 
danos, indo para vizinhanças melhores. Se você escolher esta 
última opção, você se confrontará com o problema primordial 
que todo agente precisa continuamente resolver: e agora, o que 
devo fazer?” (Dennett, 1991).
De um modo informal, problemas estão relacionados à 
resolução de tarefas humanas, tais como:
• aquisição de informações (sentidos); 
• processamento de informações (raciocínio); e,
• ações no meio exterior (capacidade de agir).
Mais formalmente, um problema constitui-se em uma 
coleção de informações (conhecimento, regras, objetivos) que 
serão usadas para decidir o que fazer (solução). Apenas alguns 
exemplos ilustrativos de problemas típicos são:
Toy Problems:
Jogos de tabuleiros: 
• problema das n rainhas, 
• Damas, Xadrez, Go, Gamão, etc.
Jogos combinatórios: 
• n-puzzle ou Taquin;
• Criptoaritmética, Palavras cruzadas; 
• Canibais e missionários.
Problemas reais:
Cálculo de rotas:
• rotas em redes de computadores;
• sistemas de planejamento de viagens;
22INTELIGÊNCIA ARTIFICIAL
• planejamento de rotas de aviões;
• caixeiro viajante;
• jogos de computadores (rotas dos personagens).
Alocação (Scheduling):
• Salas de aula;
• máquinas industriais (job shop).
Projeto de VLSI:
• Cell layout;
• Channel routing.
Navegação de Robôs
Sequência de montagem.
São características da definição de problemas:
• Decomponível: pode ser dividido em subproblemas.
• Passos podem ser desfeitos ou ignorados: deve-se avaliar o 
custo de voltar atrás.
• Universo do problema é imprevisível: pode-se fazer uso da 
probabilidade.
• Solução absoluta ou relativa: existem problemas com solu-
ções ótimas.
• A base de conhecimento é consistente internamente: modelo 
da realidade confere com o objeto ou é uma aproximação, 
ou se apenas restringe a busca.
• Grande volume de conhecimento.
• Interage com o usuário.
23INTELIGÊNCIA ARTIFICIAL
A atividade de resolução de problemas consiste em decidir 
o que fazer, encontrando sequências de ações que levem a um 
objetivo (estado) desejado. Podemos planejar a resolução de 
qualquer problema seguindo as seguintes etapas:
• Formular o problema.
• Analisar o problema.
• Identificar o conhecimento necessário.
• Escolher a técnica de resolução mais adequada.
Formulação do problema
O primeiro passo para solucionar um problema é criar uma 
descrição formal manipulável para o problema. Esta descrição 
deve conter:
• definição de um espaço de estados possíveis;
• especificação dos estados iniciais;
• especificação de um conjunto de estados que sejam aceitáveis 
como soluções (estados objetivos);
• especificação do conjunto de ações disponíveis (regras ou 
operadores).
Mais formalmente em IA, um problema é definido em 
termos de:
• um espaço de estados possíveis, incluindo:
◊	um estado inicial;
◊	um (ou mais) estado finais = objetivo.
 » Exemplo: dirigir de Porto Alegre a Caxias do Sul.
 » Estado inicial: estar em Porto Alegre.
 » Estado final: estar em Caxias do Sul.
 » Espaço de estados: todas as cidades (x,y) da região.
24INTELIGÊNCIA ARTIFICIAL
◊	A descrição de um conjunto de ações disponíveis ao agente 
de resolução. Por exemplo, move(x,y), in(z), etc.
◊	Descrição do que cada ação faz, ou seja, um modelo de 
transição de estados, que permita passar de um estado a outro.
 » Exemplo: {in(x), move(x,y) = in(y)}, considerando 
que existe um caminho válido entre x e y.
◊	Um teste objetivo para se determinar se o estado atual 
pertence ao conjunto de estados finais.
◊	Uma função de utilidade, ou função de custo de caminho, 
que indique a qualidade do resultado.
Geralmente a solução de um problema é representadopelo cami-
nho que parte do estado inicial até um dos estados finais (objetivos).
Vamos a um exemplo mais completo, formulando o pro-
blema do Jogo de Xadrez:
• Espaço de estados: uma matriz 8x8 (numerados 1-8 e a-h) 
onde cada posição possui um símbolo representando uma peça.
• Operadores: regras de movimentação do xadrez, por exemplo, 
1.d4 d5 2. c4 c6 3. cxd5 cxd5 4. Cc3 Cc6 5. Cf3 Cf6; etc.
• Estado inicial: posição oficial de abertura do xadrez:
• Estado final: qualquer estado onde o rei adversário está sendo 
atacado e o adversário não possui movimentos válidos.
• Teste objetivo: um estado pertencente ao conjunto de estados 
finais, a partir dos operadores: 1-0, 0-1 ou ½-½.
• Custo do caminho: quantidade de posições examinadas, 
(Shannon, 1949):
• cerca de 35 movimentos legais (fator de ramificação);
• em média, cada jogador poderá realizar 40 movimentos;
• exame da árvore completa: ~3580 posições.
25INTELIGÊNCIA ARTIFICIAL
Técnicas de resolução
Em geral, o espaço de solução de um problema ou o espaço 
de estados é computacionalmente representado por meio de um 
grafo, onde cada vértice corresponde a um estado e as arestas 
indicam transições entre dois estados. A busca pela solução 
de um problema compreende a navegação pelos vértices do 
grafo de estados associados, a fim de encontrar o(s) vértice(s) 
cujo(s) estado(s) corresponde(m) a solução do problema. Por 
exemplo, a Figura 6 ilustra exemplos de grafos de busca para 
o problema da viagem.
Figura 6: Exemplo grafo para o problema da viagem
P
P
S
N
F
C
1
2
8
7
9
3
4
6
5
26INTELIGÊNCIA ARTIFICIAL
As principais técnicas de resolução deste tipo de problema 
podem ser enumeradas como:
• Busca: método de resolução de um problema sem abordagem 
direta, mas com uma estrutura disponível.
• Utilização do conhecimento: método de resolução de 
problemas complexos explorando a estrutura dos objetos 
envolvidos.
• Abstração: método que separa características e variações 
importantes de outras irrelevantes no processo de resolução.
O modo como as regras a serem aplicadas são selecionadas 
é crítico para a rapidez da resolução e para a possibilidade de 
encontrar alguma solução para o problema, portanto, uma 
estratégia de busca deve, sobretudo: 
• Causar movimento: movimentar o processo de resolução 
dentro do espaço de estados.
• Ser sistemática: explorar o espaço de estados de modo que 
evite repetir caminhos já percorridos e/ou desnecessários.
• Tratar o problema da possível explosão combinatória na 
exploração.
As estratégias de resolução se adequam ao tipo de pro-
blema, definido em função do conhecimento do sistema, que 
tradicionalmente estão subdivididos em:
• Problemas de estado único (single-state problems).
• Problemas de múltiplos estados (multiple-state problems).
• Problemas de contingência (contingence problems).
• Problemas exploratórios (exploratory problems).
27INTELIGÊNCIA ARTIFICIAL
Problemas de estado único
Este tipo de problema é caracterizado por ter um mundo 
observável (pelo menos o estado inicial), determinístico, estático 
e discreto. O conhecimento associado ao problema indica que o 
agente sempre sabe em que estado ele está (mundo totalmente 
acessível), conhece o efeito de cada uma de suas ações e sabe 
se localizar depois de uma sequência qualquer de ações. Cada 
ação leva a um único estado possível do espaço de estados 
definidos na formulação original do problema.
Vamos a um exemplo para o projeto de um robô aspirador 
de pó. Informalmente este problema é descrito através de um 
ambiente simples composto por duas salas A e B, onde um 
robô aspirador de pó precisa perceber se as salas estão limpas 
ou sujas e tem por objetivo manter as duas salas limpas. O robô 
também precisa se locomover entre as duas salas e executar a 
operação de aspiração como ilustrado na Figura 7.
Figura 7: Mundo simples do robô aspirador
Problemas de múltiplos estados
As características deste tipo de problema possuem um mundo 
parcialmente observável (estado inicial não observável), determinís-
tico, estático e discreto. Neste caso, o agente não tem conheci-
mento total do ambiente, não sabe seu estado inicial (percepção 
deficiente), mas sabe o efeito de suas ações. Ou, de outra forma, 
pode não conhecer o efeito das ações (execução deficiente), mas 
conhece seu estado inicial. Aqui podemos fazer um paralelo com 
28INTELIGÊNCIA ARTIFICIAL
a famosa lei de Murphy: o robô pode correr o risco de aspirar 
poeira existente e pode jogar poeira quando o quarto já estiver 
limpo. Em todo caso, a principal questão envolvendo a resolução 
deste tipo de problema é garantir que o agente consiga raciocinar 
sobre os conjuntos de estados aos quais ele pode chegar pelas 
ações. A técnica utilizada ainda é a busca no grafo de estados.
Problemas de contingência
Nos problemas do tipo contingência, o mundo é parcial-
mente observável (estado inicial não observável), não-deter-
minístico e dinâmico. Neste caso, o agente não conhece o 
ambiente inteiro ou não sabe o efeito das ações, por exemplo, 
o nosso robô enxerga apenas o quarto onde está. Não há uma 
sequência prévia de ações que garanta a solução do problema 
e, portanto, é necessário intercalar busca e execução em uma 
técnica tradicional de Planejamento. Neste contexto é neces-
sário construir uma árvore de ações, onde cada ramo lida com 
uma possível contingência.
Problemas exploratórios
Nos problemas exploratórios, além das características dos 
problemas de contingência, os estados e as ações do ambiente 
são desconhecidos. O agente deve atuar e descobri-los. Ele não 
possui conhecimento dos possíveis estados e não possui conhe-
cimento sobre o efeito de suas ações, por exemplo, um robô 
perdido em uma cidade desconhecida, sem mapa. Neste caso 
é necessário explorar o ambiente, descobrindo gradualmente 
o resultado das possíveis ações e os estados existentes. Se o 
agente “sobreviver”, terá aprendido um mapa do ambiente, que 
poderá ser reutilizado em problemas subsequentes, portanto, a 
única técnica possível de resolução destes problemas é através 
da aprendizagem.
29INTELIGÊNCIA ARTIFICIAL
Vamos voltar a formulação de problema para nos fixarmos 
melhor na importância da formulação. Teremos como exemplo, 
o jogo das n Rainhas (n-queens), considerando um total de 8 
rainhas no nosso tabuleiro. O objetivo deste problema é dispor 
8 rainhas no tabuleiro de forma que nenhuma delas possa se 
“atacar” mutuamente. Ou seja, não pode haver mais de uma 
rainha em uma mesma linha, coluna ou diagonal. Neste caso, 
somente o custo da busca conta, pois não existe custo de caminho.
Neste caso existem diferentes esta-
dos e operadores possíveis onde a escolha 
pode ter consequências boas ou ruins na 
complexidade da busca ou no tamanho 
do espaço de estados. Vamos considerar 
alguns exemplos de formulações possíveis 
e suas características:
• Formulação A:
• estados: qualquer disposição com n (n ≤ 8) rainhas;
• estado inicial: nenhuma rainha no tabuleiro;
• operadores: adicionar uma rainha a qualquer quadrado livre. Nes-
te caso tem-se 648 possibilidades, cuja execução irá até o final para 
testarmos se dará certo.
• Formulação B:
• estados: disposição com n (n ≤ 8) rainhas, uma por coluna nas n 
colunas mais à esquerda, sem ataque mútuo (teste gradual);
• operadores: adicionar uma rainha na coluna vazia mais à esquerda em 
que não possa ser atacada. Assim teremos apenas 2057 possibilidades, 
mas poderemos chegar a um ponto em que não haja ações possíveis;
• Formulação C:
• estados: disposição com 8 rainhas, uma em cada coluna;
• operadores: mover uma rainha atacada para outra casa, na mesma 
coluna. Esta busca de estados completa precisa de 8x7 sucessores para 
cada estado.
30INTELIGÊNCIA ARTIFICIAL
Tipos de estratégia de resolução de problemas
Os principais tipos de estratégias aplicadas na resolução 
de problemas são:
• Busca não-informada ou “cega”.
• Busca em amplitude.
• Busca com custo uniforme.
• Busca em profundidade.• Busca em profundidade limitada.
• Busca em profundidade iterativa.
• Busca bi-direcional.
• Busca informada ou pela melhor escolha (Best-First).
• Busca “gulosa” (Greedy).
• Busca A*.
• Busca com limite de espaço.
• Busca IDA (A* interativo).
• Subida de encosta (HillClimbing).
Existem quatro métricas para avaliação das estratégias de 
resolução de problemas:
• Completude: a estratégia sempre encontra uma solução 
quando existe alguma? 
• Custo do tempo: quanto tempo será gasto para encontrar 
uma solução?
• Custo de espaço: quanta memória é necessária para realizar 
a busca?
• Qualidade (optimality) da solução: a estratégia encontra a 
melhor solução quando existem diferentes soluções? Menor 
custo de caminho?
31INTELIGÊNCIA ARTIFICIAL
Busca em amplitude
Na busca em largura, amplitude ou Breadth-first, o grafo 
da solução é construído em níveis. Cada nó, a partir do nó raiz, 
é expandido para todos os sucessores do nó raiz e depois os 
sucessores desses nós, e assim por diante. Em geral, todos os 
nós, em dada profundidade no grafo de busca, serão expandidos 
antes que todos os nós no nível seguinte sejam expandidos.
Em termos estruturais, os nós do grafo podem guardar 
mais informação do que apenas o estado, por exemplo: o estado 
correspondente, o seu nó pai, o operador aplicado para gerar o 
nó (a partir do pai), a profundidade do nó, o custo do nó (desde 
a raiz) e os nós sucessores, como exemplificado na Figura 8.
Figura 8: Busca em amplitude com a marcação do nó expandido 
a cada nível
O exemplo do algoritmo da Busca em largura retorna uma 
solução ou falha.
Os métodos usados neste algoritmo são:
• MAKE-QUEUE (estado inicial): coloca o estado inicial na fila.
• REMOVE-FIRST (nodos): remove os primeiros nodos da fila.
• GOAL-TEST (nodo): testa se o nodo atual é nodo final.
• EXPAND (nodo): retorna uma lista de nodos que representam os estados, 
resultando da aplicação dos operadores ao nodo atual.
• ADD-QUEUE (nodos, novos-nodos): coloca estes nodos na fila de busca.
32INTELIGÊNCIA ARTIFICIAL
Um exemplo de resolução usando o algoritmo Breadth-First 
é exemplificado na execução da Figura 9. Considerando que o 
estado inicial é A e um dos estados finais é K, a sequência de 
execuções sobre a árvore é ilustrada pela sequência numérica 
em vermelho na Figura 9, onde o caminho resultante do estado 
inicial até o objetivo é {A,B,C,D,E,F,G,H,I,J,K}.
Figura 9: Exemplo de árvore de busca usando o algoritmo 
Breadth-First
Em relação as quatro métricas de avaliação de algoritmos 
de busca apresentadas anteriormente, a busca em amplitude 
fica assim avaliada:
• Completude: é completa.
• Qualidade: ótima, se os operadores sempre têm o mesmo 
custo.
• Custo do Tempo: O(bd) nodos explorados, onde
• b = fator de ramificação
• d = profundidade do estado final (objetivo)
• O(bd) = 1 + b + b2 + b3 + .... + bd
• Custo do espaço: O(bd) nodos armazenados, ou seja, todos 
os estados a serem expandidos devem permanecer na me-
mória e o resultado é bom quando a profundidade da árvore 
de busca é pequena.
O(x) é a notação assintótica, que significa “complexidade exponencial”, ou seja, o algoritmo leva um 
tempo exponencial em função do comprimento da entrada (x) para encontrar uma solução.
33INTELIGÊNCIA ARTIFICIAL
Exemplo de complexidade, considerando que b = 10, à 
1000 nodos por segundo e 100 bytes por nodo:
(b = 10, 1000 nodos por segundo, 100 bytes por nodo)
Profundidade Nodos Tempo Memória
0 1 1ms 100B
2 111 0,1s 11KB
4 11.111 11s 1MB
6 106 18min 111MB
8 108 31hs 11GB
12 1012 35 anos 111TB
14 1014 3500 anos 11.111TB
Busca em amplitude com custo uniforme
A estratégia de busca uniforme continua expandindo os 
sucessores, mas ao invés de pegar o primeiro nó expandido, 
será escolhido o nó que possui o menor custo (g(n)), onde a 
função g(n) é uma representação do custo do caminho.
O exemplo do algoritmo da Busca em largura com custo 
uniforme, a seguir, retorna uma solução ou falha.
Notem que a diferença na expansão dos sucessores é a fun-
ção SORT(...), que ordena a prioridade dos nodos com menor 
34INTELIGÊNCIA ARTIFICIAL
custo. Neste caso é preciso agregar informação adicional ao 
problema, por exemplo, o custo do caminho pode ser a distância 
entre cidades, a quantidade de números fora de posição em um 
quebra-cabeças, etc. 
Um exemplo de resolução usando o algoritmo Breadth-First 
com Custo Uniforme é exemplificado na execução da Figura 9. 
Considerando que o estado inicial é A e um dos estados finais 
é K, a sequência de execuções sobre a árvore é ilustrada pela 
sequência numérica em vermelho na Figura 9, onde o caminho 
resultante do estado inicial até o objetivo é {A,D,C,B,L,K}.
Figura 10: Exemplo de árvore de busca usando o algoritmo 
Breadth-First com custo uniforme.
Busca em profundidade
Na busca em profundidade ou Depth-first, o grafo da 
solução é construído em profundidade, onde cada nó, a partir 
do nó raiz, é expandido sempre o filho mais à esquerda até a 
profundidade máxima.
O exemplo do algoritmo da Busca em profundidade, a 
seguir, retorna uma solução ou falha.
Nesta busca, apenas os nodos da borda (próximos a raiz) 
do grafo comportam-se como uma fila FIFO (First-In, First-
35INTELIGÊNCIA ARTIFICIAL
-Out), executados pela função ADD-START-QUEUE (nodos, 
novos-nodos).
Um exemplo de resolução usando o algoritmo Depth-First 
é exemplificado na execução da Figura10. Considerando que o 
estado inicial é A e um dos estados finais é K, a sequência de 
execuções sobre a árvore é ilustrada pela sequência numérica 
em vermelho na Figura10, onde o caminho resultante do estado 
inicial até o objetivo é {A,B,E,F,G,C,H,I,J,D,K}.
Figura 11: Exemplo de árvore de busca usando o algoritmo 
Depth-First.
O algoritmo de busca em profundidade sempre expande 
os nós mais profundos na borda atual da árvore de busca. À 
medida que os nós são expandidos, eles são marcados como 
visitados, não fazendo mais parte da estrutura que guarda a 
borda das subárvores. Um exemplo de progresso gradual é 
ilustrado na Figura12.
Figura 12: Progresso da busca em profundidade, com nós 
inexplorados em cinza claro
36INTELIGÊNCIA ARTIFICIAL
Busca informada ou heurística
Pode-se melhorar a performance da busca através de uma 
função h(n) que representa uma avaliação do custo para atingir 
o estado final, para cada nodo n do espaço de busca.
A função h(n) é chamada função heurística ou informada, 
pois é dependente do problema, já que utiliza informação adicio-
nal para melhorar a busca, podendo representar, por exemplo, a 
minimização do custo para se atingir um objetivo ou a estimativa 
do menor caminho de um estado n até um estado objetivo.
Tipos de busca heurística:
• Busca pela melhor escolha (Best-First)
• Busca gulosa (Greedy)
• Busca A*
• Busca com limite de espaço
• Busca IDA (A* interativo)
• Subida de encosta (Hill Climbing)
Busca gulosa de melhor escolha
A busca gulosa (Greedy) procura expandir sempre o nodo 
mais próximo do objetivo, caracterizando uma escolha de melhor 
local. Esta busca usa a função de avaliação h(n) como sendo a 
estimativa do custo do nodo atual ao objetivo. No exemplo da 
Figura 13, o objetivo é partir da cidade de Arad e chegar até 
a cidade de Bucareste na Romênia e a heurística h(n) usada é 
a distância em linha reta até o objetivo.
Figura 13: Exemplo de grafo de possibilidades contendo uma estimativa 
da distância em linha reta de todas as cidades até Bucharest
37INTELIGÊNCIA ARTIFICIAL
O algoritmo expande primeiro o nó, que aparentemente é 
o mais próximo do objetivo, de acordo com h(n). A Figura14 
ilustra um resultado possível usando h(n).
Figura 14: Etapas da busca gulosa para Bucareste. Os nós são 
rotulados com a distância em linha reta até o destino (h)
Uma análise preliminar do resultado da busca gulosa de-
monstra que: 
• Completude: não, pois pode ficar em loop, a menos que o 
espaço de estados seja finito e exista um teste de estados 
repetidos.
• Qualidade (ótimo): não.
• Custodo tempo: Os(bd) nós explorados, onde b = fator de 
ramificação e d = profundidade do estado final (objetivo).
• Custo do espaço: Os(bd) nós armazenados.
38INTELIGÊNCIA ARTIFICIAL
Busca A*
A busca A* (A Estrela), procura conciliar as vantagens da 
busca em amplitude e profundidade, avaliando os nós através 
da combinação do custo para alcançar o nó (g(n)) e do custo 
para ir do nó até o objetivo (h(n)), ou seja f(n) = g(n) + h(n).
Figura 15: Etapas da busca usando A*, onde os nós são 
rotulados com f(n) = g(n) + h(n)
A Figura15 ilustra o exemplo do caminho de busca para 
o exemplo anterior. Se tomarmos agora a distância real per-
corrida entre cada trecho, h(n), perceberemos que a estratégia 
A* produz o seguinte caminho de solução: Arad -> Sibiu -> 
Rimnici Vilcea -> Pitesti -> Bucharest, resultando em um 
custo total de (140+80+97+101 = 418). Enquanto que a estra-
tégia Gulosa, da Figura14, gera o caminho solução: Arad -> 
Sibiu -> Fagaras -> Bucharest, resultando em um custo total de 
(140+151+178 = 469), embora tenha percorrido menos cidades. 
Ou seja, a estratégia A* encontra uma solução ainda melhor 
que a estratégia Gulosa.
A principal diferença dos algoritmos de busca cega para os 
algoritmos de busca informada é a expansão do próximo nó a 
ser analisado. Um algoritmo genérico para buscas informadas, 
a seguir, retorna uma solução ou falha.
39INTELIGÊNCIA ARTIFICIAL
Onde o método GET-BEST-NODE (nodos) implementa 
a função f(n) = g(n) + h(n) para o algoritmo A*, e a função f(n) 
= h(n) para o algoritmo Guloso.
A análise do resultado do algoritmo A* demonstra que: 
• Completude: sim, pode ficar em loop; a menos que o espaço 
de estados seja finito e exista um teste de estados repetidos.
• Qualidade (ótimo): sim, se f(n) é admissível.
• Custo do Tempo: os(bd) nós explorados, onde b = fator de 
ramificação e d = profundidade do estado final (objetivo).
• Custo do Espaço: os (bd) nós armazenados.
Admissibilidade de uma função heurística
Uma heurística é admissível se, para cada nodo, o valor 
retornado por esta heurística nunca ultrapasse o custo real do 
melhor caminho deste nodo até o objetivo. Dado que h(n) é 
estimativa de custo de n até a solução, g(n) é custo real de n até 
a solução, então se h(n) ≤ g(n), então h é admissível e, portanto, 
o algoritmo será ótimo, ou seja, sempre encontra o caminho 
mais curto até a solução.
40INTELIGÊNCIA ARTIFICIAL
Busca competitiva
O que existe em comum entre negociações internacionais, 
decisões estratégicas de executivos de empresas concorrentes, 
uma partida de xadrez e as estratégias de busca vistas até agora?
Quando mais de um ator participa de uma resolução de 
problemas, geralmente surgem conflitos em ambientes com-
petitivos, dando origem a problemas de busca competitiva ou 
jogos, como vimos no início deste capítulo.
No contexto de problemas de busca competitiva, alguns 
jogos possuem características que podem ser formuladas como 
competições abstratas, por exemplo:
• representados por estados e regras claramente definidos;
• programas para alguns jogos podem ser derivados de mé-
todos de busca, onde alguns precisam da incorporação de 
conhecimento e informações adicionais
Definições preliminares
Um Jogo é um modelo teórico de conf litos de interesse 
(decisões possíveis, resultados possíveis) entre duas ou mais 
pessoas que têm motivações conflitantes. Um Jogador é um 
participante ativo e racional em um jogo, cujas ações afetam 
os demais. Movimentos são decisões disponíveis aos jogadores 
(simultaneamente ou não): são seguidos de uma ação, resultan-
do em um ganho (outcome, payoff, utility), podendo ser um 
evento probabilístico.
Nas interações competitivas, as escolhas são alternativas 
particulares selecionadas por jogador e uma jogada é uma se-
quência destas escolhas. Estratégias são descrições das decisões 
a tomar em todas as situações possíveis e o resultado destas 
jogadas resulta em valor ou pagamento de uma ação (Payoff / 
Utility / Ganho) ou ainda uma expressão de preferência.
41INTELIGÊNCIA ARTIFICIAL
Taxonomia de jogos
1. Segundo o payoff:
a. Jogos de soma zero: soma dos payoffs dos participantes 
é zero (Nim, Pôquer, Xadrez, etc.).
b. Jogos de soma não zero: resultados dos payoffs  zero 
(dilema do prisioneiro, etc.).
2. Segundo a informação:
a. Jogos com informação perfeita: a cada jogada, todos os 
jogadores têm conhecimento das jogadas que já ocorreram 
( Jogo da velha, Nim, Xadrez, Go, etc.).
b. Jogos com informação imperfeita: conhecimento é parcial (Pôquer).
3. Duração: jogos infinitamente longos, aplicados por mate-
máticos teóricos.
4. Simultaneidade: 
a. Jogos simultâneos cujos movimentos são paralelos e des-
conhecidos pelos oponentes.
b. Jogos sequenciais, com movimentos intercalados.
5. Simetria: 
a. Jogos simétricos: onde os payoffs para uma dada estratégia 
dependem de outras estratégias empregadas.
b. Jogos assimétricos: não existe um conjunto idêntico de 
estratégias para ambos os jogadores.
42INTELIGÊNCIA ARTIFICIAL
Formulação de problemas competitivos
Geralmente, quando um jogo é formulado em termos de 
estratégias de busca, ocorre um ambiente onde os agentes são 
considerados hostis (competitivos) e a representação de jogos 
como busca torna-se:
• relativamente fácil;
• com operadores bem definidos;
• os oponentes introduzem incertezas;
• com resolução complexa (por exemplo, no xadrez, fator médio 
de ramificação 35 e árvore com 35100 nodos);
• limitado em tempo e espaço.
Tradicionalmente, a definição formal de um jogo requer 
a representação de um estado inicial (de um tabuleiro, das 
posições das peças e do iniciador do jogo). É preciso descrever 
os operadores, como as ações definem os movimentos permiti-
dos. E, definir um teste final para determinar quando o jogo 
termina, o cálculo do resultado (vitória, empate ou derrota), o 
cálculo da função de utilidade (payoff) e um valor numérico 
para cada resultado do jogo.
Segundo Russel & Norvig (2013), um jogo pode ser de-
finido formalmente como uma espécie de problema de busca 
com os seguintes componentes:
• S0: o estado inicial, designando como o jogo é inicialmente 
criado.
• JOGADORES(s): define qual jogador deve se mover em 
um estado.
• AÇÕES(s): retornam o conjunto de movimentos válidos 
em um estado.
• RESULTADO (s, a): o modelo de transição que define o 
resultado de um movimento.
43INTELIGÊNCIA ARTIFICIAL
• TESTE DE TÉRMINO(s): retorna verdadeiro quando 
o jogo termina, onde os estados são chamados estados ter-
minais.
• UTILIDADE (s, p): uma função de utilidade ou objetivo 
que define o valor numérico para um jogo que termina no 
estado terminal s por um jogador p. Por exemplo, no xadrez, 
o resultado é uma vitória, uma derrota ou um empate, com 
valores +1, 0 ou ½.
a. Desta forma, o estado inicial S0, a função AÇÕES(s) 
e a função RESULTADO (s, a) definem a árvore de jogo, 
onde os nós são estados do jogo e as bordas são movimentos. 
Considerando que os jogadores são nomeados como MAX e 
MIN. A Figura 16 ilustra parte de uma árvore de jogo para 
o Jogo da Velha. A partir do estado inicial, MAX tem nove 
movimentos possíveis. O jogo se alterna entre a colocação 
de um X por MAX e a colocação de um O por MIN até 
que os nós folhas (ou estados terminais) sejam alcançados. 
O número em cada nó de folha indica o valor de utilidade 
do estado terminal, do ponto de vista de MAX. Neste caso, 
a estratégia básica é MAX tentando maximizar seu ganho e 
MIN tentando minimizar os efeitos das jogadas de MAX.
Figura 16: Exemplo de árvore de busca (parcial) para o Jogo da 
velha
44INTELIGÊNCIA ARTIFICIAL
Para o problema do Jogo da velha, a 
árvore tem o tamanho de aproximadamen-
te 9! = 362.880 nós terminais. Portanto, 
trivial de implementar, mas o Xadrez, por 
exemplo, já apresenta mais de 1040 nós. 
Portanto, não é uma busca trivial e nem 
ótima do ponto de vista de completude. 
Portanto, a visualização em árvore deste 
tipo de problema é apenas teórica.
Na Figura 17 seráilustrada uma 
parte da árvore de escolhas para MAX 
(representado por ) e o outro jogador, 
MIN (representado por ). Os nós ter-
minais mostram os valores de utilidade 
para MAX. A seta vermelha indica o 
melhor movimento de MAX na raiz, 
através da ação A1, porque leva a um 
estado com o mais alto valor minimax.
Figura 17: Exemplo de uma árvore parcial 
de jogo de duas jogadas
O que é este tal de “minimax”?
A partir da árvore de jogo, uma es-
tratégia ótima para a escolha das ações 
é determinada pelo valor minimax de 
cada nó. O valor minimax de um nó é a 
utilidade que MAX conhece de se en-
contrar no estado correspondente, supon-
do-se que ambos os jogadores tenham 
desempenho ótimo desde esse estado 
até o fim do jogo. O valor minimax de 
um estado terminal é simplesmente sua 
utilidade. MAX sempre terá a tendên-
cia de se mover para um estado de valor 
máximo, enquanto MIN preferirá um 
estado de valor mínimo, ou seja, dado 
que minimax é VALOR-MINIMAX(n):
O algoritmo MinMax-VALOR, 
ilustrado abaixo, calcula a decisão mi-
nimax a partir do estado atual (“estado”). 
De forma recursiva, o algoritmo percorre 
todo o caminho descendente até as folhas 
da árvore e, depois, os valores minimax 
são propagados de volta pela árvore, à 
medida que a recursão retorna.
45INTELIGÊNCIA ARTIFICIAL
No exemplo da Figura17, o algoritmo MinMax-VALOR, 
primeiro percorre todo o caminho desde o nó raiz até o nó 
terminal mais à esquerda, no terceiro nível de profundidade da 
árvore. Retorna com a função UTILIDADE (estado) sobre eles 
para descobrir que seus valores são 3, 12 e 8, respectivamente. 
Em seguida, calcula o mínimo desses valores, 3, e o devolve 
como valor propagado de volta para o nó B. Um processo se-
melhante fornece os valores propagados de volta de 2 para C 
e 2 para D. Por fim, tomamos o valor máximo entre 3, 2 e 2 
para obter o valor propagado de volta igual a 3 para o nó raiz.
O algoritmo minimax explora completamente árvore de jogo 
em profundidade. A complexidade de tempo e espaço do algoritmo 
é O(bm), para uma profundidade máxima de m e b movimentos 
válidos, caso todos os sucessores sejam gerados de uma vez. A 
complexidade de espaço será O(m) quando as ações forem geradas, 
uma de cada vez. Em jogos reais, o custo de tempo é totalmente 
impraticável, pois a busca é exponencial em relação ao número 
de movimentos. Uma estratégia importante é a possibilidade de 
calcular a decisão minimax correta sem examinar todos os nós 
na árvore de jogo. Esta estratégia se chama Poda Alfa-Beta.
A poda Alfa-Beta é um processo de eliminar ramificações 
da árvore sem examiná-las, descartando os que não contenham 
bons movimentos. Aplica-se a ambos os jogadores e α (Alfa) 
denota a melhor escolha para MAX, enquanto β (Beta) denota 
a melhor escolha para MIN.
A partir da Figura 18, o princípio da Poda Alfa-Beta 
define que:
46INTELIGÊNCIA ARTIFICIAL
• se o valor α representa o melhor valor encontrado para MAX 
(ou MIN), e se ѵ é pior do que β, MAX/MIN já achou uma 
jogada boa e pode evitar a ramificação para v.
Figura 18: Exemplo de princípio da poda alfa-beta
Um algoritmo para a Poda Alfa-Beta é ilustrado a seguir:
47INTELIGÊNCIA ARTIFICIAL
Síntese
Este capítulo introduziu métodos de resolução de problemas através de processos de busca, definindo es-
tratégias que um agente pode usar para selecionar ações em ambientes determinísticos, observáveis, estáticos e 
completamente conhecidos. A identificação de um objetivo e a formulação de um problema são etapas crítica 
na resolução de problemas. A formulação através da definição de um estado inicial, um conjunto de ações, um 
modelo de transição, a função de teste de objetivo e as métricas de custo são indispensáveis para um agente 
planejar a resolução.
Algoritmos genéricos de busca consideram todos os caminhos possíveis em estratégias de buscas em árvores, 
enquanto que, se considerarmos a busca em grafos, podemos evitar a construção de caminhos redundantes. Analisar 
os algoritmos em termos de sua completude, otimização e complexidade em tempo e espaço é uma importante 
etapa da determinação da performance do algoritmo e na definição da qualidade das soluções encontradas.
Os Toy Problems aqui apresentados e suas estratégias de solução constituem experimentos e esforço de 
pesquisa de aplicação em problemas no mundo real. Determinar voos ótimos de linhas aéreas, aplicação do pro-
blema do caixeiro-viajante, entre outros, constituem aplicação direta de uma estratégia combinatória-padrão em 
Computação. Aproximações do problema do caixeiro-viajante são utilizadas em desenho de layouts de circuitos 
VLSI (Very-Large-Scale Integration) e em problemas de navegação e montagem de robôs.
48INTELIGÊNCIA ARTIFICIAL
Exercícios
Formulação de problemas
Procure construir a formulação dos pro-
blemas (espaço de estados, estados inicial e 
finais, teste objetivo, operadores e custo do 
caminho) abaixo, ilustrando com um grafo 
parcial de busca:
Robô aspirador: como exercício, pro-
cure definir uma formulação adequada para 
o problema do robô aspirador, construindo 
o espaço de estados possíveis, os estados 
inicial e final, as ações do robô (regras ou 
operadores), o teste de término e o custo 
do caminho.
Jogo de 8-números: também conhecido 
como n-puzzle, consiste em um tabuleiro 
den×ncasas, contendo n*n-1números ini-
cialmente desordenados arranjados aleato-
riamente em cada casa do tabuleiro. Tome 
como exemplo um tabuleiro de 3×3 casas, 
distribuídos a seguir:
Início:
O objetivo é alcançar uma configura-
ção com os números ordenados através de 
movimentos que só podem ser feitos para a 
casa que está sempre vazia:
Final:
Problema dos vasilhames com água: 
existem 2 vasilhames, 1 de 4 litros e outro 
de 3 litros, sem medidas. Uma torneira pode 
ser utilizada para enchê-los. O objetivo é 
colocar exatamente 2 litros de água no va-
silhame de 4 litros.
Problema dos canibais e missionários: 
três canibais e três missionários estão via-
jando juntos e chegam à margem de um rio. 
Eles desejam atravessar para a outra margem 
e desta forma, continuar a viagem. O único 
meio de transporte disponível é um barco 
que comporta no máximo duas pessoas. Há 
uma outra dificuldade: em nenhum momen-
to o número de canibais pode ser superior ao 
número de missionários, pois desta forma, 
os missionários estariam em grande perigo 
de vida. Como administrar a travessia?
4 5 8
1 6
7 2 3
1 2 3
4 5 6
7 8
49INTELIGÊNCIA ARTIFICIAL
Estratégia busca não-informada ou cega
1. Escreva os algoritmos para busca em profundidade limitada 
e busca em profundidade iterativa, sabendo que:
• Na busca com profundidade limitada, a busca não ultrapassa 
um valor limite de profundidade. A solução deve encon-
trar-se dentro desse limite. Esse tipo de busca não tem uma 
solução ótima.
• Na busca em profundidade iterativa, tenta-se primeiro uma 
busca em profundidade com limite de profundidade 0; se 
não existe uma solução, repete-se o procedimento com pro-
fundidades 1, 2, ..., n até alcançar uma solução.
2. Baseado na análise da busca em amplitude, faça a análise 
das buscas em profundidade, profundidade limitada e pro-
fundidade iterativa (sem os exemplos de complexidade).
Busca competitiva
1. Construir a árvore minimax com os payoffs indicados nos 
nodos terminais para o Jogo dos 5 palitos:
• Objetivo do jogo: de um conjunto de 5 palitos, pegar 1 ou 
2 palitos e não ser o último a jogar.
• Exemplo de Cenário 1:
• Jogador 1: retira 2 palitos
• Jogador 2: retira 2 palitos
• Jogador 1: retira o último (perde).
• Exemplo de Cenário 2:
• Jogador 1: retira 1 palito.
• Jogador 2: retira 2 palitos.
• Jogador 1: retira 1 palito.
• Jogador 2: retira o último (perde).
2. Construa o caminho dos nós da árvore na Figura 17, usan-
do a Poda Alfa-Beta, indicando os caminhos que serão 
descartados.
50INTELIGÊNCIA ARTIFICIAL
SISTEMAS 
ESPECIALISTAS
Existem problemas cujo domínio está apenas 
na cabeça das pessoas, não formalizado.Neste caso, é preciso resolver problemas com 
a ajuda de um especialista e a simulação de 
sua inteligência.
51INTELIGÊNCIA ARTIFICIAL
Sistemas especialistas armazenam e processam conheci-
mento adquirido a partir da interação com especialistas em uma 
área de conhecimento. Inicialmente, constituem apoio à decisão, 
usando conhecimentos sobre áreas específicas, de acordo com 
comportamento humano diante destas situações. Geralmente, 
os sistemas especialistas usam métodos inferenciais na resolução 
de problemas complexos, a partir da experiência humana.
Antes de mais nada, é preciso que o sistema incorpore algum 
conhecimento humano para poder tomar decisões, responden-
do questões através de um processo de tomada de decisão ou, 
simplesmente, dividindo esse processo por meio de interações 
com o especialista.
Basicamente, como qualquer abordagem de IA, um sistema 
especialista simula o comportamento humano. Um especialista 
se baseia em fatos estabelecidos para formular hipóteses a fim 
de tomar uma decisão sobre um determinado assunto. Para isto, 
busca em sua memória um conhecimento previamente armaze-
nado, no período de sua formação ou no decorrer de sua vida 
profissional, sobre esses fatos e hipóteses. Finalmente, usa sua 
experiência sobre os fatos e hipóteses para emitir uma decisão.
Sistemas especialistas podem ser diretamente aplicados a 
vários tipos de tarefas de resolução de problemas:
• Tarefas de diagnóstico: processo de encontrar falhas em 
um sistema ou doenças em seres vivos. Exemplo: MYCIN 
diagnóstico de infecção sanguínea (Shortlife, 1973).
• Tarefas de interpretação: análise de dados para determinar 
seu significado. Exemplo: PROSPECTOR (Duda et al., 
1977) interpretação de dados geológicos como evidência 
para depósitos minerais.
• Tarefas de monitoramento: interpretação contínua de sinais 
em um sistema com objetivo de diagnosticar ou dar um alarme. 
Exemplo: NAVEX monitoramento de dados de radar para 
estimar velocidade e posição do Space Shuttle (Marsh, 1984).
52INTELIGÊNCIA ARTIFICIAL
• Tarefas de projeto (design): produção de especificações de 
sistemas que satisfaçam a requerimentos particulares. Exem-
plo: R1/XCON configuração de sistemas VAX baseada nas 
necessidades do cliente (McDermott, 1980).
• Tarefas de planejamento: produção de uma sequência de 
ações para atingir um objetivo específico. Exemplo: MOL-
GEN planejamento de processos químicos para análise e 
síntese de DNA (Stefik, 1981).
• Tarefas de predição: previsão de eventos futuros usando 
um modelo baseado em dados do passado e do presente. 
Exemplo: PLANT, previsão dos danos esperados quando 
determinada praga atacava o milho (Boulanger, 1983).
Alguns exemplos de sistemas especialistas históricos:
1965: DENDRAL (Stanford): Inferência sobre estruturas químicas.
 MACSYMA (MIT): Análise de equações simbólicas diferenciais.
HERSAY (Carnegie-Mellon): Interpretação de conjuntos fonéticos 
em linguagem natural.
1972: MYCIN (Stanford): Diagnóstico de doenças sanguíneas.
 PROSPECTOR (Stanford): Exploração e identificação de minérios.
1980: R1/XCON (Carnegie-Mellon): Configuração de computadores DEC.
Um rápido exemplo de uma aplicação do MYCIN (Da-
vis et al., 1977) é um modelo para diagnosticar meningite 
e outras infecções bacterianas, e prescrever tratamento:
• Representação de conhecimento baseada em regras 
probabilísticas (em torno de 500).
• Acima de 90% de acerto.
• Introduziu explicação e boa interface com usuário.
• Exemplo de regra:
53INTELIGÊNCIA ARTIFICIAL
Arquitetura de um sistema especialista
Existem várias estruturas e arquiteturas possíveis em que 
se pode organizar um sistema especialista. Geralmente, os 
principais elementos constituintes de um sistema especialista 
genérico são os exemplificados na Figura 19. 
Figura 19: Arquitetura geral de um sistema especialista básico
O Usuário é o elemento responsável pela verificação e 
validação do comportamento do sistema. Pode ser o especia-
lista que adiciona conhecimento ou modifica o conhecimento 
armazenado no sistema. Realiza as interações para obter res-
postas do sistema ou desenvolver especialidade relacionada ao 
domínio, extraindo conhecimento organizado.
A Base de Conhecimento (BC) constitui o repositório das 
primitivas de conhecimento: fatos, regras e heurísticas. O 
projeto deste dispositivo inf luencia o projeto e mecanismo de 
inferência, o processo de atualização do conhecimento e o me-
canismo de atualização. Para seu desenvolvimento, utilizam-se 
técnicas de representação do conhecimento, tais como: regras 
de produção, redes semânticas, frames, scripts, etc.
O processo de construção de uma base de conhecimento 
específico ao domínio é tarefa de um especialista conhecido 
como Engenheiro do Conhecimento.
54INTELIGÊNCIA ARTIFICIAL
AQUISIÇÃO
NÍVEL DE CONHECIMENTO
NÍVEL LÓGICO
NÍVEL DE IMPLEMENTAÇÃO
FORMULAÇÃO
IMPLEMENTAÇÃO
REFINAMENTO BC
O processo de aquisição do conhecimento pressupõe um 
levantamento de requisitos de conhecimento, isto é, extrair, 
estruturar e organizar o conhecimento de uma ou mais fontes. 
É a atividade inicial do processo de engenharia de conhecimen-
to, e indispensável para que as informações essenciais sejam 
coletadas e o conhecimento chave fique disponível para ser 
organizado, representado, implementado e validado através de 
um sistema. Geralmente, aplicam-se técnicas de pesquisa quali-
tativas: entrevistas, questionários, narrativas, técnicas manuais, 
semiautomáticas ou automáticas, como algoritmos de extração 
de conteúdo de documentos, mineração de dados, raciocínio 
baseado em casos, aprendizado de máquina, entre outras.
Nos sistemas especialistas, o aprendizado ocorre com a in-
corporação de novas regras nas bases de conhecimento. A cada 
processamento da base de conhecimento, o sistema especialista 
assume como verdade o conhecimento ali formalizado. Isto é pos-
sível em virtude da estrutura modular da base de conhecimento, 
permitindo a adição ou deleção de novos elementos sem alterar 
a lógica global do sistema.
Na etapa de formulação e implementação, o engenheiro precisa 
formalizar na Base de Conhecimento, podendo ser representado, 
por exemplo, através de regras de produção. Um conjunto de regras 
de produção pode ser mapeado em árvores de decisão, que são 
representações mais simples do conhecimento e, um meio efi-
ciente de construir classificadores que predizem classes baseadas 
nos valores de atributos de um conjunto de dados. Tecnicamente, 
árvores de decisão são grafos acíclicos que consistem de nodos 
que representam os atributos de arcos, provenientes destes nodos 
e que recebem os valores possíveis para estes atributos, e de no-
dos-folha, que representam as diferentes classes de um problema.
55INTELIGÊNCIA ARTIFICIAL
O Motor de Inferência é o componente do SE que aplica um 
conjunto de regras lógicas sobre a BC para deduzir informações 
novas, fornecendo elementos para a aprendizagem e explanação 
do problema. 
A capacidade do motor de inferência é baseada em um inter-
pretador capaz de percorrer a BC e buscar fatos que, deduzidos por 
regras de inferência lógicas, consegue inferir novo conhecimento. 
Duas estratégias de raciocínio são comumente usadas: 
• Forward chaining: encadeamento progressivo que inicia pelas 
condições e vai em direção aos objetivos.
• Backward chaining: encadeamento regressivo que inicia pelos 
objetivos e vai em direção às condições.
Estas regras são armazenadas na base 
de conhecimento no formato SE/ENTÃO, 
usando a seguinte gramática simplificada:
O motor de inferência pode processar estas regras usando 
encadeamento regressivo, se começar com a solução, e verifi-
car tal solução fazendo perguntas ao usuário para verificar o 
resultado. As perguntas feitas ao usuário são apenas para obter 
informações que não estão na base de conhecimento.
O encadeamento progressivo acontece no questionamen-
to ao usuário por toda a informação necessária. Em seguida, 
esta informação é usada com diferentesregras para ver se ela 
se ajusta a quaisquer dos problemas previamente descritos. Se 
ajustar, ela repassa a possível solução ao usuário.
Sendo um mecanismo genérico de causa e efeito (SE-
-ENTÃO), o motor de inferência pode ser reutilizado em 
vários contextos. Os demais componentes variam em função 
da aplicação. O motor de inferência é o módulo do sistema 
responsável pelo processo de inferência que é aplicado sobre o 
conhecimento disponível na base de conhecimento em função 
dos fatos informados via interface ou obtidos da base de dados.
SE
 <Condição 1>
 <Condição 2>
ENTÃO
 <Conclusão 1>
 <Conclusão 2>
56INTELIGÊNCIA ARTIFICIAL
Modo de raciocínio
Em um sistema especialista baseado em regras, o conhe-
cimento do domínio é todo representado em relações de con-
sequência por regras de produção no formato SE-ENTÃO 
agrupados em um conjunto “Regras (MR)”. Os dados são 
representados por um conjunto de fatos sobre a situação cor-
rente “Fatos (MF)”. A máquina de inferência compara cada 
regra a partir dos fatos armazenados na base de conhecimento, 
através de um mecanismo de “Pattern Matching”. Quando a 
parte da condição “SE” combina com algum fato na base de 
conhecimento, a regra é disparada e a ação na parte “ENTÃO” 
é executada. A combinação de regras com os fatos determina 
uma cadeia de inferência ou modo de raciocínio que pode alterar 
a base de conhecimento, descobrindo fatos novos, conforme o 
f luxo desta Figura:
Regras (MR) Fatos (MF) 
Conjunto de Conflitos (CC)
Pattern Matching
Resolução de conflitos
Disparo da(s) regra(s)
Regra(s) escolhida(s)
Alterações em MF (MR)
Eventualmente, um conjunto de fatos pode disparar a 
mesma regra, ou um fato pode fazer parte de várias regras na 
parte de condição, neste caso, um Conjunto de Conflitos (CC) 
é gerado. Quando isto ocorre, um mecanismo de resolução de 
conflitos deve ser acionado a fim de desambiguar as regras e 
definir uma geração determinística de fatos.
57INTELIGÊNCIA ARTIFICIAL
Vamos a um exemplo prático. Su-
ponha que seja necessário construir um 
sistema especialista para oferta de em-
prego especializado:
• Variáveis:
• Descoberta: o candidato fez alguma 
descoberta?
• Experiência: quantos anos de ex-
periência tem o candidato?
• Média: qual a nota média do can-
didato em seu curso superior?
• Posição: que posição deve ser ofe-
recida ao candidato?
• Qualifica: o candidato se qualifica 
para uma posição?
Após esta etapa de aquisição do co-
nhecimento, as variáveis que conciliarão a 
base de fatos, podem ser assim formuladas:
Variáveis de entrada com respectivos valores:
Descoberta: Sim / Não.
Diploma: Sim / Não.
Experiência (em anos): um número. 
Média (nota média do histórico): um número.
Variáveis de saída com valores possíveis: 
Posição: Nenhuma / Pesquisa / Eng. De Serviço / 
Eng. De Produto.
Qualifica: Sim / Não.
Seja o conjunto de regras assim assi-
nalado, formando a Memória de Regras 
(MR):
R1: SE (Diploma = Não)
 ENTÃO (Posição <-- Nenhuma).
R2: SE (Diploma = Sim) 
 ENTÃO (Qualifica <-- Sim).
R3: SE (Diploma = Sim) E (Descoberta = Sim) 
 ENTÃO (Posição <-- Pesquisa).
R4: SE (Qualifica = Sim) E (Média <= 7,0) E (Experiência 
>= 2)
 ENTÃO (Posição <-- Eng. De Serviço).
R5: SE (Qualifica = Sim) E (Média < 7,0) E (Experiência 
> 2) 
 ENTÃO (Posição <-- Não).
R6: SE (Qualifica = Sim) E (Média > 7,0) 
 ENTÃO (Posição <-- Eng. de Produto).
O conjunto de fatos iniciais, forman-
do a Memória de Fatos (MF) é assim 
inicializado:
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
O modo de inferência usando Fo-
rward-Chaining, apresenta o seguinte 
algoritmo:
58INTELIGÊNCIA ARTIFICIAL
A execução completa do algoritmo, até que nenhuma regra 
seja mais disparada, constrói as três épocas abaixo:
O modo de inferência usando Backward-Chaining, apre-
senta o seguinte algoritmo:
Neste caso, a cadeia de inferência será:
Fatos iniciais (M0):
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
Inferência 1: Dispara R2.
F4: (Qualifica = Sim).
Fatos iniciais (M1):
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
F4: (Qualifica = Sim).
Inferência 2: Dispara R6.
F5: (Posição = Eng. de Produto).
Fatos iniciais (M2):
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
F4: (Qualifica = Sim).
F5: (Posição=Eng.de Produto).
Não dispara mais regras.
59INTELIGÊNCIA ARTIFICIAL
Tratamento de incerteza
O tratamento da incerteza lida com o raciocínio inexato e 
pode ser feito através da utilização de valores intermediários 
entre os valores verdadeiro e falso. A forma clássica de imple-
mentação é feita pela quantificação do grau ou fator de certeza 
do conhecimento, conforme alguma escala convencionada pelo 
especialista.
Um exemplo de escala para o grau de incerteza do conhe-
cimento utilizado no sistema MYCIN (Davis et al., 1977) é 
apresentado na Tabela: Fator de Certeza Significado
100 Definitivamente certo
80 Quase certo
60 Provável
30 Há evidências
20 Ignorado
0 Ignorado
-20 Ignorado
-40 Há evidências contra
-60 Provavelmente não
-80 Quase certo que não
-100 Definitivamente não
Os Fatores de Certeza (FC), usados para tratamento de 
incerteza, foram originalmente definidos como a diferença 
entre a crença e a descrença, onde a partir de uma hipótese 
(H) dada a evidência (E), envolve o cálculo das funções:
• MC[H, E]: grau de aumento da crença na hipótese H, se E for ob-
servada.
• MD[H, E]: grau de aumento da descrença na hipótese H, se E for 
observada.
Ambas as medidas MC e MD serão definidas em função de:
• p(H): probabilidade a priori de H;
• p(H|E): probabilidade a posterior de H ou probabilidade condicional, 
dada a evidência E.
Logo, o fator de crença FC na hipótese H dada a evidência 
E é calculado por:
• FC [H, E] = MC[H, E] – MD[H, E]
60INTELIGÊNCIA ARTIFICIAL
A partir desta abordagem é possível combinar crença e descrença 
em uma medida de utilidade, por exemplo, se um paciente tem cer-
tos sintomas os quais sugerem diversas doenças possíveis, a doença 
com um alto FC poderia ser a primeira a ser investigada pelos testes 
ordenados.
O FC representa uma rede de crenças em uma hipótese sobre 
alguma evidência, onde um FC positivo significa que a evidência 
suporta a hipótese desde que MC > MD. Um FC=1 significa que a 
evidência definitivamente prova a hipótese enquanto um FC=0 pode 
significar:
• que não existe evidência ou ela é irrelevante (MC=MD=0);
• a crença é cancelada pela descrença, pois as duas são igualmente 
fortes ou fracas (MC=MD≠0).
Em contrapartida, um FC negativo significa que a evidência favo-
rece a negação da hipótese, desde que MC < MD, ou seja, existem mais 
razões para a descrença em uma hipótese do que para a crença nela.
Sistema de explanação
O sistema de explanação é usado quando um usuário 
precisa de uma explicação sobre a cadeia de inferência 
realizada de SE, exibindo “por que” e “como” o sistema 
chegou a determinada conclusão, rumo à solução do 
problema analisado. O processo é caracterizado por uma 
busca inversa, percorrendo as trilhas utilizadas e mar-
cadas durante a sessão de consulta, apresentando todos 
os argumentos que o levaram à solução apresentada. 
O processo de explanação também pode ser utili-
zado como instrumento de treinamento do usuário, já 
que apresenta conceitos teóricos e aplicações práticas, 
reforçando a tese da importância das interfaces na apli-
cação de sistemas especialistas.
Para fornecer explanações, um SE necessita utilizar 
“metaconhecimento”, conhecimento sobre o seu próprio 
61INTELIGÊNCIA ARTIFICIAL
conhecimento e, “introspecção”, observação sobre o seu próprio 
modo de operação. Muitas vezes estas explicações são feitas listando 
as regras que estão sendo utilizadas.
O objetivo da explanação é apresentar o comportamento do 
SE através de questões como:
• Por que uma certa pergunta foi feita pelo SE?
• Como a conclusãofoi alcançada?
• Por que alguma alternativa foi rejeitada?
• Qual é o plano para alcançar a solução?
Por exemplo, para responder à pergunta “por que é necessário 
saber o preço?”, o sistema de explanação navega pela árvore da ca-
deia de inferência buscando as informações contidas no conjunto de 
regras. Assim, uma explanação pode ser a apresentação da própria 
regra que disparou alguma condição:
REGRA #5
 SE preço = importante E pagamento = prestação
 ENTÃO
 pagamento mensal é determinado
Ferramentas de sistemas especialistas
Atualmente, a própria IA se confunde com Sistemas 
especialistas, por este ser apenas uma técnica de aplica-
ção, muitas ferramentas foram criadas especificamente 
para modelar sistemas especialistas, tal como foi abor-
dado neste capítulo. O quadro ilustrará alguns exemplos 
de ferramentas, sistemas e abordagens que podem ser 
usados em aplicações de sistemas especialistas:
62INTELIGÊNCIA ARTIFICIAL
Ferramenta Descrição Acesso
BABYLON Permite desenvolver frames, regras de produção, lógica (PROLOG) e restrições. Requer o Common Lisp instalado.
https://www.cs.cmu.edu/afs/cs/project/ai-repository/
ai/areas/expert/systems/babylon/0.html
CLIPS (C Language Integrated 
Production System)
Baseado em forward-chaining, escrito em C. Desenvolvido pela NASA. 
Plataformas: DOS, Windows, VMS, Mac e UNIX. http://www.clipsrules.net/Documentation.html
DYNACLIPS (DYNAamic CLIPS 
Utilities)
Conjunto de ferramentas constituído por blackboard, troca de conhecimento 
dinâmico e agentes que podem ser linkados com CLIPS.
https://www.cs.cmu.edu/afs/cs/project/ai-repository/
ai/areas/expert/systems/clips/dyna/0.html
FuzzyCLIPS CLIPS com conceitos nebulosos (fuzzy) e raciocínio. https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html
Jess the Rule Engine for Java Ambiente para máquina de regras declarativas em Java. https://herzberg.ca.sandia.gov/jess/
Expert SINTA
Representação do conhecimento baseado em regras de produção e fatores de 
confiança. Motor de inferência compartilhado: construção automática de telas e 
menus, tratamento de incerteza e utilização de explicações sensíveis ao contexto. 
http://www.lia.ufc.br/~bezerra/exsinta/
PIKE - Python knowledge engine Através de regras de forward/backward chaining através de código python. http://pyke.sourceforge.net
EZ-Xpert 3.0 Sistema baseado em regras que apresentam rápido desenvolvimento, grande velocidade e precisão, implementado sem um mecanismo de inferência. http://www.ez-xpert.com/index.html
LPA (Logic Programming 
Associates) Plataforma para desenvolvimento de Sistemas especialistas. http://www.lpa.co.uk/pro_exp.htm
IBM Watson Conjunto de ferramentas de IA, entre elas, sistemas baseados em regras. www.ibm.com/watson/br-pt
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/babylon/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/babylon/0.html
http://www.clipsrules.net/Documentation.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/dyna/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/dyna/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html
https://herzberg.ca.sandia.gov/jess/
http://www.lia.ufc.br/~bezerra/exsinta/
http://pyke.sourceforge.net/
http://www.ez-xpert.com/index.html
http://www.lpa.co.uk/pro_exp.htm
http://www.ibm.com/watson/br-pt
63INTELIGÊNCIA ARTIFICIAL
Síntese
Neste capítulo abordamos detalhes dos vários temas pertencentes ao estudo de 
Sistemas multiagentes, principalmente aliando questões conceituais com aplicações 
práticas e introdução a algoritmos básicos de comportamento de sistemas de agentes. 
Estudos mais recentes integram comportamentos cognitivos com representação de 
objetos inativos do ambiente, artefatos simbólicos de atuação do agente e repre-
sentação de questões normativas para comportamento social. A área de simulação 
atrai bastante atenção para a simulação de modelos matemáticos através de com-
portamentos reativos e deliberativos de múltiplas entidades interagentes.
As questões aqui abordadas são base para aplicações, envolvendo tomadas de 
decisão, planejamento autônomo, elaboração de metas, avaliação de atividades co-
ordenadas e inteligência distribuída.
64INTELIGÊNCIA ARTIFICIAL
Exercícios
Problema 1: Diagnóstico de falha de automóveis
O usuário expõe o problema, dizendo que “tentou ligar o 
carro hoje e o motor não funcionou”!
• Procure modelar o problema utilizando regras de produção 
a partir da seguinte explicação do especialista:
• Quando o motor de um carro não arranca, minha primeira 
suspeita é de que o carro esteja sem gasolina. Porém, se 
há cheiro de gasolina quando se tenta arrancar, ou se tem 
a certeza que o tanque está cheio, suspeito que a gasolina 
pode não chegar ao carburador, logo, a mangueira pode estar 
bloqueada. Se até aqui tudo está bem, tente ligar os faróis 
para testar a bateria ou algum problema elétrico.
Problema 2: Diagnóstico médico
Três diagnósticos distintos são identificados através dos 
seguintes conjuntos de sintomas e problemas associados.
• Modele o problema de forma que o conjunto de regras 
possa inferir as recomendações segundo as evidências. Como 
existem evidências compartilhadas, acrescente fatores de certeza 
para inferir múltiplas recomendações por ordem de certeza.
Gripe
• espirros
• febre
• dores no corpo
• coriza
• cansaço
Recomendação: 
vitamina C, repouso
Recomendação: 
antibiótico, repouso
Recomendação: 
antibiótico, xarope, 
repouso
Amidalite
• dor ao engolir
• febre
• amídalas inchadas e 
avermelhadas
Bronquite
• tosse seca
• febre
• cansaço
• amidalite
65INTELIGÊNCIA ARTIFICIAL
Problema 3: Diagnóstico financeiro
Um banco está disponibilizando aos seus clientes um empréstimo de R$20.000,00 para compra de au-
tomóveis. Os clientes que solicitam o empréstimo são avaliados pela instituição, verificando se tem ou não 
direito ao benefício.
• Apresente a modelagem dos fatos e das regras de produção para inferência da avaliação dos clientes.
• Escolha uma das ferramentas de desenvolvimento de sistemas especialistas deste capítulo e procure 
implementar o módulo de avaliação do problema financeiro.
Características essenciais de clientes habilitados
• Residência = Porto Alegre
• Renda acima de R$ 1500,00
• Outras características de clientes habilitados
• Emprego com carteira assinada
• Estado civil = casado, divorciado
• Casa própria
• Carro quitado
• Idade superior a 25 anos
66INTELIGÊNCIA ARTIFICIAL
ALGORITMOS 
GENÉTICOS
É possível encontrar soluções cada vez 
melhores a partir da evolução das gerações 
anteriores, baseando-se nos processos 
naturais de evolução. Computação evolutiva 
determina a sobrevivência dos melhores 
candidatos, construindo uma população de 
soluções ótimas.
67INTELIGÊNCIA ARTIFICIAL
Algoritmos genéticos representam um tipo de estratégia 
de busca de soluções em que os estados sucessores são gerados 
pela combinação de dois estados, ao invés da geração ocorrer 
tradicionalmente apenas sobre um único estado.
As estratégias de busca vistas até agora exploravam sistema-
ticamente espaços de busca, mantendo-se um ou mais caminhos 
na memória, registrando as alternativas exploradas em cada 
ponto do caminho. A solução encontrada é o caminho completo 
até o estado objetivo. Nem sempre a solução necessária é este 
caminho, problemas de otimização baseados em n-queens, por 
exemplo, tais como projeto de circuitos integrados, leiaute de 
instalações industriais, escalonamento de jornadas de trabalho, 
programação automática, otimização de rede de telecomunica-
ções, roteamento de veículos, gerenciamento de carteiras, entre 
outros, buscam uma configuração final otimizada das rainhas 
(ou recursos) e não a ordem em que elas são posicionadas.
Algoritmos