Busca

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Resolução de Problemas por meio de Busca
AGENTE SOLUCIONADOR DE PROBLEMAS:
Agente baseado em metas (objetivos) cuja função é encontrar uma sequência de ações que leva a um estado desejado.
FORMULAÇÃO DO PROBLEMA:
O problema deve ser definido como um problema de busca (pesquisa) de uma solução no espaço de estados.
Espaço de estados: todos os estados interessantes disponíveis ao agente.
Para formular um problema deve-se definir:
Estados: representações do mundo exterior (ambiente);
Operadores (ações): causam a mudança (transição) de um estado para outro.
Para iniciar o processo de busca por uma solução deve-se especificar o estado inicial e o objetivo.
*
*
Exemplo
Sair de Arad e chegar a Bucareste (ambas na Romênia):
*
*
Pesquisa (Busca)
Busca
É o processo de procura pela melhor sequência de ações que leve a um estado-objetivo.
Algoritmo de busca
Algoritmo que recebe como entrada, um problema e retorna uma solução (uma sequência de ações).
Execução
Execução da solução proposta pelo algoritmo de busca.
 Acao problemSolvingAgent(Percepto p) {
 static Estado estado;
 Ação[] seq;
 Objetivo obj;
 Problema problema;
 atualizaEstado(estado, p);
 if (seq == null) { // início da busca
 obj = formulaObjetivo(estado);
 problema = formulaProblema(estado, obj);
 seq = pesquisa(problema)
 }
	// FASE DE EXECUÇÃO
 acao = encontraAcao(seq, estado);
 seq = acoesRestantes(estado, seq, acao);
 
 return acao;
}
*
*
Formulação de Problemas
Problemas podem ser classificados como sendo de quatro tipos:
De único estado
De múltiplos estados (conformante ou conformativo)
De contingências
De exploração
*
*
Tipos de Problemas
Problemas de único estado:
Ao executar uma ação o agente sabe o estado resultante (ele tem sensores suficientes).
Problemas de múltiplos estados (“conformantes”):
Ao executar uma ação, o agente tem conhecimento incompleto sobre o estado resultante (sensores não captam tudo que é necessário). O agente pode não saber onde está.
{5}
{6}
{8}
direita
aspira
{1,2,…,8}
{2,4,6,8}
{4,8}
direita
aspira
{7}
{3,7}
esquerda
aspira
*
*
Problemas de contingências:
O agente requer o uso de sensor(es) durante a execução de uma ação: busca e execução são alternadas.
Problemas de exploração:
O agente desconhece completamente os efeitos de suas ações: a capacidade de aprendizagem é requerida.
Tipos de Problemas
*
*
Problemas e Soluções
Um problema é uma coleção de informações que um agente irá utilizar para decidir o que fazer (qual ação executar).
Um problema é definido especificando-se:
Estado inicial. Ex: Em(Arad)
Função sucessor: conjunto de pares ação-estado. 
Ex: S(Em(Arad)) = {[Mover(Arad, Zerind), Em(Zerind)], [Mover(Arad, Sibiu), Em(Sibiu)], [Mover(Arad, Timisoara), Em(Timisoara)]}
Teste de objetivo (ou meta). Ex: Em(Bucareste)? (teste explícito), naoHaPó(x) (teste implícito)
Função de custo dos caminhos. Ex: soma das distâncias entre as cidades componentes do caminho.
class Problema {
 Estado estadoInicial;
 Sucessor sucessor;
 TesteDeObjetivo teste;
 FuncaoDeCustoDoCaminho custos;
}
Uma solução é um caminho do estado inicial a um estado que satisfaz o teste de objetivo.
*
*
Aspectos de Metodologias de Busca
Medindo o desempenho da resolução de problemas
A efetividade de uma busca pode ser medida de pelo menos três modos:
O método encontra uma solução?
A solução encontrada é “boa” (de baixo custo de caminho)?
Qual é o custo de busca, associado ao tempo e memória, necessário para encontrar a solução?
Escolhendo estados e ações
A arte real da resolução de problemas está em se definir as descrições de possíveis estados e ações.
Ex:
Em(Arad)  descrição simples e suficiente para a resolução do problema.
Mover(Arad, Sibiu)  captura o essencial à resolução. Garante que a ação será a mais fácil possível de ser executada.
Abstração 
É o processo de remover detalhes (não relevantes) de uma representação.
*
*
Problemas Exemplo
Toy problems (Miniproblemas)
Mais fáceis que os problemas do mundo real
Mais concisos, ou seja, menores
Descrição exata
Permite comparação fácil de algoritmos alternativos
Quebra-cabeças de 8 números
FORMULAÇÃO:
Estados: locais das peças e do vazio
Estado inicial: qualquer configuraçao das peças e do vazio
Função sucessor: gera estados que resultam de mover vazio para Esquerda, Direita, ParaCima ou ParaBaixo
Teste de objetivo: estado casa com o estado final (figura)?
Custo de caminho: cada movimento (passo) custa 1 (custo de caminho = núm. de passos)
Essa classe de problemas é NP-completo!
*
*
O Mundo do Aspirador
FORMULAÇÃO (PERCEPÇÃO TOTAL):
Estados: um dos 8 estados da figura
Estado inicial: qualquer um dos 8 estados da figura
Função sucessor: gera estados que resultam das ações Esquerda, Direita, Aspirar
Teste de objetivo: nenhum lugar tem sujeira
Custo de caminho: 1 para cada ação (custo = número de passos)
*
*
Problema Real: Montagem Robótica
FORMULAÇÃO:
Estados: coordenadas (números reais) dos 
ângulos das juntas do robô
partes do objeto a ser montado
Estados iniciais: geralmente um conjunto de coordenadas predefinidas
Função sucessor: gera um conjunto de coordenadas pela aplicação de correntes elétricas nos motores do robô
Teste de Objetivo: montagem completa
Custo de caminho: tempo de montagem
*
*
IDÉIA BÁSICA:
Exploração simulada do espaço de estados por meio da geração dos sucessores dos estados já explorados.
Árvore de busca:	Estrutura de um algoritmo de busca:
Algoritmos em Árvores de Pesquisa (Busca)
Arad
Sibiu
Timisoara
Zerind
Arad
Fagaras
Oradea
Rimnicu 
Vilcea
 Solucao treeSearch(Problema p, Estrategia e) {
 inicializa a árvore de pesquisa com o estado inicial de p
 while (true) { 
 if (não existem candidatos para expansão)
 return FALHA;
 escolha um nodo filho de acordo com a estratégia e
 if (nodo contem um estado-objetivo)
 return a solução correspondente;
 else
 expanda o nodo e adicione os nodos resultantes à
 árvore de pesquisa
 }
}
*
*
Um estado é uma representação de uma configuração física (real)
Um nodo é uma estrutura de dados constituinte de uma árvore de pesquisa que inclui: pai, filhos, profundidade, custo de caminho
class Nodo {
 Nodo pai;
 Nodo[] filhos;
 int depth;
 FuncaoDeCusto g; // até a raiz
}
Implementação: Nodos x Estados
Estado:
Nodo:
depth = 6
g = 6
pai
f i l h o s
*
*
Algoritmo Geral de Pesquisa
Solucao treeSearch(Problema problema, Lista borda) {
 borda.insereFrente(criaNodo(estadoInicial(problema)));
 while (true) {
 if (borda.vazia())
 return FALHA;
 nodo = borda.frente(); // retorna e remove o nodo!!
 if (problema.testeDeObjetivo.fim(estado(nodo)))
 return solucao(nodo);
 borda.insereTodos(expande(nodo, problema)); // aqui os métodos
 // se diferenciam
 }
}
A função expande cria novos nodos, preenchendo os campos e atualizando os estados correspondentes.
A lista pode ser uma fila ou pilha ou uma outra estrutura que defina uma ordem em que nodos são inseridos e removidos. Ela implementa a estratégia de busca.
*
*
Estratégias de Pesquisa
As estratégias de busca podem ser avaliadas com base em quatro critérios:
Completeza: estratégia sempre encontra uma solução se existe uma?
Complexidade de tempo: quanto tempo demora até encontrar uma solução? É proporcional ao número de nodos gerados/expandidos.
Complexidade de espaço: quanta memória é necessária? É proporcional ao número de nodos armazenados.
Otimalidade: a melhor solução possível é encontrada quando existe mais de uma solução possível?
Complexidade de tempo e espaço são medidas em
termos de:
b: fator de ramificação máximo da árvore de busca;
d: profundidade da solução de menor custo;
m: profundidade máxima da árvore (pode ser infinita).
*
*
Pesquisa “O Melhor Primeiro” (Best-first)
Utiliza uma função de avaliação para guiar a busca.
Função de avaliação: avalia um nodo da árvore de pesquisa de acordo com algum critério.
A função de avaliação produz um número que tenta descrever o “quão bom” (ou ruim) é o nodo no processo de busca pela melhor solução. Ou seja, o nodo deve ser expandido ou não?
Na realidade, o nodo expandido é o que “parece ser” o melhor segundo a função de avaliação.
DUAS ABORDAGENS:
Busca gulosa (greedy)
Algoritmo A*
*
*
Busca Gulosa (Greedy Search)
Procura minimizar o custo estimado para atingir o objetivo.
Logo, esse método sempre expande o nodo cujo estado é previsto como o mais próximo do objetivo. Ou seja, expande o nodo “mais próximo” do objetivo.
Para estimar o custo de se alcançar o objetivo é utilizada uma função heurística.
Função heurística:
h(n) é o custo estimado do caminho mais barato do estado n até um estado-objetivo.
EXIGÊNCIA:
h(n) = 0 SE n É UM ESTADO-OBJETIVO!!
Funções heurísticas são específicas para um determinado problema.
*
*
… Busca Gulosa (Greedy Search)
Algoritmo:
A “fila” é ordenada em ordem decrescente da estimativa de “quão bom” é um nodo.
Solucao bestFirstSearch(Problema problema, EvaluationFunction eval) { 
 fila = “uma função que ordena nodos via eval”;
 return treeSearch( problema, fila );
}
Solucao greedySearch(Problema problema) { 
 h = new HeuristicFunction(); 
 return bestFirstSearch( problema, h ); 
}
class HeuristicFunction extends EvaluationFunction { … }
*
*
De Arad a Bucareste
Heurística:
hDLR(n) = distância em linha reta de n ao objetivo
*
… De Arad a Bucareste
*
*
Busca Gulosa - Propriedades
Completeza: não (pode entrar em loop)
Ex: Considerando o problema de ir de Iasi a Fagaras, a busca gulosa pode ficar em loop: Iasi  Neamt  Iasi  Neamt...
Tempo: O(bm) (m é a profundidade máxima do espaço de busca)
Uma boa função heurística é essencial para melhorar o desempenho
Espaço: O(bm)
Mesma observação acima!
Otimalidade: não.
Pode levar à expansão desnecessária de nodos (exemplo acima).
É similar à busca em profundidade. Consegue sair de um dead end para continuar a busca (com marcação de nodos visitados).
*
*
Pesquisa A*
Combina a busca por custo uniforme com a busca gulosa.
Função de avaliação: f(n) = g(n) + h(n)
g(n): custo real do caminho do nodo inicial até n.
h(n): custo estimado do caminho mais barato de n até um estado-objetivo.
f(n): custo estimado do caminho mais barato do estado inicial até um estado-objetivo passando por n.
A* usa uma heurística admissível:
h é tal que h(n) ≤ h*(n) para todo n.
h*(n) dá o custo real de n até um objetivo.
Ou seja, uma heurística admissível nunca superestima o custo real!!!
Ex: hDLR
Solucao aStarSearch(Problema problema) {
 return bestFirstSearch(problema, f);
}
*
… De Arad a Bucareste – A*
*
*
Algoritmos de Aperfeiçoamento Iterativo
Algoritmos mantêm apenas o último estado gerado.
Para gerar o próximo estado, os algoritmos modificam (“aperfeiçoam”) o estado atual.
Aplicáveis em situações onde:
O caminho do estado inicial até o atual é irrelevante: o estado atual contém toda informação necessária para orientar a busca.
Ex: Problema do caixeiro viajante (TSP): inicia-se com uma rota possível e tenta-se melhorar a solução variando estradas (arestas) entre pares de cidades.
Espaço consumido é constante!
Exemplos:
Caixeiro viajante
Leiaute de VLSI
*
*
Duas classes de algoritmos de aperfeiçoamento iterativo:
 Hill-climbing (“subida de encosta”)
 É uma escalada
 É chamado 
