• Baseado no PEAS
• Continua interação com o meio ambiente
• Estado inicial t = 0
• Ações Possíveis → Função ACTIONS(s) dado un estado s
• Modelo de transição: a função RESULTS(s,a) retorna o estad oresultante de uma ação
• teste de meta: função GOAL(s) determina se o estado s é um estade de meta
• Custo de caminho: a função PATHCOST(h) retorna o custo acossiado um sequencia $h = s_0, a_0, ... , S_{t_1}, a_{t-1}, s_t$.
• O Custo de uma sequência pode ser nodelado por uma função de custo local $c: S \times A \times S \rarr \Re$
  • $PATHCOST(h) = \sum^{T-1}{t=0} c(s_t,a_t,s{t+1})$
  • $GOAL(s_t) \in\{TRUE, FALSE\} or \\ GOAL(S_T \in B$
• Busca por solução

função **Busca**(problema) **retorna** uma solução ou falha:
	inicializar a fronteira usando o estado inicial do problema
	inicializar o conjunto explorado como vazio
	**repita**:
			**se** fronteira vazia:
				**Retorna** falha
			escolher um nó folha e remover da fronteira
			**se** o estado do nó for um estao objetivo
				**então retorna** solução correspondente
			adicionar o nó ao conjunto explorado
			expandi io nó escolhido encontrado os próximos nós
			para cada próximo nó
				**se** não estiver na fronteira nem no conjunto explorado
					**então** adiciona á fronteira

• Tipos de Busca
  • FIFO → Busca em largura
  • LIFO → Busca em profundidade
  • Fila de prioridade: custo parcial + conhecimento a priori
• Em:
  • Busca cega: não sabe qual o melhor nó da fronteira a ser expandido, apenas distingue o estado objetivo do não objetivos
  • Busca Informada ou heurística: estima qual o melhor nó da fronteira a ser expanddo com base em funções heurísticas. Sabbem se um estado não objetivo é o mais promissor
  • Busca Local: Operam em um único estado e movem-se para a vizinhança desse estado
• Avaliação de Algoritimo
  • Completude: a estratégia garante encontrar um solução, se existir uma?
  • Otimalidade: a estratéfia encontra a solução ótima
  • Complexidade de tempo: Tempo gasto em uma solução?
  • Complexidade de memória: quanto de memória é preciso?
• Grafo dirigido é sempre obtido implicitamente
• Complexidade em termos de:
  • Fator de ramificação b: númeoro máximo de sucesores
  • Profundidade d: profundidade do nó objetivo menos profundo
  • Comprimento máximo m: comprimento máximo de qualquer caminho no espaço dos estados
• Busca em largura
  • Observa lateralmente a arvore
  • Completude: Em um tempo finito ele gera todos os caminhos até certo nível
  • Otimalidade: Se o custo de ação for uniforme ela ferará uma solução ótima
  • complexidade de tempo: $O(b^d) ou O(b^{d+1})$, dependendo da implementação
  • Complexidade de memória: $O(b^d)$
  • Alto custo, certeza de solução
• Busca em profundidade:
  • Observa por um caminho inteiro, antes de voltar e tentar outro caminho
  • Completude: Apensa se a quantidade de estados for finita
  • Otimalidade: Não é garantida
  • Complexidade de tempo: No pior dos casos é $O(b^m)$
  • Complexidade de memória: Se a implementação permite nós repetidos,$O(bm)$
• Busca em profundidade Limitada: Considera um limite de profundidad e l
  • completude: se $d \le l$
  • Otimialidade: Não garantida
  • Complexidade de tempo: No pior dos casos bode resultar em $O(b^l)$
  • Complexidade de memória: em uma implementação que permite nós recebidos, $O(bl)$
• Busca em profundidade iterativa: executa instâncias da busca em profundidad limitada com l crescete, isto é, $l = l_0 * i | i \in \N$
  • Completude; Garantida
  • Otimalidade Garantida apenas se o custo dado é em função da rocundidade
  • Complexidade de tempo: no pior do casso $O(b^l)$
  • Complexidade de memória: em uma implementaçaõ que permite nís recevidos, $O(bl)$
• Busco de custo uniforme: Considera o custo da ação
  • Utiliza Fila de prioridade, testa o nó somente antes de explandilo para procurar solução ótima e substitui estados já passados se o custo for menot
  • Completude: Garantida se o custo é semre crescente
  • Otimalidade: Garantida, se o custo é sempre crescente
  • complexidade de tempo: $O(b^{1 + \lfloor C / \epsilon \rfloor})$*
  • Complexidade de memória: $O(b^{1 + \lfloor C / \epsilon \rfloor})$*