Inteligência Artificial e o Teste de Turing

Prévia do material em texto

Unidade 01 
Introdução a Inteligência Artificial, Problemas e Espaço de Problemas 
 
1. CONTEXTUALIZAÇÃO 
 
 A inteligência é uma capacidade que os seres humanos – cuja espécie é 
denominada “Homem Sábio” – possuem influenciados por todos os seus componentes 
ontológicos. Inúmeros autores formalizam o conceito de inteligência de maneiras 
distintas. De acordo com o dicionário Aurélio ‘[Aurélio, 2009], inteligência é a “faculdade 
ou capacidade de aprender, apreender, compreender ou adaptar-se; habilidade mental; 
perspicácia”. Jean Piaget [Piaget, 1982] define como ”aquilo que você usa quando não sabe 
o que fazer” e de acordo com Humberto Maturana [Maturana, 1998] “representa um 
atributo ou propriedade distintiva de alguns organismos”. 
 Formulados alguns conceitos de inteligência, é possível iniciar uma reflexão no 
sentido de quais características um determinado procedimento deve possuir, para ser 
considerado inteligente. Neste contexto, cabe destacar: 
 Aprendizado por experiência; 
 Utilização de conhecimento adquirido por experiência; 
 Capacidade de solucionar problemas mesmo na ausência de alguma informação; 
 Reação imediata perante uma nova situação; 
 Capacidade de determinar o que é relevante e o que não é; 
 Capacidade de raciocínio; 
 Capacidade de entender imagens visuais e processar e manipular símbolos; 
 Tem criatividade e imaginação; 
 Fazer uso de heurísticas, ou seja, saber identificar uma solução como satisfatória 
mesmo que esta não seja a melhor de todas as soluções possíveis. 
 A partir destas características, pode-se levantar o seguinte questionamento: qual a 
possibilidade/dificuldade de se criar sistemas inteligentes? Uma porta que se abre quando 
alguém se aproxima, um carro que avisa quando a porta está aberta ou quando o cinto de 
 
 
Título: Unidade 1 
 
Autora: Profª. M. Sc. Luciana De Nardin 
 
segurança não está colocado ou um computador que joga xadrez podem ser considerados 
procedimentos inteligentes? 
 Partindo deste questionamento a próxima seção introduz o conceito de 
inteligência artificial, suas aplicações e outras informações relevantes. 
 
2. A ÁREA DE INTELIGÊNCIA ARTIFICIAL 
 
 É interessante analisar a metáfora existente no nome inteligência artificial, uma 
vez que “inteligência” é uma capacidade exclusiva e natural do ser humano e, se torna 
contraditório, pensar nessa característica modelada artificialmente. 
 A Tabela 1 ilustra as diferenças no tratamento de determinadas informações entre 
a inteligência natural e artificial, e através destas diferenças percebe-se o quão complexo 
se torna construir sistemas verdadeiramente ou “naturalmente” inteligentes. 
 
 Natural Artificial 
Facilidade em adquirir uma grande quantidade de 
informação externa 
Alto Baixo 
Utilização de sensores para percepção (visão, audição, 
tato, cheiro) 
Alto Baixo 
Capacidade de ser criativo e tem imaginativo Alto Baixo 
Capacidade de aprender por experiência Alto Baixo 
Capacidade de armazenar dados detalhados Baixo Alto 
Capacidade de fazer cálculos complexos Alto Baixo 
Capacidade de adaptação Alto Baixo 
Capacidade de utilização de várias fontes de informação Alto Baixo 
Facilidade na transferência de informação Baixo Alto 
 
Tabela 1 Diferenças no Tratamento da Informação entre Inteligência Natural e Artificial 
 
2.1 Teste de Turing 
 
 Um dos primeiros testes a investigar questões de inteligência de máquina foi 
escrito em 1950 por Alan Turing [Turing, 1950] e foi chamado de Teste de Turing. Em 
sua proposta Turing sugeriu deixar de lado a maneira convencional de avaliar o conceito 
de inteligência, que era utilizando uma longa lista de requisitos mínimos, e propôs um 
teste que medisse o desempenho de uma máquina supostamente inteligente em 
comparação ao desempenho de um ser humano. 
 Este teste recebeu o nome de “jogo de imitação” e foi realizado da seguinte 
maneira: seleciona-se uma máquina “A” a ser avaliada e duas pessoas nomeadas “B” e “C”. 
A entidade C é o interrogador e as entidades A e B são os interrogados. As três entidades 
estão em locais distintos e distantes o suficiente, para que não haja nenhum contato visual, 
e se comunicam por meio de uma interface (computador). A tarefa do interrogador C é 
distinguir o computador (A) do ser humano (B) utilizando como referência apenas as 
respostas fornecidas às suas perguntas através do dispositivo de interface. Se o 
interrogador C não for capaz de distinguir a máquina do ser humano, pode-se considerar 
que a máquina A é inteligente. 
 A Figura 1 ilustra esta situação fisicamente. 
 
 
Figura 1 – Ilustração gráfica do Teste de Turing 
 
 A situação proposta por Turing neste teste assegura que o interrogador não será 
influenciado pela aparência da máquina. Dessa forma, o interrogador está livre para 
perguntar qualquer coisa (direta ou indireta) que contribua para descobrir quem é a 
máquina. 
 Luger [Luger, 2004] sugere dois testes para identificar pontos estratégicos em 
cada uma das entidades. Primeiro, pode-se solicitar que as duas entidades realizem um 
determinado cálculo aritmético bastante complexo, é fato que a máquina será mais rápida 
e com probabilidade de acerto maior do que a do ser humano; em contrapartida, a 
máquina pode perceber que este seja um bom momento de “deixar” de obter a resposta 
correta com o intuito de se parecer com o ser humano. O segundo teste proposto é de 
natureza emocional, pedindo, por exemplo, que ambas as entidades façam uma análise 
sobre um determinado poema ou uma obra de arte, uma vez que esta estratégia irá 
requerer que o computador possua conhecimentos sobre sensações emocionais inerentes 
aos seres humanos. 
 Na próxima seção serão apresentados uma série de problemas que apresentam 
características bastante complexas. Sobre tais problemas serão levantados 
questionamentos que buscam destacar as dificuldades apresentadas por cada uma das 
situações. 
 
2.2 Problemas Encontrados no Desenvolvimento de Aplicações 
 
a) Controle de robôs: como obter navegação segura e eficiente, estabilidade, 
manipulação final e versátil? Como tratar o comportamento dos robôs em 
ambientes dinâmicos e imprevisíveis? Exemplos: HAZBOT (robô para 
ambientes com atmosfera inflamável), robô aspirador etc. 
Como tratar questões referentes à visão, raciocínio, planejamento, controle, 
comunicação e aprendizagem? Exemplo: RoboCup (futebol de robôs). 
b) Jogos e histórias interativas: como modelar o ambiente físico e o 
comportamento/personalidade dos personagens? Como permitir boa 
interação com o usuário? Exemplos: The Sims 3 (2009), Fifa Soccer etc. 
c) Automação de sistemas complexos: como modelar os componentes do 
sistema e lhes dar autonomia? Como assegurar uma boa comunicação e 
coordenação entre esses componentes? 
d) Busca de informações na web: como localizar a informação relevante? 
e) Recomendação de produtos: como fazer recomendações personalizadas de 
produtos? Como modelar os perfis dos compradores? 
f) Personalidades virtuais (verbots): como modelar indivíduos que tenham 
capacidade de conversar e trocar informações com humanos? Exemplo: 
Cybelle (www.cybelle.cjb.net) 
g) Previsão: como prever o valor do dólar ou o clima de amanhã? Quais dados 
são realmente relevantes? Existem comportamentos recorrentes? 
h) Detecção de intrusão e filtragem de spams: como saber se uma mensagem é 
lixo ou se ela realmente interessa? Como saber se um dado comportamento de 
um usuário é suspeito e como lidar com isto? 
i) Sistemas de controle: como brecar o carro sem as rodas deslizarem em 
função da velocidade, atrito etc.? Como focar a câmera fotográfica em função 
da luminosidade, distância etc.? Como ajustar a temperatura da água da 
máquina de lavar em função da quantidade de roupa, fluxo de água etc.? 
http://www.cybelle.cjb.net/
j) Interface: como dar ao usuário a ajuda de que ele realmente precisa? Como 
interagir (e quem sabeaté navegar) com celular sem ter de digitar nada 
(hands-free)? 
 Todos os problemas levantados apresentam as seguintes características em 