gradiente descendente
(gradient descent) quando
a função de avaliação é 
vista como custo e não 
como qualidade (na área 
de redes neurais,
especialmente).
 Simulated annealing
Iniciar com uma configuração qualquer que é uma solução e fazer modificações para aperfeiçoar a solução já obtida.
O objetivo é encontrar um pico (máximo) na superfície do espaço de estados.
“Escalando o Everest com neblina forte e com amnésia...
Idéia Geral
*
*
Hill-climbing
void hillClimbing(Problema problema, EvaluationFunction eval) {
 Nodo corrente, proximo, melhor;
 int iteracao;
 iteracao = 0;
 melhor = “um valor inicial adequado”;
 repita
	 local = false;
	 corrente = “um valor inicial qualquer”;
	 repita
	 “seleciona todos os pontos na vizinhança de corrente”;
	 proximo = “o melhor entre os selecionados segundo eval”;
	 if ( eval( proximo ) > eval( corrente ) )
	 corrente = proximo;
	 else
	 local = true; 	// caiu em um máximo local
	 enquanto ( local == false );
 	 iteracao = iteracao + 1;
	 if ( eval( corrente ) > eval( melhor ) )
	 melhor = corrente;
 enquanto ( iteracao < MAX );
}
*
*
Hill-climbing Estocástico
void hillClimbing(Problema problema, EvaluationFunction eval) {
 Nodo corrente, proximo, melhor;
 int iteracao;
 iteracao = 0;
 corrente = “um valor inicial qualquer”;
 repita
 proximo = “um valor na vizinhança de corrente”;
	 “faça corrente = proximo de acordo com a probabilidade
	 dada por p( corrente, proximo )”;
	 iteracao = iteracao + 1;
	enquanto ( iteracao < MAX );
}
Apenas 1 loop.
A regra que diz quando mover
	de um ponto para outro é
	probabilística.
