Resumo 2º Bimestre de Inteligencia Artificial

Prévia do material em texto

RESUMO IA
Teste de Turing
Como passar no teste de Turing?
Processamento de linguagem natural
Representação de conhecimento
Raciocínio automatizado
Aprendizado de máquina
O teste evita a interação física direta para focar na inteligência. 
Desvantagem
Ele não é uma definição a partir de princípios básicos e sim de imitação.
O que é um sistema inteligente?
Abordagens de Estudo da IA
Sistemas que pensam como seres humanos = Pensamento + Humano
Sistemas que pensam racionalmente = Pensamento + Racional
Sistemas que agem como seres humanos = Comportamento + Humano
Sistemas que agem racionalmente = Comportamento + Racional
Pensando de forma humana: modelagem cognitiva
Surgiu nos anos 60
Objetivo: tentar construir teorias precisas e verificáveis sobre os processos de funcionamento da mente humana.
Como validar?
Top-down: Prevendo e testando o comportamento de sujeitos humanos (ciência cognitiva).
Bottom-up: Identificação direta de dados neurológicos (neurociência cognitiva).
Áreas separadas de IA.
Pensando racionalmente: “leis do pensamento”
 Aristóteles: tentou codificar os raciocínios corretos = silogismos.
Exemplo: “Sócrates é um homem; todos os homens são mortais; então, Sócrates é mortal”
O estudo dessas leis deu início ao campo da lógica = notação e regras de derivação para pensamentos.
Existem programas que, em princípio, podem resolver qualquer problema solucionável descrito em notação lógica.
OBSTÁCULOS NA PRÁTICA: 
Não é fácil enunciar o conhecimento informal em termos formais.
Esgotamento dos recursos computacionais. 
Qual é o propósito prático do “pensamento”?
Agindo racionalmente: a abordagem do agente racional
Comportamento racional = agir corretamente na hora certa.
Agir corretamente = fazer o que é esperado para atingir seus objetivos, dada a informação disponível.
Não necessariamente envolve pensamentos (raciocínios lógicos).
A ação pode ser resultado de um reflexo. Ex.: Tirar a mão de um objeto quente.
O raciocínio lógico deve ser usado para alcançar um objetivo.
Agentes Racionais 
Um agente é algo que percebe e age.
Abstratamente, um agente é uma função que mapeia uma seqüência de percepções em uma ação.
Para cada tipo de ambiente e tarefa, buscamos o agente com a melhor performance.
Às vezes limitações computacionais impedem a racionalidade perfeita.
Racionalidade limitada: fazer o melhor possível dentro das limitações computacionais
A “Pré-História” da IA 
Filosofia - Lógica, métodos de raciocínio, mente como um sistema físico, origens do aprendizado (indução), racionalidade 
Matemática - Representações formais, algoritmos, computabilidade, intratabilidade, probabilidade
Economia - Conceito de utilidade, teoria da decisão, teoria dos jogos
Neurociência - Substrato físico para a atividade mental 
Psicologia - Percepção e controle motor, técnicas experimentais 
Engenharia da computação - Construção de computadores rápidos, ambientes computacionais, conceitos de programação 
Linguística - Representação do conhecimento e gramática 
Breve Histórico da IA 
1943 --McCulloch & Pitts: Modelo booleano do cérebro 
1950 --Turing publica "Computing Machinery and Intelligence" 
1956 --Encontro em Dartmouth: o termo “Inteligência Artificial" é criado 
1950s --Primeiros programas de IA, incluindo o jogador de damas de Samuel, o Logic Theorist de Newell & Simon e o Geometry Theorem Prover de Gelernter. 
1965 --Robinson descobre um método de raciocínio lógico completo 
1966—73 IA enfrenta o problema da complexidade computacional A pesquisa em redes neurais quase desaparece. 
1969—79 Desenvolvimento de sistemas especialistas 
1980-- IA (sistemas especialistas) se torna uma indústria 
1986-- Retorno das redes neurais 
1987-- IA se torna uma ciência 
1995-- Surgimento de agentes inteligentes 
Agentes Inteligentes
Agentes
Um agente é algo capaz de perceber seu ambiente por meio de sensores e de agir sobre esse ambiente por meio de atuadores.
Exemplos
Agente humano 
Sensores: Olhos, ouvidos e outros órgãos. 
Atuadores: Mãos, pernas, boca e outras partes do corpo.
Agente robótico 
Sensores: câmeras e detectores de infravermelho. 
Atuadores: vários motores. 
Agente de software 
Sensores: entrada do teclado, conteúdo de arquivos e pacotes vindos da rede. 
Atuadores: tela, disco, envio de pacotes pela rede.
Mapeando percepções em ações 
Sequência de percepções: história completa de tudo que o agente percebeu. 
O comportamento do agente é dado abstratamente pela função do agente: [f: P* A] onde é a P* é uma sequência de percepções e A é uma ação.
O programa do agente roda em uma arquitetura física para produzir f.
Agente = arquitetura + programa.
Exemplos
O mundo do aspirador de pó: 
Percepções: local e conteúdo
Exemplo: [A, sujo] 
Ações: Esquerda, Direita, Aspirar, NoOp
Agentes Racionais
Como preencher corretamente a tabela de ações do agente para cada situação?
O agente deve tomar a ação “correta” baseado no que ele percebe para ter sucesso.
O conceito de sucesso do agente depende uma medida de desempenho objetiva
Exemplos: quantidade de sujeira aspirada, gasto de energia, gasto de tempo, quantidade de barulho gerado, etc.
A medida de desempenho deve refletir o resultado realmente desejado.
Para cada sequência de percepções possíveis deve selecionar uma ação que se espera que venha a maximizar sua medida de desempenho, dada a evidência fornecida pela seqüência de percepções e por qualquer conhecimento interno do agente.
Exercício: para que medida de desempenho o agente aspirador de pó é racional?
Racionalidade é diferente de perfeição. 
A racionalidade maximiza o desempenho esperado, enquanto a perfeição maximiza o desempenho real.
A escolha racional só depende das percepções até o momento.
Mas os agentes podem (e devem!) executar ações para coleta de informações.
Um tipo importante de coleta de informação é a exploração de um ambiente desconhecido.
O agente também pode (e deve!) aprender, ou seja, modificar seu comportamento dependendo do que ele percebe ao longo do tempo.
Nesse caso o agente é chamado de autônomo.
Um agente que aprende pode ter sucesso em uma ampla variedade de ambientes
PEAS
Ao projetar um agente, a primeira etapa deve ser sempre especificar o ambiente de tarefa. 
Performance = Medida de Desempenho 
Environment = Ambiente 
Actuators = Atuadores 
Sensors = Sensores
Exemplo de PEAS: Motorista de Táxi Automatizado
Medida de desempenho: viagem segura, rápida, sem violações às leis de trânsito, confortável para os passageiros, maximizando os lucros.
Ambiente: ruas, estradas, outros veículos, pedestres, clientes.
Atuadores: direção, acelerador, freio, embreagem, marcha, seta, buzina. 
Sensores: câmera, sonar, velocímetro, GPS, hodômetro, acelerômetro, sensores do motor, teclado ou microfone.
Outros Exemplos de PEAS: Sistema de Diagnóstico Médico, Robô de seleção de peças, Instrutor de Inglês Interativo. Etc…
Propriedades de ambientes de tarefa
Completamente observável (versus parcialmente observável)
Os sensores do agente dão acesso ao estado completo do ambiente em cada instante.
Todos os aspectos relevantes do ambiente são acessíveis.
Determinístico (versus estocástico) 
O próximo estado do ambiente é completamente determinado pelo estado atual e pela ação executada pelo agente. 
Se o ambiente é determinístico exceto pelas ações de outros agentes, dizemos que o ambiente é estratégico.
Episódico (versus sequencial) 
A experiência do agente pode ser dividida em episódios (percepção e execução de uma única ação). 
A escolha da ação em cada episódio só depende do próprio episódio. 
Estático (versus dinâmico) 
O ambiente não muda enquanto o agente pensa. 
O ambiente é semidinâmico se ele não muda com a passagem do tempo, mas o nível de desempenho do agente se altera.
Discreto (versus contínuo) 
Um número limitado e claramente definido de percepções e ações.
Agente único (versus multi-agente) 
Um único agente operando sozinho no ambiente.
No caso multi-agente podemoster
Multi-agente cooperativo 
Multi-agente competitivo
Exemplo 
Xadrez com relógio Xadrez sem relógio Direção de Táxi 
Completamente observável 	Sim 		 Sim 			Não 
Determinístico 			Sim 		 Sim 			Não 
Episódico 			Não 		 Não 			Não 
Estático 			Semi 		 Sim 			Não 
Discreto 			Sim 		 Sim 		Não 
Agente único 			Não 		 Não 		Não
O tipo de ambiente de tarefa determina em grande parte o projeto do agente. 
O mundo real é parcialmente observável, estocástico, seqüêncial, dinâmico, contínuo, multi-agente.
Programas e funções de agentes 
Um agente é completamente especificado pela função de agente que mapeia sequências de percepções em ações. 
Uma única função de agente (ou uma única classe de funções equivalentes) é racional. 
Objetivo: encontrar uma maneira de representar a função racional do agente concisamente.
Agente Dirigido por Tabela 
Desvantagens: 
Tabela gigante (xadrez = 10150 entradas) 
Tempo longo para construir a tabela 
Não tem autonomia
Mesmo com aprendizado demoraria muito para aprender a tabela.
Tipos básicos de agentes 
Quatro tipos básicos, do mais simples ao mais geral 
Agentes reativos simples 
Agentes reativos baseados em modelos 
Agentes baseados em objetivos 
Agentes baseados na utilidade
Agente Reativo Simples
Exemplo: ASPIRADOR DE PÓ REATIVO
Regras condição-ação (regras se-então) fazem uma ligação direta entre a percepção atual e a ação.
O agente funciona apenas se o ambiente for completamente observável e a decisão correta puder ser tomada com base apenas na percepção atual.
Agentes reativos baseados em modelos
Variaveis Estaticas:
Estado, uma descrição do estado atual do mundo 
regras, um conjunto de regras condição-ação
ação, a ação mais recente, incialmente nenhuma
Agentes reativos baseados em objetivos
Agentes reativos baseados na utilidade
Agentes com aprendizagem
Resolução de problemas por meio de busca
Agentes de resolução de problemas 
Agentes reativos não funcionam em ambientes para quais o número de regras condição-ação é grande demais para armazenar. 
Nesse caso podemos construir um tipo de agente baseado em objetivo chamado de agente de resolução de problemas.
Busca
 Um agente com várias opções imediatas pode decidir o que fazer comparando diferentes sequências de ações possíveis.