comum: 
 Grande complexidade devido ao grande número, a variedade e a natureza das 
tarefas; 
 Não possuem solução algorítmica, mas, tem-se grande conhecimento sobre o 
problema; 
 Envolve a modelagem do comportamento de um ser inteligente que seja capaz 
de aprender, possuir iniciativa etc. 
 Utilizando estes problemas, pode-se visualizar o quão importante é se 
implementar um sistema supostamente inteligente, mesmo que se tenha certa dificuldade 
em pensar em um modelo que seja capaz de se comparar à inteligência dos humanos em 
toda sua amplitude; já que, para se dizer que um programa raciocina como um ser 
humano, é necessário penetrar nos componentes reais que envolvem a inteligência. 
Componentes como vontades, sentimentos, percepções, sensações – fatores que 
influenciam os seres humanos no processo de tomada de decisão. Muitas vezes, se está 
diante de situações que colocam a emoção descrita por Pascal contra a razão defendida 
por Descartes. 
 Sistemas artificialmente inteligentes possuem limitações, mas, também podem 
apresentar inúmeras vantagens. 
 A partir dessas considerações é possível contextualizar formalmente o conceito de 
inteligência artificial, entretanto, vale destacar que cada autor exerce essa tarefa de 
maneira distinta. A Tabela 2 destaca algumas dessas definições. 
 
[Luger & Stubblefield, 1993] 
Ramo da ciência da computação dedicado à automação de 
comportamento inteligente. 
[Nilsson, 1998] 
Conjunto de técnicas para a construção de máquinas “inteligentes” 
capazes de resolver problemas que requerem inteligência humana. 
[Winston, 1992] 
Tecnologia de processamento de informação que envolve processos 
de raciocínio, aprendizado e percepção. 
[Rich & Knight, 1994] 
Área de pesquisa que investiga formas de habilitar o computador a 
realizar tarefas nas quais, até o momento, o ser humano tem um 
melhor desempenho. 
 
Tabela 2 Definição da IA de acordo com alguns autores 
 
2.3 Categorias de IA 
 
 Os sistemas que usam IA podem ser categorizados em quatro grandes grupos. São 
eles: 
a) Sistemas que pensam como humanos: possuem uma abordagem cognitiva e 
tentam expressar a “teoria da mente” em um programa de computador. Nesta 
categoria, a automação das atividades está associada com o pensamento 
humano e não se preocupa em resolver problemas com precisão, mas, procura 
simular a forma com que os seres humanos resolvem seus problemas. Como 
exemplos podem-se citar: processo de tomada de decisão, solução de 
problemas e aprendizagem [Simon & Newell, 1961]. 
b) Sistemas que pensam racionalmente: tais sistemas seguem as leis do 
pensamento utilizando silogismos, que são padrões para estruturas de 
argumentos que sempre fornecem conclusões corretas partindo do princípio 
de que as premissas estão corretas. Neste contexto, estão as leis do 
pensamento que dão origem à lógica e que governam a mente. Porém, esse 
modelo apresenta algumas desvantagens tais como: 
- Dificuldade em representar o conhecimento informal em um modelo formal 
como a notação lógica exige; 
- Dificuldade em representar incerteza; 
- Mesmo em problemas descritos por poucos fatos torna-se impraticável para 
resolver problemas. 
c) Sistemas que agem como humanos: o exemplo clássico de sistemas desta 
categoria é o teste de Turing. Neste modelo procura-se fazer com que o 
computador se comporte como um ser humano realizando funções que 
requerem inteligência quando realizadas por pessoas conforme visto 
anteriormente na seção 2.1. 
d) Sistemas que agem racionalmente: neste tipo de sistema se encaixam os 
agentes. Um agente é uma entidade que percebe o meio através de sensores e 
age por meio de efetuadores. No entanto, espera-se que um agente não se 
comporte como um mero “programa”, uma vez que deve possuir características 
mais “evoluídas” que simples programas. Entre essas características podemos 
destacar: adaptar-se a mudanças, perceber o ambiente, raciocinar sobre o 
estado atual e o estado esperado, entre outras. 
 
2.4 Áreas de Apoio para a IA 
 
 Inúmeras áreas contribuíram com ideias, pontos de vista e técnicas para a 
fundamentação da IA. A Figura 2 ilustra essas áreas. 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 2 – Áreas de apoio para a IA 
 
2.5 Subáreas da IA 
 
 A Figura 3 mostrada a seguir e extraída de [Souto, 2009] mostra algumas das 
subáreas da IA. 
 
Figura 3 – Subáreas da IA (Fonte: [Souto, 2009]). 
 
 
IA 
Psicologia 
Biologia 
Ciência da 
Computação 
Linguística 
Engenharia 
Filosofia 
Lógica 
Matemática 
 
2.6 Evolução histórica da IA 
 
 No verão de 1956 no decorrer de dois meses, foi realizado em Dartmouth um 
seminário denominado Workshop Dartmouth College que contou com dez participantes de 
todo mundo incluindo representantes de Princeton, IBM e MIT. Deste seminário, o fruto 
mais importante foi um acordo para adotar o nome sugerido por John McCarthy de 
Inteligência Artificial, para nominar a área de pesquisa que tenta construir máquinas 
que funcionem de forma autônoma em ambientes complexos e, muitas vezes, variáveis. 
Nas próximas seções serão descritos os principais acontecimentos históricos na área de IA 
conforme períodos e fatos apresentados em [Russell & Norvig, 2004]. 
 
2.6.1 A gestação da IA (1943-1955) 
 
 O primeiro trabalho reconhecido na área de IA foi um modelo de neurônios 
artificiais realizado por Warren McCulloch e Walter Pitt em 1943. 
 No começo dos anos 50, Marvin Minsky e Dean Edmonds construíram o primeiro 
computador baseado em redes neurais. Ironicamente, posteriormente, Minsky provou 
teoremas importantes que levaram a descrença de redes neurais devido a algumas 
limitações. 
 
2.6.2 O entusiasmo inicial com a IA (1952-1969) 
 
 No início da década de 50, Newell e Simon desenvolveram o General Problem 
Solver (GPS) cujo objetivo era imitar protocolos humanos de resolver problemas. Dessa 
forma, o GPS foi o primeiro modelo a incorporar a abordagem Pensar como Humanos 
descrita anteriormente na seção 2.3. 
 Em 1952, Arthur Samuel escreveu um conjunto de programas que incorporavam o 
princípio do aprendizado para jogar damas e contrariou o que era senso comum na época, 
o fato de que os programas só eram capazes de fazer aquilo para o qual tinham sido 
programados. Um fato interessante percebido foi que os programas rapidamente 
aprendiam a jogar melhor do que seus criadores. 
 Em 1958, no MIT, John McCarthy definiu a linguagem de alto nível LISP que se 
tornaria a linguagem predominante em IA. Depois disso, em 1963 J. A. Robinson descobriu 
o método de resolução (um algoritmo completo para demonstração de teoremas para a 
lógica de primeira ordem), a partir desta descoberta, a linguagem PROLOG estava a 
caminho. 
 Com Marvin Minsky no MIT, as pesquisas na área de redes neurais voltaram a 
florescer. 
 
2.6.3 Uma dose de realidade (1966-1973) 
 
 A principal barreira que muitos projetos de IA encontraram foi o fato de que os 
métodos eram eficientes, para demonstrar um ou dois exemplos simples, e falhavam 
terrivelmente quando foram testados com uma seleção maior de problemas ou problemas 
mais complexos. 
 Outras três dificuldades que podem ser destacadas são: 
 Os primeiros programas tinham pouco ou nenhum conhecimento do assunto 
que eles tratavam e tinham sucesso apenas através de manipulações sintáticas 
muito simples (exemplo: ELIZA em 1965). 
 A intratabilidade de muitos problemas que estavam tentando ser resolvidos 