É possível que o próximo ponto seja pior que o atual.
Entretanto, a probabilidade de aceitação do próximo ponto depende da diferença de mérito entre ele e o atual [eval(corrente)-eval(proximo)] e
	do parâmetro T.
*
*
Hill-climbing Estocástico: Parâmetros
Qual o papel de T no algoritmo?
	Vamos supor que eval(corrente) = 107 e eval(proximo) = 120.
	Logo, eval(corrente) – eval(proximo) = -13, indicando que ó próximo ponto é melhor que o atual.
	Qual a probabilidade de aceitar o próximo ponto quando o valor de T varia?
Maior o valor de T, menor é a importância do mérito dos pontos em questão!
Quando T diminui, o algoritmo estocástico se transforma no ordinário!
*
*
Hill-climbing Estocástico: Parâmetros
Qual o papel de T no algoritmo?
	Vamos supor que eval(corrente) = 107.
	Logo, eval(corrente) – eval(proximo) = -13, indicando que ó próximo ponto é melhor que o atual.
	Suponhamos, também que T = 10.
	Qual a probabilidade de diversos candidatos a próximo ponto quando o valor de T se mantém fixo?
Se o novo ponto tem o mesmo mérito que o atual, então p = 0.5
Muito razoável: não importa qual deles!
Se o novo ponto é melhor então sua chance é maior que 0.5! E quanto melhor for, maior é a probabilidade de ele ser escolhido!
*
*
Simulated Annealing
Em vez de reiniciar de um outro local aleatoriamente escolhido...
IDÉIA:
Escapar de máximos locais permitindo alguns movimentos “ruins” (downhill) mas diminuindo progressivamente a amplitude e freqüência desses movimentos.
Simulated annealing é similar ao hill-climbing ordinário.
Simulated annealing é similar ao hill-climbing estocástico. 
Mas ele varia o parâmetro T durante a execução:
Inicia com valores maiores e decresce à medida que a solução melhora.
Ao final da execução, T é pequeno e o algoritmo é praticamente o mesmo que o hill-climbing ordinário.
T é chamado de “temperatura”.
Quando a temperatura é alta, movimentos “ruins” são mais prováveis e quando é baixa, são menos prováveis.
*
*
Simulated Annealing - Algoritmo
void simulatedAnnealing(Problema problema, EvaluationFunction eval) {
 Nodo corrente, proximo;
 int iteracao;
 iteracao = 0;
 “inicialize T”;
 corrente = “um valor inicial qualquer”;
 repita
	 repita
	 proximo = “um ponto na vizinhança de corrente”;
	 if ( eval( proximo ) > eval( corrente ) )
	 corrente = proximo;
	 else
	 if ( random( 0, 1 )
< )
		 corrente = proximo;
	 enquanto ( “condiçao de terminação não satisfeita” );
	 T = g( T, iteracao );	// função g atualiza a temperatura T
 	 iteracao = iteracao + 1;
 enquanto ( “critério de parada não satisfeito” );
}
*
*
Simulated Annealing - Considerações
Se a “temperatura” decresce suficientemente devagar, o máximo global é alcançado.
Aplicações práticas em leiaute de VLSI, escalonamento em linhas de produção, problemas de otimização em geral.
Questões dependentes do problema:
Qual o valor inicial de T?
Qual a condição de terminação?
Qual a taxa de diminuição da temperatura?
Quando parar o algoritmo?
*
*
Aplicando a Idéia de Hill Climbing: O Problema das Oito Rainhas
Como colocar 8 rainhas nas colunas de um tabuleiro de xadrez de modo que nenhuma possa atacar a outra?
Estados: posições das 8 rainhas, uma por coluna
Função sucessora: retorna todos os possíveis estados que resultam da movimentação de uma única rainha para outro quadrado na mesma coluna.
Função de avaliação (custo da heurística): número de pares de rainhas que podem se atacar direta ou indiretamente.
h = 17
h = 1
*
*
Algoritmos Genéticos
Os algoritmos genéticos (AGs) são um método (probabilístico) de pesquisa (busca) por soluções baseado na teoria da evolução.
A analogia foi proposta e desenvolvida por John Holland (anos 70).
O AG básico possui três operadores inspirados nos processos que ocorrem na natureza
Reprodução por seleção natural
Crossing over (crossover)
Mutação
Cada solução, chamada de um indivíduo, é representada como uma string de bits:
*
*
Algoritmo Genético Básico
0) Uma população inicial (um certo número de soluções) é gerada aleatoriamente, e a próxima geração é formada a partir da anterior repetindo-se os passos:
Calcule a adequação (fitness) de cada indivíduo. Se algum deles for “adequado o suficiente”, termine. Este indivíduo é a solução.
Repita até gerar uma nova população:
2.1) Selecione um par de indivíduos de maneira que os “mais adequados” tenham maior probabilidade de serem escolhidos para a reprodução e para cederem descendentes para a próxima geração (seleção natural darwiniana);
2.2) Cruze os indivíduos selecionados no passo 2.1) fazendo o crossover ou troca de partes dos indivíduos, de acordo com uma certa probabilidade (probabilidade de crossover [ 0.7, em geral)];
2.3) Deixe que alterações ocasionais ocorram em algum bit dos indivíduos segundo uma certa probabilidade [probabilidade de mutação ( 0.02, em geral)];
Volte ao passo 1.
*
*
Crossover: o cruzamento consiste na troca de partes entre dois indivíduos selecionados para compor a próxima geração da população de soluções candidatas, segundo a probabilidade de crossover.
Sejam os dois indivíduos:
			 (14910)
			 (22910)