Esse processo de procurar pela melhor sequência é chamado de busca.
Formular objetivo → buscar → executar
Formulação de problemas 
Um problema é definido por quatro itens: 
1. Estado inicial ex., “em Arad" 
2. Ações ou função sucessor S(x) = conjunto de pares estado-ação – ex., S(Arad) = {, … } 
3. Teste de objetivo, pode ser – explícito, ex., x = “em Bucharest" – implícito, ex., Cheque-mate(x) – 
4. Custo de caminho (aditivo) – ex., soma das distâncias, número de ações executadas, etc. – c(x,a,y) é o custo do passo, que deve ser sempre ≥ 0 
Uma solução é uma sequência de ações que levam do estado inicial para o estado objetivo. 
Uma solução ótima é uma solução com o menor custo de caminho.
Agente de Resolução de Problemas
Variaveis Estáticas
percept = Percepção do mundo real
seq = Um sequência de Ação(Inicialmente Vazia)
state = Alguma descrição do mundo atualmente
goal = um objetivo, inicialmente Vazio
problem = Um problema para formular
Supõe que ambiente é estático, observável, discreto e determinístico.
Espaço de estados 
O conjunto de todos os estados acessíveis a partir de um estado inicial é chamado de espaço de estados. – Os estados acessíveis são aqueles dados pela função sucessora. 
O espaço de estados pode ser interpretado como um grafo em que os nós são estados e os arcos são ações. 
Selecionando um espaço de estados
O mundo real é absurdamente complexo: o espaço de estados é uma abstração 
Estado (abstrato) = conjunto de estados reais 
Ação (abstrata) = combinação complexa de ações reais – 
ex., "Arad Zerind" representa um conjunto complexo de rotas, desvios, paradas, etc. – 
Qualquer estado real do conjunto “em Arad“ deve levar a algum estado real “em Zerind“.
Solução (abstrata) = conjunto de caminhos reais que são soluções no mundo real 
A abstração é útil se cada ação abstrata é mais fácil de executar que o problema original.
Exemplo 1: Espaço de Estados do Mundo do Aspirador de Pó
Estados: Definidos pela posição do robô e sujeira (8 estados)
Estado inicial: Qualquer um
Função sucessor: pode-se executar qualquer uma das ações em cada estado (esquerda, direita, aspirar)
Teste de objetivo: Verifica se todos os quadrados estão limpos 
Custo do caminho: Cada passo custa 1, e assim o custo do caminho é o número de passos do caminho
Outros exemplos: O quebra-cabeça de 8 peças,:Oito rainhas Formulação incremental, Oito rainhas Formulação de estados completos, etc.
Problemas do mundo real 
Problema de roteamento – encontrar a melhor rota de um ponto a outro (aplicações: redes de computadores, planejamento militar, planejamento de viagens aéreas) 
Problemas de tour – visitar cada ponto pelo menos uma vez 
Caixeiro viajante – visitar cada cidade exatamente uma vez – encontrar o caminho mais curto
Layout de VLSI – posicionamento de componentes e conexões em um chip
Projeto de proteínas – encontrar uma sequência de aminoácidos que serão incorporados em uma proteína tridimensional para curar alguma doença. 
Busca de soluções 
Idéia: Percorrer o espaço de estados a partir de uma árvore de busca. 
Expandir o estado atual aplicando a função sucessor, gerando novos estados. 
Busca: seguir um caminho, deixando os outros para depois. 
A estratégia de busca determina qual caminho seguir. 
Descrição informal do algoritmo geral de busca em árvore
Árvore de busca não é equivalente a espaço de estados!
Há 20 estados no mapa da Romênia (espaço de estados), mas infinitos caminhos a percorrer. Portanto a árvore de busca, neste caso, tem tamanho infinito. – 
Caminho infinito: Arad-Sibiu-Arad-Sibiu-Arad-...
Estados vs. nós 
Um estado é uma (representação de) uma configuração física 
Um nó é uma estrutura de dados que é parte da árvore de busca e inclui estado, nó pai, ação, custo do caminho g(x), profundidade 
A função Expand cria novos nós, preenchendo os vários campos e usando a função sucessor do problema para gerar os estados correspondentes. 
A coleção de nós que foram gerados, mas ainda não foram expandidos é chamada de borda (ou fringe) – 
Geralmente implementados como uma fila. – 
A maneira como os nós entram na fila determina a estratégia de busca.
Algoritmo geral de busca em árvore 
Estratégias de busca 
Uma estratégia de busca é definida pela escolha da ordem da expansão de nós 
Estratégias são avaliadas de acordo com os seguintes critérios: – 
completeza: o algoritmo sempre encontra a solução se ela existe? – 
complexidade de tempo: número de nós gerados – 
complexidade de espaço: número máximo de nós na memória – 
otimização: a estratégia encontra a solução ótima? 
Complexidade de tempo e espaço são medidas em termos de: – 
b: máximo fator de ramificação da árvore (número máximo de sucessores de qualquer nó) – 
d: profundidade do nó objetivo menos profundo – 
m: o comprimento máximo de qualquer caminho no espaço de estados (pode ser ∞)
Estratégias de Busca Sem Informação (ou Busca Cega)
Estratégias de busca sem informação usam apenas a informação disponível na definição do problema. –
 Apenas geram sucessores e verificam se o estado objetivo foi atingido. 