pela IA (problemas NP - Completos X hardwares mais rápidos). 
 As limitações das estruturas básicas usadas para gerar comportamento 
inteligente. 
 
2.6.4 Sistemas Baseados em Conhecimento: a chave para o poder? (1969-1979) 
 
 O método de resolução de problemas, usado na primeira década na IA, foi o 
mecanismo de busca dopropósito geral que buscava reunir passos básicos de raciocínio 
com o intuito de encontrar soluções completas. Este modelo foi também chamado de 
método fraco, uma vez que usava pouca informação sobre o domínio do problema. 
Porém, apresentava desempenho paupérrimo quando o domínio do problema era mais 
amplo e complexo. 
 Nesta época, Ed Feigenbaum e outros em Stanford começaram a investigar uma 
nova metodologia de sistemas especialistas. Como resultado desta investigação foi 
desenvolvido o DENDRAL (1969) e seu objetivo era inferir a estrutura molecular a partir 
das informações fornecidas através de um espectrômetro de massa. 
 Com o crescimento das aplicações inspiradas no mundo real, cresceu a demanda 
por esquemas de representação de conhecimento alternativos tais como: programação 
lógica e frames. 
 
 
 
2.6.5 A IA se torna comercial (1980-1988) 
 
 Com as pesquisas já voltadas para a área comercial, o primeiro sistema especialista 
que apresentou sucesso comercial se chamava R1 e tinha por função ajudar a configurar 
ordens para novos computadores e, em 1986, seu uso levava a uma economia de cerca de 
40 milhões de dólares/ano. 
 Em 1981, os japoneses anunciaram o projeto “Quinta Geração” cujo objetivo era 
construir computadores inteligentes que rodavam Prolog. O crescimento da indústria de 
IA neste período saiu da casa dos milhões para a casa dos bilhões de dólares. 
 
2.6.6 O retorno das Redes Neurais (de 1986 até a atualidade) 
 
 Após a descrença das redes neurais do início da década de 50, a ciência da 
computação negligenciou o campo das redes neurais, mas as pesquisas continuaram em 
outros campos, especialmente na física. 
 Ao mesmo tempo, algumas desilusões sobre a aplicabilidade de sistemas 
especialistas começaram a surgir. 
 A partir de 1986, novas técnicas surgiram (destacando: algoritmos genéticos e 
sistemas nebulosos) e inúmeras revoluções ocorreram na área de robótica, visão por 
computador, aprendizado de máquina, representação do conhecimento, reconhecimento 
de voz e outros. 
 
2.7 Paradigmas da IA 
 
 Um paradigma pode ser definido como um modelo, uma representação de um 
padrão ou uma referência inicial para estudos e pesquisas; e um paradigma se distingue de 
outro basicamente em três aspectos. São eles: 
 - a forma de adquirir o conhecimento; 
 - a forma de representar o conhecimento: de entrada, de saída e interno; 
 - a forma de raciocinar utilizando esse conhecimento. 
 As pesquisas em IA se dividem em três grandes linhas ou paradigmas. São eles: 
Paradigma Cognitivo ou simbólico, Conexionista ou subsimbólico e Evolucionário. Além 
destes três, podemos utilizar ainda os chamados paradigmas híbridos que são aqueles que 
associam mais de um paradigma dos citados anteriormente. 
 Nas próximas subseções serão descritos cada um deles detalhadamente. 
 
2.7.1 Paradigma Cognitivo ou Simbólico 
 
 Este paradigma se fundamenta na hipótese de que a inteligência é consequência de 
uma manipulação formal de símbolos. Basicamente, se inspira nos processos mentais de 
alto nível, para realizar a representação do conhecimento. Para isso, é preciso: 
 Identificar o conhecimento do domínio; 
 Representá-lo utilizando uma linguagem formal de raciocínio; 
 Implementar um mecanismo de inferência para raciocinar sobre este 
conhecimento e produzir novos. 
 Este paradigma apresenta como principal vantagem a versatilidade; em 
contrapartida, é inadequado para: 
 Raciocínio para execução de ações reflexas (por exemplo: controle dos motores 
efetuadores de um robô); 
 Raciocínio com conhecimento incerto ou que apresente muitos ruídos; 
 Raciocínio que envolva cálculos ou probabilidades. 
 Algumas das técnicas que fazem parte deste paradigma são: a lógica proposicional, 
a lógica de primeira ordem e sistemas baseados em regras. Estas três técnicas serão 
estudadas detalhadamente nas Unidades 05 e 06 desta disciplina. 
 
2.7.2 Paradigma Conexionista ou Sub-Simbólico 
 
 Este paradigma se fundamenta basicamente no funcionamento do cérebro humano 
e tem como princípio que, a partir do momento em que for feito um modelo preciso do 
cérebro humano, este modelo será capaz de reproduzir a inteligência que um cérebro real 
possui. 
 Neste contexto, o conhecimento é representado como padrões de atividades em 
um modelo de rede com pequenas unidades de processamento individual distribuído 
através de conjuntos ou camadas de neurônios. A solução neste paradigma será 
encontrada de maneira paralela, uma vez que todos os neurônios dentro de um conjunto 
ou de uma camada processam suas entradas de maneira simultânea e independente 
[Luger, 2004]. 
 A grande vantagem apresentada por este paradigma é que seus algoritmos 
geralmente são treinados, ao invés de terem que ser pré-programados para todas as 
situações. Entre as tarefas que o paradigma conexionista se mostra adequado [Luger, 
2004] se destacam: 
 Sistemas classificatórios: devem decidir a qual categoria ou grupo pertence um 
determinado valor de entrada; 
 Reconhecimento de padrões: deve identificar uma estrutura ou padrão em um 
conjunto de dados; 
 Predição: deve identificar, por exemplo, a partir de um grupo de sintomas qual 
a doença em potencial; 
 Otimização: deve encontrar a “melhor” solução dado um conjunto de 
restrições; 
 Filtragem de Ruídos: deve identificar e separar o que é realmente sinal do que 
é ruído. 
Para ilustrar o funcionamento de uma rede neural, é fundamental conhecer o 
funcionamento de um neurônio natural e como os neurônios estão interligados formando 
uma rede que é fonte inspiradora para as redes neurais artificiais. 
A Figura 4 ilustra um neurônio natural. 
 
Figura 4 – Neurônio Natural 
 
 No neurônio mostrado na Figura 4 é possível visualizar as sinapses que são o 
ponto de ligação entre dois neurônios. Essa conexão não acontece fisicamente, pois há um 
espaço denominado fenda sináptica, onde ocorre a ação dos neurotransmissores, que são 
substâncias liberada pelos axônios, que por sua vez atravessam a fenda e estimulam os 
receptores pós-sinápticos. Através da ação dos neurotransmissores é que acontece a 
transmissão de um impulso nervoso (ou informação) de um neurônio para outro. 
 Uma rede neural busca representar em modelo de maneira artificial, assim, um 
neurônio artificial padrão está representado na Figura 5. 
 
 
Figura 5 – Neurônio Artificial 
 
 Neste neurônio pode-se destacar: 
 Sinais de entrada (s1, sj, sn): são dados que podem vir do ambiente ou ainda 
da ativação de outros neurônios. Geralmente, as entradas são discretas, do 
conjunto {0,1} ou {-1,1} ou ainda, números reais. 
 Ligações sinápticas (w1i, wji, wni): são as ligações entre os neurônios. Cada 
ligação deve ter associada a ela um valor (peso), que irá representar a sua força de 
conexão, assim, os estímulos de entrada (s1, sj, sn) serão multiplicados pelos 
respectivos pesos da ligação correspondentes de forma a gerar um sinal positivo 
(excitatório) ou negativo (inibitório). 
 Combinador Linear (∑): realiza o somatório dos sinais produzidos através do 
produto entre os pesos sinápticos e as entradas fornecidas ao neurônio. 
 Função de limiar (∫): a saída do neurônio (s(i)) será definida através da 