Supondo que a posição escolhida (“sorteada”) seja 3, então, após o crossover, teríamos os indivíduos descendentes:
 (13710)
 (24610)
Algoritmos Genéticos: Operadores
*
. . . . . . 
*
*
Mutação: é a mudança do valor em uma posição de um indivíduo
Seja o indivíduo: 				(14910)
Se a posição 3 é escolhida (aleatoriamente) para sofrer mutação, o indivíduo resultante será:
					
								(18110)
Se for a posição 4:
								(13310)
Ou seja, há troca de bits (0  1 ou 1  0)
A mutação pode impedir que a busca por uma solução fique parada em um mínimo local.
... Algoritmos Genéticos: Operadores
*
*
... Algoritmos Genéticos: Operadores
Seleção: deve ser feita de modo que indivíduos mais adequados (com melhor fitness) tenham maiores chances (probabilidade) de serem escolhidos para cederem descendentes para a próxima geração.
Método clássico é conhecido como roleta. Seja a população:
*
*
Executando um AG Simples
Otimizar a função f(x) = x2, x variando entre 0 e 31 (5 bits)
*
*
Algoritmo Genético Básico: Questões de Implementação 
0) Uma população inicial (um certo número de soluções) é gerada aleatoriamente, e a próxima geração é formada a partir da anterior repetindo-se os passos:
Calcule a adequação (fitness) de cada indivíduo. Se algum deles for “adequado o suficiente”, termine. Este indivíduo é a solução.
Repita até gerar uma nova população:
2.1) Selecione um par de indivíduos de maneira que os “mais adequados” tenham maior probabilidade de serem escolhidos para a reprodução e para cederem descendentes para a próxima geração (seleção natural darwiniana);
2.2) Cruze os indivíduos selecionados no passo 2.1) fazendo o crossover ou troca de partes dos indivíduos, de acordo com uma certa probabilidade (probabilidade de crossover [ 0.7, em geral)];
2.3) Deixe que alterações ocasionais ocorram em algum bit dos indivíduos segundo uma certa probabilidade [probabilidade de mutação ( 0.02, em geral)];
Volte ao passo 1.
*
*
… Algoritmo Genético Básico: Questões de Implementação 
0) Uma população inicial (um certo número de soluções) é gerada aleatoriamente, e a próxima geração é formada a partir da anterior repetindo-se os passos:
*
*
… Algoritmo Genético Básico: Questões de Implementação 
Calcule a adequação (fitness) de cada indivíduo. Se algum deles for “adequado o suficiente”, termine. Este indivíduo é a solução.
Para uma implementação simples, pode-se terminar o AG quando um certo
número de gerações for executado.
Uma alternativa é avaliar o fitness médio da população ou o melhor 
fitness: caso eles não aumentem satisfatoriamente, o AG é fiinalizado. 
*
*
… Algoritmo Genético Básico: Questões de Implementação 
2) Repita até gerar uma nova população:
2.1) Selecione um par de indivíduos de maneira que os “mais adequados” tenham maior probabilidade de serem escolhidos para a reprodução e para cederem descendentes para a próxima geração (seleção natural darwiniana);
*
*
… Algoritmo Genético Básico: Questões de Implementação 
2) Repita até gerar uma nova população:
2.2) Cruze os indivíduos selecionados no passo 2.1) fazendo o crossover ou troca de partes dos indivíduos, de acordo com uma certa probabilidade (probabilidade de crossover [ 0.7, em geral)];
G G A – T C – G – – A 
	 - G G A T C G – – – A