As estratégias de busca sem informação se distinguem pela ordem em que os nós são expandidos. – 
Busca em extensão (Breadth-first) – 
Busca de custo uniforme –
Busca em profundidade (Depth-first) – 
Busca em profundidade limitada – 
Busca de aprofundamento iterativo
Busca em extensão 
Expandir o nó não-expandido mais perto da raiz. 
Implementação: – a borda é uma fila FIFO (first-in, first-out), isto é, novos itens entram no final.
Propriedades da busca em extensão 
Completa? Sim (se b é finito) 
Tempo? 1+b+b2+b3+… +b d + b(bd -1) = O(bd+1) 
Espaço? O(bd+1)(mantém todos os nós na memória) 
Ótima? Sim (se todas as ações tiverem o mesmo custo)
Requisitos de Tempo e Memória para a Busca em Extensão 
Busca com fator de ramificação b=10. 
Supondo que 10.000 nós possam ser gerados por segundo e que um nó exige 1KB de espaço. 
Busca de custo uniforme 
Expande o nó não-expandido que tenha o caminho de custo mais baixo. 
Implementação: – borda = fila ordenada pelo custo do caminho 
Equivalente a busca em extensão se os custos são todos iguais 
Completa? Sim, se o custo de cada passo ≥ ε 
Tempo? # de nós com g ≤ custo da solução ótima, O(b C*/ ε ) onde C * é o custo da solução ótima 
Espaço? de nós com g ≤ custo da solução ótima, O(b C*/ ε ) 
Ótima? Sim pois os nós são expandidos em ordem crescente de custo total.
Busca em Profundidade 
Expande o nó não-expandido mais profundo. 
Implementação: – borda = fila LIFO (last-in, first-out) = pilha
Propriedades da Busca em Profundidade 
Completa? Não: falha em espaços com profundidade infinita, espaços com loops –
Se modificada para evitar estados repetidos é completa para espaços finitos 
Tempo? O(bm): péssimo quando m é muito maior que d. – 
mas se há muitas soluções pode ser mais eficiente que a busca em extensão 
Espaço? O(bm), i.e., espaço linear! – 118 kilobytes ao invés de 10 petabytes para busca com b=10, d=m=12 
Ótima? Não 
Busca em Profundidade Limitada 
Igual busca em profundidade com limite de profundidade l, isto é, nós com profundidade l não tem sucessores
Implementação Recursiva
Propriedades da Busca em Profundidade Limitada 
Completa? Não; a solução pode estar além do limite. 
Tempo? O(bl ) 
Espaço? O(bl) 
Ótima? Não
Busca de Aprofundamento Iterativo em Profundidade 
Propriedades da busca de aprofundamento iterativo 
Completa? Sim 
Tempo? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd ) 
Espaço? O(bd) 
Ótima? Sim, se custo de passo = 1
Estados repetidos 
O processo de busca pode perder tempo expandindo nós já explorados antes – 
Estados repetidos podem levar a loops infinitos – 
Estados repetidos podem transformar um problema linear em um problema exponencial
Detecção de estados repetidos 
Comparar os nós prestes a serem expandidos com nós já visitados. –
Se o nó já tiver sido visitado, será descartado. – 
Lista “closed” (fechado) armazena nós já visitados. 
Busca em profundidade e busca de aprofundamento iterativo não tem mais espaço linear. – 
A busca percorre um grafo e não uma árvore.
Resumo 
A formulação de problemas usualmente requer a abstração de detalhes do mundo real para que seja definido um espaço de estados que possa ser explorado através de algoritmos de busca.
Há uma variedade de estratégias de busca sem informação (ou busca cega). 
A busca de aprofundamento iterativo usa somente espaço linear e não muito mais tempo que outros algoritmos sem informação.
Busca com informação e exploração
Busca com informação (ou heurística) 
Utiliza conhecimento específico sobre o problema para encontrar soluções de forma mais eficiente do que a busca cega. – 
Conhecimento específico além da definição do problema. 
Abordagem geral: busca pela melhor escolha. – 
Utiliza uma função de avaliação para cada nó. – 
Expande o nó que tem a função de avaliação mais baixa. – 
Dependendo da função de avaliação, a estratégia de busca muda.
Busca pela melhor escolha 
Idéia: usar uma função de avaliação f(n) para cada nó. – 
estimativa do quanto aquele nó é desejável 
Expandir nó mais desejável que ainda não foi expandido que
Implementação: Ordenar nós na borda em ordem decrescente de acordo com a função de avaliação 
Casos especiais: – Busca gulosa pela melhor escolha – 
Busca A*
Busca gulosa pela melhor escolha 
Função de avaliação f(n) = h(n) (heurística) = estimativa do custo de n até o objetivo ex., hDLR(n) = distância em linha reta de n até Bucareste. 
Busca gulosa pela melhor escolha expande o nó que parece mais próximo ao objetivo de acordo com a função heurística. 
Não é ótima, pois segue o melhor passo considerando somente o estado atual. – 
Pode haver um caminho melhor seguindo algumas opções piores em alguns pontos da árvore de busca. 
Minimizar h(n) é suscetível a falsos inícios. – 
Ex. Ir de Iasi a Fagaras 
Heurística sugerirá ir a Neamt, que é um beco sem saída. 
Se repetições não forem detectadas a busca entrará em loop.
Completa? Não – pode ficar presa em loops, ex., Iasi Neamt Iasi Neamt 
Tempo? O(bm) no pior caso, mas uma boa função heurística pode levar a uma redução substancial 
Espaço? O(bm) – mantém todos os nós na memória 
Ótima? Não
Busca A* 
Idéia: evitar expandir caminhos que já são caros 
Fu aq nção de avaliação f(n) = g(n) + h(n) – 
g(n) = custo até o momento para alcançar n – 
h(n) = custo estimado de n até o objetivo – 
f(n) = custo total estimado do caminho através de n até o objetivo. 
Heurística Admissível 
Uma heurística h(n) é admissível se para cada nó n, h(n) ≤ h * (n), onde h * (n) é o custo verdadeiro de alcançar o estado objetivo a partir de n. 
Uma heurística admissível nunca superestima o custo de alcançar o objetivo, isto é, ela é otimista.
Exemplo: hDLR(n) (distância em linha reta nunca é maior que distância pela estrada).
Teorema: Se h(n) é admissível, A* usando algoritmo BUSCA-EM-ARVORE é ótima.
Prova que A* é ótima com heurística admissível 
Assuma um nó objetivo não- ótimo G2 , e seja C* o custo da solução ótima. Então, como G2 não é ótimo e h(G2 ) = 0, sabemos que: f(G2 ) = g(G2 ) + h(G2 ) = g(G2 ) > C* 
Considere qualquer nó de borda n que esteja num caminho de solução ótimo. Se h(n) não superestimar o custo de completar o caminho de solução, então: f(n) = g(n) + h(n) C*.
Logo, se f(n) C* < f(G2 ), G2 não será expandido e A* deve retornar uma solução ótima. 
Isso vale para busca em árvore, para outras estruturas de busca pode não valer. 
Na busca em grafos temos que assegurar que o caminho ótimo para qualquer estado repetido seja o primeiro a ser seguido. – 
Requisito extra para h(n): consistência 
Consistência (ou monotonicidade) 
Uma heurística é consistente (ou monotônica) se para cada nó n, cada sucessor n' de n gerado por qualquer ação a, h(n) ≤ c(n,a,n') + h(n') 
Se h é consistente, temos f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n) 
Isto é, f(n) is não-decrescente ao longo de qualquer caminho. 
Teorema: Se h(n) is consistente, A* usando BUSCA-EM-GRAFOS é ótima.
A * é ótima com heurística consistente
A * expande nós em ordem crescente de valores de f. 
Gradualmente adiciona “contornos" de nós. 
Contorno i tem todos os nós com f=fi , onde f i < fi+1 
Se h(n)=0 temos uma busca de custo uniforme círculos concêntricos. 
Quanto melhor a heurística mais direcionados ao objetivo serão os círculos 
Propriedades da Busca A* 
Completa? Sim (a não ser que exista uma quantidade infinita de nós com f ≤ f(G) ) 
Tempo? Exponencial no pior caso 
Espaço? Mantém todos os nós na memória
Ótima? Sim 
Otimamente eficiente – 
Nenhum outro algoritmo de busca ótimo tem garantia de expandir um número de nós menor que A*. Isso porque qualquer algoritmo que não expande todos os nós com f(n) < C* corre o risco de omitir uma solução ótima. 
Medindo a qualidade de uma heurística 
Fator de ramificação efetiva – 
A* gera N nós – 
Profundidade da solução é d – 
Supondo uma árvore uniforme, podemos calcular o fator de ramificação efetiva b* a partir de: N+1 = 1+b* + (b*)² + …. +(b*`)²
Dominância
h2 é melhor que h1 e muito melhor que a busca por aprofundamento iterativo. 
h2 é sempre melhor que h1 pois 
h2 domina h1 
Como ambas heurísticas são admissíveis, menos nós serão expandidos pela heurística dominante. – 
Escolhe nós mais próximos da solução. 
Como criar heurísticas admissíveis? 
A solução de uma simplificação de um problema (problema relaxado) é uma heurística para o problema original. – 
Admissível: a solução do problema relaxado não vai superestimar a do problema original. – 
É consistente para o problema original se for consistentepara o relaxado. 
Usar o custo da solução de um subproblema do problema original. 
Calcular o custo da solução exata sem se preocupar com os * Limite inferior do custo do problema completo
Banco de dados de padrões: –
 Armazenar o custo exato das soluções de muitos subproblemas. – 
Para um determinado estado procurar o subproblema referentes àquele estado. – 
Exemplo: todas as configurações das 4 peças na figura anterior. 
Algoritmos de Busca Local
Em muitos problemas de otimização o caminho para o objetivo é irrelevante. –
Queremos apenas encontrar o estado objetivo, não importando a seqüência de ações. – 
Espaço de estados = conjunto de configurações completas. 
Queremos encontrar a melhor configuração. 
Neste caso podemos usar algoritmos de busca local. 
Mantêm apenas o estado atual, sem a necessidade de manter a árvore de busca. 
Busca de Subida de Encosta 
“É como subir o Everest em meio a um nevoeiro durante uma crise de amnésia”
Elevação é a função objetivo: queremos encontrar o máximo global. 
Elevação é o custo: queremos encontrar o mínimo global. 
O algoritmo consiste em uma repetição que percorre o espaço de estados no sentido do valor crescente (ou decrescente). 
Termina quando encontra um pico (ou vale) em que nenhuma vizinho tem valor mais alto. 
Não mantém uma árvore, o nó atual só registra o estado atual e o valor da função objetivo. 
Não examina antecipadamente valores de estados além dos valores dos vizinhos imediatos do estado atual. 
Problema: dependendo do estado inicial pode ficar presa em máximos (ou mínimos) locais.
Movimento lateral para evitar platôs – 
Porém pode ocorrer repetição infinita, temos que impor um limite para o número de movimentos laterais. 
Subida de encosta com reinícios aleatórios. – 
Conduz várias buscas a partir de vários estados iniciais escolhidos aleatoriamente. – 
É completa, pois no pior acaso irá acabar gerando o estado objetivo como estado inicial, porém é ineficiente. 
Busca de têmpera simulada (simulated annealing)
Combina a subida de encosta com um percurso aleatório resultando em eficiência e completeza. 
Subida de encosta dando uma “chacoalhada” nos estados sucessores. – 
Estados com avaliação pior podem ser escolhidos com uma certa probabilidade. –
 Esta probabilidade diminui com o tempo.
Escapa de máximos locais permitindo alguns passos “ruins” mas gradualmente decresce a sua freqüência.
Pode-se provar que se T decresce devagar o suficiente, a busca pode achar uma solução ótima global com probabilidade tendendo a 1. 
Muito usada em projetos de circuitos integrados, layout de instalações industriais, otimização de redes de telecomunicações, etc.
Busca em Feixe Local
Manter k estados ao invés de um. 
Começa com k estados gerados aleatoriamente. 
A cada iteração, todos os sucessores dos k estados são gerados.
Se qualquer um deles for o estado objetivo, a busca para; senão seleciona-se os k melhores estados da lista pra continuar.
Algoritmos genéticos 
Um estado sucessor é gerado através da combinação de dois estados pais. 
Começa com k estados gerados aleatoriamente (população). 
Um estado é representado por uma string de um alfabeto finito (normalmente strings de 0s e 1s). 
Função de avaliação (função de fitness). Valores mais altos pra estados melhores. 
Produz a próxima geração de estados por seleção, mutação e crossover. 
Função de fitness: número de pares de rainhas que não estão se atacando (min = 0, max = 8 × 7/2 = 28) 
24/(24+23+20+11) = 31% 
23/(24+23+20+11) = 29% etc