função de ativação que calcula o estado final do neurônio determinando – quanto o 
nível de ativação do neurônio está acima ou abaixo de um determinado valor. 
Dessa forma, que o objetivo principal desta função é produzir o estado de 
ligado/desligado dos neurônios reais [Luger, 2004]. 
 Uma rede neural artificial possui inúmeros neurônios conectados entre si e 
organizados em camadas. A camada de entrada e a camada de saída mostradas na Figura 6 
são fundamentais. As camadas escondidas ou subcamadas serão definidas de acordo com a 
topologia que estabelece o padrão de conexões entre os neurônios individuais. A Figura 6 
ilustra essas informações. 
 
 
Figura 6 – Modelobásico de uma Rede Neural 
 
2.7.3 Paradigma Evolucionista 
 
 Neste paradigma não há nada de cognitivo para a solução dos problemas. A fonte 
de inspiração é o paradigma neodarwiniano da evolução das espécies. 
 Em seu livro a Origem das Espécies Charles, Darwin faz a seguinte explanação: 
“Que limites podemos impor a este poder, que age durante longas eras e escrutina 
rigidamente toda a constituição, estrutura e hábitos de cada criatura – favorecendo o que 
é bom e rejeitando o que é ruim? Não vejo limites a este poder de adaptar 
vagarosamente e maravilhosamente cada forma às mais complexas relações de vida”. 
 Este é o princípio básico da teoria da evolução das espécies, no qual o paradigma 
evolucionista se inspira e que tem as seguintes características: 
 A diversidade é gerada através de cruzamentos entre indivíduos e mutações 
em indivíduos; 
 Os seres mais adaptados aos seus ambientes sobrevivem através da seleção 
natural das espécies; 
 As características genéticas de tais indivíduos são herdadas pelas próximas 
gerações. 
 
3. SISTEMA DE PRODUÇÃO 
 
 Um sistema de produção de acordo com Nilsson [Nilsson, 1986] é um formalismo 
computacional que tem se provado importante em IA e consiste de três partes: base de 
dados, regras de produção e estratégias de controle. A base de dados deverá conter todas 
as informações de maneira estruturada sobre um determinado problema. O conjunto de 
regras de produção opera sobre a base de dados e são representadas por um par do tipo 
condição-ação. A condição da regra é um padrão que determina quando aquela regra pode 
ser aplicada para um caso específico do problema em questão, e a ação define o passo da 
solução do problema associado [Luger, 2004]. Por fim, têm-se as estratégias de controle 
cujas funções primordiais são: escolher as regras aplicáveis e identificar quando um 
estado meta foi alcançado. 
 Tais partes podem ser representadas pelo esquema gráfico mostrado na Figura 7 
que ilustra como acontece a interação. 
 
Figura 7 – Esquema gráfico de um sistema de produção 
 
 Um exemplo muito simples de um sistema de produção pode ser mostrado 
utilizando o exemplo das Torres de Hanói. O problema das Torres de Hanói consiste em 
uma base com três pinos, em um dos pinos está organizado um conjunto de três discos (ou 
mais) em ordem crescente de diâmetro de cima para baixo como mostrado na Figura 8. O 
problema consiste em passar todos os discos do pino atual para um segundo pino 
qualquer utilizando o terceiro pino como auxiliar no menor número possível de jogadas e 
sem violar as seguintes regras: 
 Um disco maior nunca pode ser colocado sobre um disco menor; 
 Só é permitido mover um disco de cada vez; 
 Um disco deve estar sempre em um dos três pinos ou em movimento. 
 
Figura 8 – Ilustração gráfica do problema das Torres de Hanói 
 
 Conhecendo o problema é possível modelar o sistema de produção da seguinte 
forma: 
 Base de dados (representação): 
 - x representa a lista de discos no pino A 
 - y representa a lista de discos no pino B 
 - z representa a lista de discos no pino C 
 
Estado inicial = (x, y, z) = (123, 0, 0) 
 
 Regras de Produção (representação ótima e sequencial) 
 R1 = mover disco do pino A para o pino C 
 R2 = mover disco do pino A para o pino B 
 R3 = mover disco do pino C para o pino B 
 R4 = mover disco do pino A para o pino C 
 R5 = mover disco do pino B para o pino A 
 R7 = mover disco do pino B para o pino C 
 R8 = mover disco do pino A para o pino C 
 Estratégias de Controle 
 Sucesso = (0, 0, 123) 
Fracasso = (x, y, a), (x, a, z), (a, y, z) com a = vwu ou vw onde v > w, ou seja, 
qualquer situação do tipo (132, 0, 0) onde um disco maior esteja sobre um 
disco menor. 
 
Problema  Como evitar repetição? 
 Como buscar sucesso? Qual a melhor estratégia? 
 
4. CONSIDERAÇÕES SOBRE A BUSCA EM UM ESPAÇO DE ESTADOS 
 
 Um problema em IA pode ser definido em termos de um espaço de estados 
possíveis que inclui um estado inicial e um final que representa o estado objetivo ou meta. 
Por exemplo, se a necessidade é ir de Poços de Caldas a Belo Horizonte, então o estado 
inicial é Poços de Caldas, o estado final é Belo Horizonte, e o espaço de estados será todas 
as cidades da região. 
 Para realizar uma busca em um espaço de estados, é fundamental definir os 
seguintes itens. São eles: 
a) Definição do objetivo: o objetivo no contexto de cada problema é uma 
propriedade abstrata e é representada por um ou mais estados do conjunto de 
estados possíveis. Por exemplo: condição de xeque-mate em um jogo de xadrez 
ou estar em Belo Horizonte; 
b) Aplicação das regras de produção: as regras de produção representam um 
conjunto de ações que permitam passar de um estado para outro. Por exemplo: 
mexer uma peça em um jogo de xadrez ou dirigir de uma cidade até outra; 
c) Identificação da solução: a solução será representada por um caminho 
(sequência de ações) que conduz do estado inicial até o estado final (objetivo); 
d) Espaço de estados: é o conjunto de todos os possíveis estados alcançáveis a 
partir do estado inicial através de qualquer sequência de ações. 
 Utilizando como exemplo o problema do 8-Number Puzzle ilustrado na Figura 9 (a) 
e (b), cujo objetivo é colocar os números em ordem crescente deixando o espaço em 
branco na última posição, é possível definir todos os itens necessários, para que uma 
busca aconteça em um espaço de estados. 
 
4 5 8 
 1 6 
7 2 3 
Figura 9 (a) – Estado inicial do 8-Number Puzzle 
 
1 2 3 
4 5 6 
7 8 
Figura 9 (b) – Estado final do 8-Number Puzzle 
 
 Sendo: 
 Espaço de estados: cada possível configuração do tabuleiro; 
 Estado inicial: qualquer um dos estados possíveis; 
 Estado final: número ordenados com o espaço em branco na posição [3,3]; 
 Regras de produção: mover o espaço em branco (esquerda, direita, para cima 
e para baixo); 
 Custo do caminho: cada passo custa um assim, o custo do caminho é o número 
de passos até encontrar a solução. 
 A partir da definição do sistema de produção para o 8-Number Puzzle é possível 
esquematizar uma árvore de busca mostrada na Figura 10, onde as regras de produção são 
as seguintes: 
a) R1 = mover branco para cima 
b) R2 = mover branco para a direita 
c) R3 = mover branco para baixo 
d) R4 = mover branco para esquerda 
 
Figura 10 – Árvore de busca para o 8-Number Puzzle 
 Observando a Figura 04 é possível perceber que a partir do estado inicial denotado 
como raiz da árvore, três novos estados são possíveis a partir da aplicação das regras R1, 
R2 ou R3. A R4 não pode ser aplicada, pois não é possível realizar o movimento de mover o 
espaço em branco para a esquerda. Se for aplicada a regra R1, uma mudança de 
configuração no tabuleiro acontece e um novo estado é gerado, a partir deste estado é 
possível aplicar as regras R2 ou R3. Dessa forma, espera-se que pelo menos uma solução 
possível seja encontrada em uma das folhas da árvore. 
 
5 ESTRATÉGIAS DE CONTROLE 
 
 Como visto brevemente na seção 3, as estratégias de busca têm como principais 
funções: 
 Selecionar a ordem de aplicação das regras. 
 Registrar qual foi a sequencia de regras aplicadas e o estado associado a cada 