*
*
… Algoritmo Genético Básico: Questões de Implementação 
2) Repita até gerar uma nova população:
2.3) Deixe que alterações ocasionais ocorram em algum bit dos indivíduos segundo uma certa probabilidade [probabilidade de mutação ( 0.02, em geral)];
G A A T T C A G T T A 
| | | | | | 
G G A – T C – G – – A 
*
Um estado alcançado a partir de um outro é chamado de sucessor.
*
Em um feriado, um agente está em Arad. Ele deve chegar em Bucareste até amanhã senão perderá o vôo ( só tem outro daqui a 15 dias!!)
*
MODIF
Um agente que deve ir de Arad para Bucareste deve decidir qual a SEQUÊNCIA DE AÇÕES o leva do estado inicial Em(Arad) ao estado objetivo Em(Bucareste).
*
Mundo do aspirador simplificado: apenas dois locais (quadrados)
*
*
*
Nos pares ação-estado, a ação é especificada ou executada por um operador.
No livro o equivalente a Mover(Arad, Zerind) é Ir(Zerind). Entretanto, esta última escolha é menos descritiva.
*
CUSTO TOTAL = CUSTO DE PESQUISA + CUSTO DO CAMINHO(SOLUÇÃO)
Em computação teórica e robótica, o custo de busca (pesquisa) – o que é feito antes da interação com o ambiente) é chamado de custo offline e o custo do caminho é chamado de custo online.
O ESTADO do mundo real inclui muito mais coisas que a descrição simples escohida para o problema ARAD-BUCARESTE. P. ex: qual veículo etá sendo utilizado, se está chovendo ou não etc.
*
MODIF
*
*
MODIF
*
Expansão de um estado é a geração de seus possíveis estados sucessores.
A Estratégia
de busca determina qual estado será o próximo a ser expandido.
*
*
O livro usa fila em vez de lista. Mas usa uma fila em que pode-se remover elementos que entraram por último na fila, logo é uma pilha. A estrutura de dados lista e a maneira como ela é utilizada diferenciam, em técnicas simples, a estratégia de busca
*
MODIF
FATOR DE RAMIFICAÇÃO: NÚMERO MÁXIMO DE filhos de qualquer nodo da árvore
OTIMALIDADE não existe no dicionário!!!
*
O nome best-first não é muito adequado pois se o melhor nodo sempre é expandido então não há busca, há uma marcha direta até o objetivo.
A medida do custo de uma solução deve incorporar uma estimativa do custo do caminho de um estado até o estado-objetivo mais próximo.
*
Erro na página 95: Nota de pé de página número 3 está cortada.
*
*
Só é possível calcular hDLR se as coordenadas das cidades forem conhecidas.
Essa é a informação extra dada pela heurística e que torna a busca mais eficiente.
*
*
MODIF
*
Heurísticas admissíveis são otimistas por natureza!!!
*
Erro de português na primeira linha da página 103.
*
*
O aperfeiçoamento iterativo faz uma busca local: apenas os estados vizinhos ao estado corrente são examinados. Nenhum estado “mais adiante” é examinado. Entretanto, esses algoritmos são muito utilizados na prática.
To anneal: 
A: aquecer e, então, esfriar (como com o vidro e o aço) geralmente para tornar menos rígido
B: esfriar vagarosamente (em um forno)
C: aquecer e, então, esfriar (ácido nucléicos) a fim de separar as duas fitas e induzir a combinação em uma temperatura mais baixa
Na verdade, annealing aqui vem do nome dado ao processo de, gradualmente, resfriar uma substância até seu congelamento
*
PROBLEMAS:
Máximos locais
Platôs
Cadeias ou estrias
Algoritmo é apenas um loop que, continuamente, move na direção de um valor maior.
Não mantém uma árvore de pesquisa. Os nodos necessitam guardar o estado e seu valor dado pela função de avaliação.
Quando há mais de um candidato a escolher, o algoritmo pode selecionar qualquer um (randomicamente).
Três problemas com essa política:
	1) Máximos locais: é um pico que é menor que o pico mais alto, no espaço de estados.. Se cair em um máximo local, o algoritmo pode parar em uma solução ruim, longe da melhor possível;
	2) Platôs: é uma área no espaço de estados em que a função de avaliação possui o mesmo valor. O algoritmo executa um “random walk”, ou passeio ao acaso e pode produzir resultados ruins ou ficar estacionado!
	3) Cadeias (estrias ou ridges): algoritmo pode oscilar entre soluções e progredir vagarosamente até o máximo global.
