AI - algoritmos de pesquisa populares

Pesquisar é a técnica universal de resolução de problemas em IA. Existem alguns jogos para um único jogador, como jogos de peças, Sudoku, palavras cruzadas, etc. Os algoritmos de pesquisa ajudam a pesquisar uma posição específica em tais jogos.

Problemas de Pathfinding de Agente Único

Os jogos como os quebra-cabeças 3X3 de oito peças, 4X4 de quinze peças e 5X5 de vinte e quatro peças são desafios para encontrar caminhos de um único agente. Eles consistem em uma matriz de ladrilhos com um ladrilho em branco. O jogador deve organizar as peças deslizando uma peça vertical ou horizontalmente em um espaço em branco com o objetivo de cumprir algum objetivo.

Os outros exemplos de problemas de localização de caminhos de agente único são o Problema do Caixeiro Viajante, o Cubo de Rubik e a Prova de Teorema.

Terminologia de Pesquisa

  • Problem Space- É o ambiente em que ocorre a pesquisa. (Um conjunto de estados e um conjunto de operadores para alterar esses estados)

  • Problem Instance - É o estado inicial + estado da meta.

  • Problem Space Graph- Representa um estado de problema. Os estados são mostrados por nós e os operadores são mostrados por arestas.

  • Depth of a problem - Comprimento do caminho mais curto ou da sequência mais curta de operadores do estado inicial ao estado objetivo.

  • Space Complexity - O número máximo de nós armazenados na memória.

  • Time Complexity - O número máximo de nós que são criados.

  • Admissibility - Uma propriedade de um algoritmo para sempre encontrar uma solução ótima.

  • Branching Factor - O número médio de nós filhos no gráfico do espaço do problema.

  • Depth - Comprimento do caminho mais curto do estado inicial ao estado de objetivo.

Estratégias de busca de força bruta

Eles são muito simples, pois não precisam de nenhum conhecimento específico do domínio. Eles funcionam bem com pequeno número de estados possíveis.

Requisitos -

  • Descrição do estado
  • Um conjunto de operadores válidos
  • Estado inicial
  • Descrição do estado da meta

Pesquisa em amplitude

Ele começa a partir do nó raiz, explora os nós vizinhos primeiro e avança para os vizinhos de nível seguinte. Ele gera uma árvore por vez até que a solução seja encontrada. Ele pode ser implementado usando a estrutura de dados da fila FIFO. Este método fornece o caminho mais curto para a solução.

E se branching factor(número médio de nós filhos para um determinado nó) = be profundidade = d, então o número de nós no nível d = b d .

O número total de nós criados no pior caso é b + b 2 + b 3 +… + b d .

Disadvantage- Como cada nível de nós é salvo para a criação do próximo, ele consome muito espaço de memória. A necessidade de espaço para armazenar nós é exponencial.

Sua complexidade depende do número de nós. Ele pode verificar nós duplicados.

Pesquisa em profundidade

É implementado em recursão com estrutura de dados de pilha LIFO. Ele cria o mesmo conjunto de nós que o método Largura-Primeiro, apenas na ordem diferente.

Como os nós no caminho único são armazenados em cada iteração da raiz ao nó folha, o requisito de espaço para armazenar os nós é linear. Com o fator de ramificação be a profundidade m , o espaço de armazenamento é bm.

Disadvantage- Este algoritmo não pode terminar e continuar infinitamente em um caminho. A solução para esse problema é escolher uma profundidade de corte. Se o corte ideal for d , e se o corte escolhido for menor que d , então este algoritmo pode falhar. Se o corte escolhido for maior que d , o tempo de execução aumentará.

Sua complexidade depende do número de caminhos. Não pode verificar nós duplicados.

Pesquisa bidirecional

Ele pesquisa para a frente do estado inicial e para trás do estado de objetivo até que ambos se encontrem para identificar um estado comum.

O caminho do estado inicial é concatenado com o caminho inverso do estado objetivo. Cada pesquisa é feita apenas até a metade do caminho total.

Pesquisa de custo uniforme

A classificação é feita no aumento do custo do caminho para um nó. Sempre expande o nó de menor custo. É idêntico à pesquisa de amplitude inicial se cada transição tiver o mesmo custo.

Explora caminhos em ordem crescente de custo.

Disadvantage- Pode haver vários caminhos longos com custo ≤ C *. A pesquisa de custo uniforme deve explorar todos eles.

Profundidade iterativa de aprofundamento - primeira pesquisa

Ele executa a pesquisa em profundidade até o nível 1, começa de novo, executa uma pesquisa completa em profundidade no nível 2 e continua dessa forma até que a solução seja encontrada.

Ele nunca cria um nó até que todos os nós inferiores sejam gerados. Ele apenas salva uma pilha de nós. O algoritmo termina quando encontra uma solução na profundidade d . O número de nós criados na profundidade d é b d e na profundidade d-1 é b d-1.