regra. 
 Identificar quando o estado meta foi atingido. 
 Além destas, é também sua responsabilidade sempre apresentar “movimento” 
após a aplicação de uma regra, com isso evitando loopings. 
 De acordo com [Russell & Norvig, 2004], a saída de um algoritmo consiste 
basicamente em uma falha ou sucesso, porém, alguns algoritmos podem ficar em loopings 
infinitos e nunca retornarem uma saída. Dessa forma, são sugeridos quatro aspectos que 
deverão ser analisados para escolha de uma estratégia de controle. São eles: 
1. Completeza: ou seja, o algoritmo oferece garantia de encontrar sempre uma 
solução quando esta existir? 
2. Otimização: a estratégia encontra a solução ótima? Considerando como soluçãoótima aquela que tiver o menor custo de caminho entre todas as soluções. 
3. Complexidade de tempo: quanto tempo o algoritmo leva para encontrar uma 
solução? 
4. Complexidade de espaço: quanta memória é necessária para executar a 
busca? 
Nas próximas seções serão apresentadas algumas estratégias de controle divididas 
em duas categorias: Irrevogáveis e por Tentativa. 
 
5.1 Estratégias de Controle Irrevogáveis 
 
 O exemplo clássico deste tipo de estratégia é o algoritmo Hill Climbing ou Subida da 
Encosta. Este algoritmo é a técnica de busca local mais básica; é baseado no método do 
gradiente (otimização) e utiliza uma função heurística para selecionar as regras. Uma 
regra só será selecionada se produzir um estado na base de dados que gere um valor 
maior ou igual ao valor atual para a função heurística. Ele é repetitivo e se move de forma 
contínua no sentido do valor – isto é, encosta acima e só termina quando alcança um “pico” 
onde nenhum vizinho tenha valor mais alto. Se nenhuma das regras permitir um aumento 
no valor da função, uma regra será selecionada arbitrariamente de forma que também não 
diminua o valor; caso não haja nenhuma regra que possa satisfazer isso, o processo é 
cancelado. 
 Sua característica principal, quando comparado a métodos por tentativa, é o fato 
de não examinar antecipadamente valores de estados além dos vizinhos imediatos ao 
estado atual. De acordo com [Russel & Norvig, 2004], o funcionamento deste algoritmo é 
equivalente a “tentar alcançar o cume do Monte Everest em meio a um nevoeiro denso 
durante uma crise de amnésia”. 
 Este algoritmo é também conhecido como busca gulosa local, uma vez que opta por 
um estado vizinho sem levar em consideração para onde irá depois dele. 
 Com o intuito de auxiliar a compreensão de seu funcionamento, será utilizado um 
problema já citado anteriormente, o 8-Number Puzzle com a diferença que o estado final 
serão os números ordenados, mas, o espaço em branco deverá estar na posição central 
([2,2]). Uma função precisa ser definida para avaliar a regra a ser aplicada, dessa forma, a 
função será representada pelo negativo do número de peças que estejam fora do lugar. 
 A Figura 11 mostra o estado inicial e o estado final (ou estado meta) que deverá ser 
atingido. 
 
Figura 11 – Estado inicial e estado final (ou meta) 
 Para o estado inicial, o valor da função é f= - 4 e representa o negativo das quatro 
peças que estão fora do lugar, sendo elas: 1, 2, 6 e 8. 
 A partir do estado inicial são possíveis os seguintes movimentos: mover branco 
para a esquerda (f = - 5), mover branco para a direita (f = - 5) e mover branco para cima (f 
= - 3). Dessa forma, a única regra que faz com que o valor de f aumente é mover branco 
para cima. A Figura 12 ilustra o novo estado gerado a partir da aplicação da regra. 
 
 
Figura 12 – Novo estado gerado com três peças fora do lugar 
 Considerando o novo estado mostrado na Figura 12 são possíveis os seguintes 
movimentos: mover branco para esquerda (f = - 3), mover branco para cima (f = - 3), 
mover branco para a direita (f = - 4) e mover branco para baixo (f = - 4). Neste ponto, não 
existe nenhuma regra que aumente o valor da função, mas, existem duas regras que 
mantêm o valor da função estável; assim, uma dessas duas regras será aplicada. Se a regra 
escolhida for a que move o espaço em branco para cima, o estado atual será o mostrado na 
Figura 13. 
 
Figura 13 – Novo estado gerado com três peças fora do lugar 
 
 A partir do estado mostrado na Figura 13 são possíveis os seguintes movimentos: 
mover o branco para a esquerda (f = - 2), mover o branco para a direita (f = - 4) e mover 
branco para baixo (f = - 3). Uma vez que movendo o branco para a esquerda a função 
melhora seu valor, este será o movimento escolhido e o novo estado é mostrado na Figura 
14. 
 
Figura 14 – Novo estado gerado com duas peças fora do lugar 
 
 Considerando o estado atual mostrado na Figura 14 são possíveis os seguintes 
movimentos: mover branco para a direita (f = - 3) e mover branco para baixo (f = - 1). Com 
o objetivo de melhorar a função o movimento de mover o branco para baixo é escolhido, e 
o novo estado é mostrado na Figura 15. 
 
Figura 15 – Novo estado gerado com uma peça fora do lugar 
 
 A partir do estado mostrado na Figura 15 três movimentos são possíveis: mover 
branco para cima (f = - 2), mover branco para a direita (f = 0) e mover branco para baixo (f 
= - 2). Dentre as opções disponíveis será escolhido o movimento do branco para a direita, 
com isso, o valor da função atinge zero, ou seja, nenhuma peça está fora do lugar e se 
atinge o estado meta representado anteriormente na Figura 11. 
 A sequência de passos que fizeram com que fosse atingido o estado meta é 
mostrada na Figura 16. 
 
 
Figura 16 – Sequência de passos realizados para atingir o estado meta 
 Apesar do algoritmo Subida da Encosta se mostrar eficiente em algumas situações, 
ele apresenta algumas limitações e pode ficar paralisado pelas seguintes razões: 
 Máximo local: é um estado melhor do que seus vizinhos, porém, pior que o 
máximo global. Os algoritmos de subida da encosta que atingirem a vizinhança 
de um máximo local serão deslocados para cima em direção ao pico, porém, 
depois ficarão estagnados lá sem ter para onde ir; 
 Pico: os picos são uma sequência de máximos locais que torna difícil a 
navegação para este tipo de algoritmo; 
 Platô: é uma área do espaço de estados em que a topologia é plana, ou seja, a 
função de avaliação tem sempre o mesmo valor e não é possível progredir. Um 
algoritmo da subida da encosta pode ser incapaz de encontrar a saída de um 
platô. 
 O sucesso deste tipo de algoritmo depende muito da topologia do espaço de 
estados e, mesmo com métodos eficientes que são usados para minimizar suas limitações, 
a Subida da Encosta (Hill Climbing) pode não se mostrar eficiente. 
 
5.2 Estratégias de Controle por Tentativa 
 Neste tipo de busca é feita uma provisão para aplicação de outras regras, uma vez 
que é uma estratégia de controle por tentativa. Nas estratégias de controle por tentativa 
serão estudados dois tipos: backtracking (ou retrocesso) e a busca em grafo. 
5.2.1 Backtrack 
 Em sua execução uma regra é selecionada e, caso a aplicação desta regra produza 
um estado inadequado ou não permita chegar ao estado meta, ocorre um retrocesso, e 
outra regra é selecionada e aplicada. 
 Em suas características principais podemos destacar o fato de exigir pouco 
conhecimento para a seleção das regras já que podem ser selecionadas de acordo com 
algum esquema arbitrário, porém, é mais eficiente quando a seleção das regras não é 
arbitrária, mas, utiliza alguma informação para a seleção. A chave em sua execução é o fato 
deste ser um procedimento recursivo. 
 O algoritmo base da sua execução é o seguinte: 
 1. Se TERM(DATA) retorne NIL 
 Neste caso, TERM é um predicado verdadeiro para argumentos que satisfazem a 