Random-restart hill-climbing: reinicia o algoritmo de um outro estado inicial. Isso é feito executando-se o algoritmo uma série de vezes até que cada execução pare ou não faça progresso algum. A solução é o melhor resultado encontrado até então por qualquer uma das execuções. Ele pode usar um número fixo de execuções ou pode continuar até que o melhor resultado NÃO tenha sido melhorado por um certo número de iterações. Claramente, se um número suficiente de execuções é realizado, o random-restart hill-climbing irá, eventualmente, encontrar uma solução.
Se a superfície gerada pelo espaço de soluções parecer-se com um porco-espinho (o que é verdade para a maioria dos problemas reais), hill-climbing irá mal... Ou a solução será pobre ou o número de execuções terá que ser muuuiito grande.
Mas, apesar disso, o algoritmo dá uma solução que pode ser apreciável...
*
*
Suponha que o próximo é MELHOR, ou seja, eval(próximo) > eval(corrente), então:
Se T é pequeno, logo o próximo é quase sempre “pego” (p quase igual a 1) (isto é: corrente  próximo, quase sempre)	
Se T é grande, logo o próximo é quase “sorteado” (p quase igual a 0.5)
Agora suponha que o próximo é PIOR, ou seja, eval(próximo) < eval(corrente), então:
Se T é pequeno, logo o próximo quase NUNCA é “pego” (p quase igual a 0) (isto é: quase NUNCA corrente  próximo)	
Se T é grande, logo o próximo é quase “sorteado” (p quase igual a 0.5)
*
*
Em vez de sempre tentar “hill climb”, permite-se fazer um “downhill” algumas vezes.
Uma analogia existe entre a temperatura e o grau de organização de um sistema e o comportamento do simulated annealing. Quanto maior a temperatura mais desorganizado tende a ser um sistema de partículas (maior temperatura, maior energia cinética e maior velocidade das partículas). Da mesma forma, no simulated annealing, maiores temperaturas permitem maior “desorganização” visto que movimentos “ruins” (downhill) serão mais prováveis.
*
*
*
*
*
O Passo 2 é chamado de uma geração do algoritmos genético.
*
Se os indivíduos não forem representados como strings de bits, uma nova forma de executar o crossover deve ser inventada.
*
*
Se os indivíduos não forem representados como strings de bits, uma nova forma de executar a mutação deve ser inventada.
*
*
*Observe que o indivíduo 3 original não participou do crossover enquanto o indivíduo 2 participou duas vezes.
*
O Passo 2 é chamado de uma geração do algoritmos genético.
*
O Passo 2 é chamado de uma geração do algoritmos genético.
*
O Passo 2 é chamado de uma geração do algoritmos genético.
*
O Passo 2 é chamado de uma geração do algoritmos genético.
*
O Passo 2 é chamado de uma geração do algoritmos genético.
*
O Passo 2 é chamado de uma geração do algoritmos genético.