Comparação de várias complexidades de algoritmos

Vamos ver o desempenho dos algoritmos com base em vários critérios -

Critério Largura primeiro Profundidade primeiro Bidirecional Custo Uniforme Aprofundamento interativo
Tempo b d b m b d / 2 b d b d
Espaço b d b m b d / 2 b d b d
Optimalidade sim Não sim sim sim
Integridade sim Não sim sim sim

Estratégias de pesquisa informadas (heurísticas)

Para resolver grandes problemas com grande número de estados possíveis, o conhecimento específico do problema precisa ser adicionado para aumentar a eficiência dos algoritmos de pesquisa.

Funções de avaliação heurística

Eles calculam o custo do caminho ideal entre dois estados. Uma função heurística para jogos de peças deslizantes é calculada contando o número de movimentos que cada peça faz a partir de seu estado de objetivo e adicionando esse número de movimentos para todas as peças.

Pesquisa Heurística Pura

Ele expande os nós na ordem de seus valores heurísticos. Ele cria duas listas, uma lista fechada para os nós já expandidos e uma lista aberta para os nós criados, mas não expandidos.

Em cada iteração, um nó com um valor heurístico mínimo é expandido, todos os seus nós filhos são criados e colocados na lista fechada. Em seguida, a função heurística é aplicada aos nós filhos e eles são colocados na lista aberta de acordo com seu valor heurístico. Os caminhos mais curtos são salvos e os mais longos são descartados.

Uma pesquisa

É a forma mais conhecida de Melhor pesquisa inicial. Ele evita expandir caminhos que já são caros, mas expande os caminhos mais promissores primeiro.

f (n) = g (n) + h (n), onde

  • g (n) o custo (até agora) para chegar ao nó
  • h (n) custo estimado para ir do nó ao objetivo
  • f (n) custo total estimado do caminho de n até a meta. Ele é implementado usando a fila de prioridade aumentando f (n).

Greedy Best First Search

Ele expande o nó que se estima estar mais próximo do objetivo. Ele expande os nós com base em f (n) = h (n). Ele é implementado usando a fila de prioridade.

Disadvantage- Pode ficar preso em loops. Não é o ideal.

Algoritmos de pesquisa local

Eles começam com uma solução prospectiva e, em seguida, passam para uma solução vizinha. Eles podem retornar uma solução válida mesmo se ela for interrompida a qualquer momento antes de terminar.

Pesquisa de escalada

É um algoritmo iterativo que começa com uma solução arbitrária para um problema e tenta encontrar uma solução melhor alterando um único elemento da solução de forma incremental. Se a mudança produzir uma solução melhor, uma mudança incremental será considerada uma nova solução. Este processo é repetido até que não haja mais melhorias.

função Hill-Climbing (problema), retorna um estado que é um máximo local.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage - Este algoritmo não é completo nem ideal.

Pesquisa de feixe local

Nesse algoritmo, ele contém k número de estados a qualquer momento. No início, esses estados são gerados aleatoriamente. Os sucessores desses k estados são calculados com a ajuda da função objetivo. Se algum desses sucessores for o valor máximo da função objetivo, o algoritmo para.

Caso contrário, os (k estados iniciais ek número de sucessores dos estados = 2k) estados são colocados em um pool. O pool é então classificado numericamente. Os k estados mais altos são selecionados como novos estados iniciais. Este processo continua até que um valor máximo seja alcançado.

a função BeamSearch ( problema, k ), retorna um estado de solução.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

Recozimento simulado

Recozimento é o processo de aquecimento e resfriamento de um metal para alterar sua estrutura interna para modificar suas propriedades físicas. Quando o metal esfria, sua nova estrutura é apreendida, e o metal retém suas propriedades recém-obtidas. No processo de recozimento simulado, a temperatura é mantida variável.

Inicialmente definimos a temperatura alta e depois permitimos que ela 'esfrie' lentamente conforme o algoritmo prossegue. Quando a temperatura está alta, o algoritmo pode aceitar soluções piores com alta frequência.

Começar

  • Inicializar k = 0; L = número inteiro de variáveis;
  • De i → j, pesquise a diferença de desempenho Δ.
  • Se Δ <= 0 então aceite else if exp (-Δ / T (k))> random (0,1) então aceite;
  • Repita as etapas 1 e 2 para as etapas L (k).
  • k = k + 1;

Repita as etapas 1 a 4 até que os critérios sejam atendidos.

Fim

Problema do caixeiro viajante

Nesse algoritmo, o objetivo é encontrar um passeio de baixo custo que começa em uma cidade, visita todas as cidades no trajeto exatamente uma vez e termina na mesma cidade de partida.

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end