condição terminal (estado meta) do sistema de produção. Se a terminação for bem 
sucedida, a lista vazia NIL é retornada. 
 2. Se DEADEND(DATA) retorne FAIL 
 DEADEND é um predicado verdadeiro para argumentos que são conhecidos por 
não estar em um caminho que conduza a solução. Nesse caso, o procedimento retorna 
FAIL. 
 3. RULES  APPRULES(DATA) 
 APPRULES é uma função que computa as regras aplicáveis e seus argumentos e os 
ordena de maneira arbitrária ou de acordo com uma função heurística (de forma que a 
melhor solução esteja no topo da lista) 
 4. LOOP: Se NULL (RULES) retorne FAIL 
 Neste ponto, tem início um looping de forma que se não há mais regras a ser 
aplicadas, o algoritmo retorna FAIL. 
 5. R  FIRST (RULES) 
 A melhor das regras aplicáveis é escolhida. 
 6. RULES  TAIL (RULES) 
 A lista de regras aplicáveis é diminuída através da remoção da regra escolhida e 
aplicada no passo 5. 
 7. RDATA  R(DATA) 
 A regra R é aplicada paraproduzir uma nova base de dados. 
 8. PATH  BACKTRACK (RDATA) 
 A função BACKTRACK é chamada recursivamente na nova base de dados. 
 9. Se PATH = FAIL retorne para LOOP 
 Se a chamada recursiva falha, tente outra regra. 
 10. Retorne CONS(R, PATH); 
 Caso contrário, passe a frente a lista bem sucedida de regras, adicionando a regra R 
na frente da lista PATH através do procedimento CONS. 
 Para ilustrar o funcionamento de um algoritmo do tipo Backtrack, a seguir é 
apresentado e resolvido o problema das Quatro Rainhas; é dado um tabuleiro 4 x 4 
posicionar quatro rainhas de forma que nenhuma rainha ataque qualquer outra, sendo 
que uma rainha ataca qualquer rainha situada na mesma linha, mesma coluna ou mesma 
diagonal. 
 O primeiro passo é definir um sistema de produção para o problema. Dessa forma, 
a Figura 17 ilustra o estado inicial que é o tabuleiro vazio. 
 
Figura 17 – Estado inicial do problema das Quatro Rainhas 
 
 As regras de produção serão definidas da seguinte forma: 
 Rij  representam as posições no tabuleiro, sendo que i representa as linhas, j 
representa as colunas e ambos podem variar de 1 a 4. 
 Condição: 
 - Se i = 1, significa que não há nenhuma rainha no tabuleiro. 
 - Se 1 < i <= 4, significa que há rainha na linha (i – 1) 
 Ação: Colocar uma rainha na linha i e coluna j (Rij). Por exemplo, R12 significa 
colocar uma rainha na linha 1 coluna 2. 
 A estratégia de controle utilizada será o backtrack com seleção, sendo que a 
seleção será realizada através de uma função heurística que fará a ordenação pelo número 
característico da diagonal. Neste caso, a cada posição do tabuleiro será associado um 
número que representa o tamanho da maior diagonal conforme pode ser visto na Figura 
18. 
 
4 3 3 4 
3 4 4 3 
3 4 4 3 
4 3 3 4 
 Figura 18 – Tabuleiro com ordenação pelo número característico da diagonal 
 
 Na Figura 18 é possível perceber que a primeira posição do tabuleiro (linha 1 e 
coluna 1) tem associado o número quatro, isso se deve ao fato de sua maior diagonal ter 
quatro casas. Na segunda posição (linha 1 e coluna 2), uma diagonal tem duas casas e a 
outra tem três casas; considerando que será utilizada a maior diagonal, a segunda posição 
do tabuleiro terá o número três. Esse processo se repete até que o tabuleiro esteja 
totalmente preenchido. A seguir, é possível definir a ordem de aplicação das regras 
considerando os números no tabuleiro e a seguinte regra: começando pela primeira linha, 
a primeira regra a ser aplicada é a que tem o menor número, caso existam dois números 
iguais, primeiro será utilizado o mais a esquerda. Dessa forma, a ordem de aplicação das 
regras é mostrada na Tabela 4. 
 
Linha do Tabuleiro Regras 
1 R12, R13, R11, R14 
2 R21, R24, R22, R23 
3 R31, R34, R32, R33 
4 R42, R43, R41, R44 
Tabela 4 – Ordem de aplicação das regras 
 O estado final ou estado meta que se deseja alcançar é o mostrado na Figura 19. 
 
Figura 19 – Estado meta do problema das Quatro Rainhas 
 Definidos: estado inicial, regras de produção, estratégia de controle e estado final, 
pode-se começar a resolver o problema. Utilizando a Tabela 4, a primeira regra a ser 
aplicada será R12, o que significa que a primeira rainha será colocada na linha 1 e coluna 2. 
Executada esta regra, o tabuleiro ficará como mostrado na Figura 20. 
 
Figura 20 – Nova configuração do tabuleiro gerada a partir da aplicação da Regra R12 
 Uma vez que a primeira linha já tem sua rainha, é necessário prosseguir para a 
segunda linha. De acordo com a Tabela 4, a primeira regra a ser aplicada para a segunda 
linha é a R21; depois de aplicada esta regra, o tabuleiro ficará como mostrado na Figura 21. 
 
 Figura 21 – Nova configuração do tabuleiro gerada a partir da aplicação da Regra R21 
 Depois de aplicada a regra R21 é possível perceber que uma das regras básicas do 
problema das Quatro Rainhas é violada!!! Uma vez que uma rainha se encontra na mesma 
diagonal que outra, a rainha da primeira linha será atacada, o que significa que esta regra 
não pode ser aplicada. Com isso, acontece um deadend e um retrocesso (ou backtrack) é 
necessário. Dessa forma, a aplicação da regra anterior é desfeita e uma nova regra será 
aplicada. A próxima regra a ser aplicada de acordo com a Tabela 4 é a R24. Após o 
retrocesso e a aplicação da nova regra, o tabuleiro ficará como mostrado na Figura 22. 
 
 
Figura 22 – Nova configuração do tabuleiro após retrocesso e aplicação da Regra R24 
 Colocada a rainha da linha dois e uma vez que na posição R41 não acontece nenhum 
ataque, deve-se passar para a linha três do tabuleiro. De acordo com a Tabela 01, para a 
terceira linha, a primeira regra a ser aplicada será a R31. Uma vez aplicada R31, o tabuleiro 
ficará como mostrado na Figura 23. 
 
 Figura 23 – Nova configuração do tabuleiro gerada a partir da aplicação da Regra R31 
 Para a quarta linha do tabuleiro, a primeira regra a ser aplicada é R42, e o resultado 
da aplicação desta regra pode ser visto na Figura 24. 
 
Figura 24 – Nova configuração do tabuleiro gerada a partir da aplicação da Regra R42 
 Na Figura 24 é possível perceber que um deadend acontece já que a rainha da 
quarta linha encontra-se na mesma diagonal da rainha da terceira linha. Com isso, é 
necessário um retrocesso (ou backtrack) e uma nova regra deve ser aplicada. De acordo 
com a Tabela 4, a próxima regra a ser aplicada para a quarta linha é a R43 e, após a 
aplicação desta regra, o tabuleiro ficará como mostrado na Figura 25. 
 
Figura 25 – Nova configuração do tabuleiro após retrocesso e aplicação da Regra R43 
 Considerando que a aplicação de R42 não viola nenhuma das regras do problema 
das Quatro Rainhas, conclui-se o preenchimento do tabuleiro; porém, neste ponto é 
fundamental verificar se o estado encontrado é o estado que se deseja. Assim, voltando à 
Figura 19, pode-se perceber que o estado que foi alcançado é realmente o estado desejado. 
 O número de backtracks que aconteceram foi dois, e um resumo da resolução do 
problema das Quatro Rainhas pode ser visto na Figura 26. 
 
Figura 26 – Resumo da resolução do problema das Quatro Rainhas 
 Avaliando a execução descrita passo a passo anteriormente e a Figura 26, é 
possível perceber que para o backtrack: 
 O procedimento termina com sucesso somente se atinge o estado meta 
(condição de terminação sobre DATA); 
 Terminações sem sucesso (deadend) ocorrem nas linhas 2 e 4; 
 No passo 4 o procedimento falha se todas as regras já foram tentadas; 
 O procedimento pode nunca terminar, uma vez que podem acontecer ciclos ou 
recursões infinitas; 
 Limites arbitrários sobre ciclos ou sobre a recursividade podem ser colocados. 
5.2.2 Busca em Grafos 
 A busca em grafos pode ser utilizada quando o espaço de estados puder ser 
representado por meio de um grafo direcionado (árvore). Neste caso: 
 Os nós correspondem às situações do problema; 
 Os arcos correspondem a movimentos válidos que transformam uma situação 
em outra; 
 Um problema será definido por um estado inicial e um estado final; 
 Uma solução do problema corresponde a um caminho no grafo. 
Se o problema for um problema de otimização (seja de maximização ou 
minimização) podem ser associados custos aos arcos. 
Nesta seção serão apresentadas estratégias de busca reunidas sob o título de busca 
sem informação (busca cega) e busca com informação (busca heurística). No primeiro 
caso, as estratégias não têm nenhuma informação adicional sobre os estados, seu papel é 
apenas o de gerar sucessores e saber distinguir um estado objetivo de um não objetivo. No 
segundo caso, as estratégias sabem se um estado não objetivo é “melhor” que outro. A 
diferença básica entre ambas se deve à ordem em que os nós serão visitados. 
 
5.2.2.1 Busca desinformada 
a) Busca em Largura 
 Na busca em largura (ou em extensão) o nós raiz é expandido primeiro, em seguida 
todos os sucessores deste nó raiz sãoexpandidos e, assim, sucessivamente. A Figura 27 
ilustra essa situação e a ordem de visitação dos nós será: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 e, por 
último, o 12. 
 
 
Figura 27 – Busca em Largura 
Cabe destacar que na busca em largura, se houver uma solução, é garantido que 
esta solução será obtida exigindo o menor número de etapas, uma vez que caminhos mais 
longos só serão explorados quando os mais curtos já tiverem sido além, de não correr o 
risco de examinar por longo tempo becos sem saída. Porém, nem sempre esta é a melhor 
estratégia, uma vez que apresenta a desvantagem de ser necessário armazenar todos os 
nós na memória, assim, a complexidade de espaço é igual à complexidade de tempo. 
1º 
2º 
4º 
3º 
A raiz da árvore de busca gera b nós no primeiro nível, b2 nós no segundo nível, b3 
no terceiro nível e assim sucessivamente. Considerando d a profundidade, o número total 
de nós gerados será: 
b + b2 + b3 +.... + bd + (bd+1 – b) = O (bd + 1) 
Em [Russell & Norvig, 2004] temos o seguinte exemplo: considerando um grafo de 
profundidade oito, o tempo necessário para encontrar uma solução seria 
aproximadamente 31 horas ao custo memória de 1 terabyte ou 1024 gigabytes. Caso a 
profundidade aumentasse para 12, seriam necessários 35 anos de processamento e 10 
petabytes (1024 terabytes) de memória. 
Neste contexto, os requisitos de memória são um problema maior para a busca em 
largura do que o tempo de execução, uma vez que esperar 31 horas pela solução de um 
problema é aceitável, porém, poucos computadores têm a memória principal da ordem de 
terabytes necessária. Além disso, problemas de complexidade exponencial não podem ser 
resolvidos por métodos de busca sem informação, exceto as muito pequenas. 
b) Busca em Profundidade 
 Na busca em profundidade o algoritmo começa no nó raiz e expande o nó mais 
profundo na borda atual do grafo. Assim, a busca prossegue imediatamente até o nível 
mais profundo do grafo onde os nós não têm mais sucessores. À medida que esses nós são 
retirados da borda, a busca retorna ao nó seguinte mais raso que ainda tem sucessores a 
serem explorados. A Figura 28 ilustra essa situação. 
 
 
Figura 28 – Busca em Profundidade 
 
 A ordem de visitação dos nós na Figura 28 é 1, 2, 5, 9, 10, 6, 3, 4, 7, 11, 12 e 8. 
1º 
2º 
3º 4º 
5º 
6º 
7º 
A busca em profundidade tem requisitos de memória bem mais modestos que a 
busca em largura, pois só precisa armazenar um único caminho de um nó raiz até um nó 
folha e, uma vez que um nó é expandido, ele pode ser removido da memória, assim que 
todos os seus descendentes tenham sido explorados. Alem disso, tem chances de 
encontrar uma solução sem examinar muito do espaço de busca desde que a solução esteja 
nos primeiros nós e mais profundos. 
c) Estratégia Branch-and-Bound 
 Esta estratégia consiste basicamente em “ramificar e podar”. Ela começa gerando 
caminhos completos e armazenando o menor caminho encontrado até o momento. Assim 
que um caminho em avaliação apresentar um comprimento parcial maior do que o 
caminho total já encontrado essa solução, é deixada de lado, e outra começa a ser 
explorada, pois, se o caminho parcial já é maior que um caminho total encontrado 
anteriormente, com certeza este caminho será pior e não há necessidade de continuar 
explorando-o. Dessa forma, esta estratégia pode garantir o encontro do menor caminho de 
maneira mais eficiente, mas, ainda assim, pode requerer tempo exponencial. 
 O tempo exato que esta estratégia irá economizar depende da ordem em que os 
caminhos são explorados, porém, continua ineficiente para problemas grandes. 
5.2.2.2 Busca com informação (busca heurística) 
 Os métodos vistos nas seções anteriores encontram uma solução para um 
problema partindo de um nó origem até um estado meta. Entretanto, em muitos casos a 
utilização destes métodos se torna impraticável devido ao elevado número de nós que 
devem ser expandidos até que uma solução seja encontrada. Um exemplo clássico desse 
tipo de problema é o Caixeiro Viajante, onde um vendedor tem uma lista de cidades que 
precisa visitar exatamente uma vez. Existem estradas diretas entre cada par de cidades da 
lista, e o objetivo é encontrar a menor rota que o vendedor deverá seguir começando e 
terminando pela mesma cidade, que pode ser qualquer uma da lista. 
 Neste problema é possível perceber a necessidade de explorar todos os caminhos 
possíveis na árvore de busca e retornar o de menor comprimento; porém, quando o 
número de cidades começa a aumentar, ocorre o que se chama de explosão combinatória 
já que o número de soluções diferentes para n cidades é (n-1)!, ou seja, para dez cidades 
teremos 3.628.000 soluções diferentes. 
 Problemas desta natureza, com solução algorítmica conhecida, mas, cuja solução 
demoraria muito tempo para ser encontrada, são categorizados como NP - Completos e, na 
prática, é como se não tivessem solução. 
 Para minimizar este problema, em alguns casos é possível estabelecer alguns 
princípios (ou regras práticas) para ajudar a reduzir a busca. Qualquer técnica utilizada 
para melhorar a busca depende, fundamentalmente, de informações especiais sobre o 
problema, e essas informações são chamadas de informações heurísticas. Uma heurística é 
uma técnica cujo objetivo é melhorar a eficiência de um determinado processo de busca ao 
custo de não assegurar que a solução ótima será encontrada; porém, raramente são 
necessárias soluções ótimas, geralmente, uma boa aproximação é aceitável. Neste 
contexto, a heurística irá apontar para caminhos que podem ser “interessantes” percorrer, 
porém, algumas vezes pode ser considerada inadequada no sentido que pode deixar de 
fora pontos interessantes para outros indivíduos. É importante destacar que funções 
heurísticas são específicas para cada problema. 
 Uma das maiores dificuldades quando se pretende utilizar uma função heurística é 
exatamente como definir uma boa função heurística. Para isso, ela deve ter como 
principal característica ser admissível, ou seja, nunca se deve superestimar o custo real 
da solução. Utilizando como exemplo o problema de encontrar o menor caminho entre 
Poços de Caldas e Belo Horizonte, pode-se considerar que uma função heurística 
admissível é considerar a distância direta entre os pontos, afinal, a menor distância entre 
dois pontos é uma reta. Com isso, é possível avaliar se a função heurística não está nem 
subestimada nem superestimada. 
 Nas próximas seções serão apresentados alguns algoritmos que utilizam 
heurísticas. 
a) Heurística do vizinho mais próximo 
 O funcionamento desta heurística é a cada nó visitado selecionar a melhor 
alternativa localmente superior a cada etapa. Utilizando como exemplo o problema do 
caixeiro viajante aplicado ao mapa mostrado na Figura 29, a lógica de execução do 
algoritmo é: 
1. Selecione arbitrariamente uma cidade inicial; 
2. Para selecionar a próxima cidade, examine todas as cidades que ainda não 
foram visitadas e selecione a que estiver mais perto da cidade atual e vá para 
lá; 
3. Repita o passo até que todas as cidades tenham sido visitadas. 
 
Figura 29: Mapa para simulação do algoritmo do vizinho mais próximo 
 
 Aplicando o passo 1 do algoritmo mostrado anteriormente, deve-se escolher a 
cidade inicial. Supondo que a cidade inicial seja Arad, a partir dela é possível chegar a 
Zerind (distante 75 milhas), Sibiu (distante 140 milhas) e Timisoara (distante 118 milhas). 
Aplicando o passo 2, deve-se escolher a cidade mais próxima da atual (ainda não visitada), 
portanto, a cidade escolhida será Zerind. Esta cidade passa a ser o novo ponto de origem. A 
partir de Zerind, pode-se ir para Oradea (distante 71 milhas) ou voltar para Arad (distante 
75 milhas). Uma vez que Arad já foi visitada, a única escolha possível é Oradea, então, 
segue-se para lá, e esta passa a ser a nova cidade origem. O processo continua até que 
todas as cidadestenham sido visitadas. 
Utilizando este procedimento, o número de possíveis soluções cai de (n-1)! para n2. 
b) Busca pela melhor escolha 
 Esta heurística tenta expandir o nó mais próximo à meta, supondo que isso 
provavelmente levará a uma solução rápida e é bastante semelhante à busca em 
profundidade, por preferir seguir um único caminho até o objetivo, mas, caso encontre um 
beco sem saída, irá retroceder. Além de a execução ser semelhante à busca em 
profundidade, ela tem também as mesmas deficiências – não é ótima nem é completa. 
c) Algoritmo A* 
 O algoritmo A* tem como objetivo minimizar o custo total estimado da solução 
através de uma função de avaliação. Essa função heurística de avaliação é representada 
por: 
f(n) = g(n) + h(n) 
 
 Onde: 
 g(n) é a distância de n ao nó inicial (s); 
 h(n) é a distância estimada de n ao nó final (t). 
 A Figura 30 ilustra essa situação. 
 Figura 30 – Função heurística A* 
 Neste algoritmo é expandido o nó de menor valor de f na fronteira do espaço de 
estados. Assim, se h for admissível f(n) nunca irá superestimar o custo real da melhor 
solução através de n. 
 Para ilustrar o funcionamento do algoritmo A* , será apresentado um exemplo 
proposto por [Russell & Norvig, 2004] cujo objetivo é ir de Arad até Bucareste. A Tabela 5 
apresenta as distâncias em linha reta de cada uma das cidades até Bucareste e a Figura 31 
apresenta o mapa com destaque para o ponto inicial (Arad) e para o ponto final 
(Bucareste). 
Arad 366 Mehadia 241 
Bucareste 0 Neamt 234 
Craiova 160 Oradea 380 
Dobreta 242 Pitesti 100 
Eforie 161 Rimnicu Vilcea 193 
Fagaras 176 Sibiu 253 
Giurgiu 77 Timisoara 329 
Hirsova 151 Urziceni 80 
Iasi 226 Vaslui 199 
Lugoji 244 Zerind 374 
Tabela 5 – Distâncias em linha reta até Bucareste 
 
 
Figura 31 – Espaço de busca entre Arad e Bucareste 
 
 A função heurística será f(n) = g(n) + h(n) , onde g(n) representa a distância da 
cidade n até Arad , e por h(n) que representa a distância em linha reta de n até Bucareste. 
Dessa forma, partindo de Arad podemos ir para Timisoara, Zerind e Sibiu. A expansão 
deste nós ficará como mostrado na Figura 32. 
 
 
Figura 32 – Expansão do nó Arad 
 A cada uma das cidades mostradas na Figura 32 estão associados os custos de 
acordo com a função heurística definida anteriormente. Dessa forma, o algoritmo A* irá 
optar pela menor distância, ou seja, vai escolher se deslocar para Sibiu e irá expandir esse 
nó como mostrado na Figura 33. 
 
Figura 33 – Expansão do nó Sibiu 
 Na Figura 33 é possível perceber que a partir de Sibiu é possível se deslocar para 
Arad, Fagaras, Oradea e Rimnicu. Dentre as possibilidades, a cidade mais próxima é 
Rimnicu, e com isso o próximo nó a ser expandido é Rimnicu. A execução continua desta 
forma até que a cidade Bucareste seja atingida. 
 Algumas considerações devem ser feitas com relação ao algoritmo A*. São elas: 
 A solução encontrada pelo A* é completa e ótima; 
 O comportamento do algoritmo A* é monotônico, ou seja, o custo de cada nó 
gerado no mesmo caminho nunca diminui; 
 O custo de tempo é exponencial de acordo com o tamanho da solução, porém, 
boas funções heurísticas diminuem significativamente esse custo; 
 Com relação a armazenamento de informação é importante destacar que são 
guardados todos os nós expandidos na memória, o que é um problema bem 
mais grave do que o tempo de busca e a complexidade do espaço do A* ainda é 
proibitiva. 
 
6. BIBLIOGRAFIA 
 
[Aurélio, 2009] Dicionário Aurélio. Disponível em: 
<http://www.dicionariodoaurelio.com>. Acesso em: 25 jul 2009. 
 
[Bello, 1995] Bello, J. L. P. A Teoria Básica de Jean Piaget. Vitória, 1995. Disponível em: 
<http://www.pedagogiaemfoco.pro.br/per09.htm>. Acesso em: 03 ago 2009. 
 
[Luger, 2004] Luger, G. F. Inteligência Artificial: estruturas e estratégias para a 
resolução de problemas complexos. Porto Alegre: Bookman, 2004. 774 págs. 
 
[Luger & Stubblefield, 1993] Luger, G. F.; Stubblefield, W. A. Artificial Intelligence: 
Structures and Strategies for Complex Problem Solving. Benjamin/Cummings. Redwood 
City, Califórnia, 2ª Ed., 1993. 
 
[Lustosa & Alvarenga, 2004] Lustosa, V. G.; Alvarenga, R. O Estado da Arte em 
Inteligência Artificial. Revista Digital da CVA-Ricesu. Brasília, 2004. 
 
[Maturana, 1998] Maturana, H. R. Da Biologia à Psicologia. Artmed Editora Ltda, 1998. 
 
[Nilsson, 1998] Nilsson, N. J. Artificial Intelligence: a new synthesis. Morgan Kaufmann, 
1998. 
 
[Piaget, 1982] Piaget, J. O Nascimento da Inteligência na Criança. 4ª Ed., Rio de Janeiro: 
Zahar, 1982. 
 
[Rich & Knight, 1994] Rich, E.; Knight, K. Inteligência Artificial. 2ª Ed., São Paulo: 
McGraw-Hill, 1994. 
 
[Russell & Norvig, 2004] Russell, S.; Norvig, Peter. Inteligência Artificial. 2ª Ed. 2003. 
 
[Simon & Newell, 1961] Simon, H. A.; Newell, A. Computer simulation of human thinking 
and problem solving. Datamation, June/July, 35-37, 1961. 
 
[Souto, 2009] Souto, M. C. P. Introdução à Inteligência Artificial. Notas de Aula. 
DIMAp/UFRN. Disponível em: <http://www.dimap.ufrn.br/~marcilio/IA/IA2004.1/IA-
aula-01-introducao.ppt>. Acesso em: 03 ago 2009. 
 
[Turing, 1950] Computing machinery and intelligente. Mind, 59: págs. 433-460. 
 
[Winston, 1992] Winston, P. H. Artificial Intelligence. MA: Addison-Wesley, 1992.