Tudo sobre Busca Informada em Inteligência Artificial

A busca informada é um tipo de algoritmo de busca que usa conhecimento específico do domínio para guiar sua busca através de um espaço de problema. De sistemas de navegação a jogos, processamento de linguagem natural para gerenciamento da cadeia de suprimentos e busca mais informada em inteligência artificial reduziu significativamente a quantidade de tempo e recursos computacionais necessários para resolver diferentes problemas.

Ao usar o conhecimento específico do domínio para orientar a pesquisa, os algoritmos de pesquisa informados podem eliminar rapidamente caminhos irrelevantes ou menos promissores, permitindo que a pesquisa se concentre nas opções mais promissoras. Para fazer isso, esses tipos de algoritmos de busca em IA usam heurísticas para melhorar a eficiência e a velocidade da busca.

Inscreva-se no Curso de Machine Learning das melhores universidades do mundo. Ganhe programas de certificação Master, Executive PGP ou Advanced para acelerar sua carreira.

Este artigo irá discutir o conceito de busca informada em inteligência artificial, suas funções heurísticas, exemplos de algoritmos e suas vantagens e desvantagens.

função heurística

Em termos simples, uma função heurística é uma abordagem de resolução de problemas que usa uma regra prática ou um “melhor palpite” para estimar a distância ou o custo para um estado objetivo em um problema de pesquisa. A função heurística estima quão longe o estado objetivo está do estado atual, o que pode ser usado para guiar um algoritmo de busca em direção ao objetivo.

Os algoritmos de pesquisa informada usam essas funções como uma fonte adicional de informações para tomar decisões informadas sobre qual caminho seguir. Por esse motivo, funções heurísticas são essenciais em algoritmos de busca informada.

Exemplos da vida real da função heurística

Para entender melhor as funções heurísticas, aqui estão alguns exemplos da vida real:

• No clássico jogo de “quebra-cabeças deslizantes”, uma função heurística simples pode ser contar o número de peças fora do lugar na configuração atual em comparação com a configuração do objetivo. Quanto mais blocos fora do lugar, mais distante o estado atual está do estado objetivo.
• No xadrez, uma função heurística poderia ser atribuir um valor a cada peça no tabuleiro com base em sua força e posição relativas e usar a soma desses valores para estimar a vantagem ou desvantagem do jogador atual. Essa função heurística pode ser usada para guiar um algoritmo de busca em direção a movimentos que provavelmente resultarão em uma posição melhor.

Com isso resolvido, vamos agora avançar e entender alguns dos exemplos mais usados ​​de algoritmos de busca informada em inteligência artificial.

Exemplos de Algoritmos de Pesquisa Informada

Dois dos algoritmos de pesquisa informada mais comumente usados ​​incluem a melhor primeira pesquisa e a pesquisa A*. Vamos entender esses dois algoritmos junto com alguns exemplos, vantagens, desvantagens e sua implementação em Python:

1. Melhor primeira pesquisa

A melhor primeira busca é um algoritmo de busca que expande primeiro o nó mais promissor, de acordo com uma função heurística. O algoritmo começa no nó inicial e examina todos os seus nós filhos, escolhendo o filho com o menor valor heurístico como o próximo nó a explorar. Este processo continua até que o nó objetivo seja encontrado ou todos os nós tenham sido explorados.

Melhor primeira pesquisa – um exemplo ilustrado

Aqui está um exemplo simples para ilustrar a melhor primeira pesquisa:

Suponha que você esteja tentando encontrar o caminho mais curto de sua casa até um supermercado próximo. Você conhece a distância até o supermercado de alguns locais próximos, mas não sabe a rota exata a seguir. Para resolver esse problema usando a pesquisa do melhor primeiro, você pode:

1. Comece no local de sua casa e calcule o valor heurístico para cada local próximo com base na distância até o supermercado.
2. Escolha o local próximo com o menor valor heurístico como o próximo nó a explorar.
3. Calcule o valor heurístico para cada um dos locais de seus filhos a partir desse local próximo e escolha aquele com o menor valor heurístico como o próximo nó a explorar.
4. Repita esse processo até chegar ao supermercado.

Melhor primeira pesquisa – implementação do Python

Veja como você pode implementar o melhor primeiro algoritmo de pesquisa em Python:

importar heapq

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# inicializa a fronteira e o conjunto explorado

fronteira = [(heuristic_func(start_state, goal_state), start_state)]

explorado = set()

# inicializa o caminho e o custo

caminho = {}

custo = {}

path[start_state] = Nenhum

custo[estado_inicial] = 0

enquanto fronteira:

# obtém o nó com o menor valor heurístico da fronteira

(h, current_state) = heapq.heappop(fronteira)

if current_state == goal_state:

# retorna o caminho se o estado objetivo for atingido

caminho de retorno

explorado.add(current_state)

# gera possíveis ações a partir do estado atual

para ação em action_func(current_state):

próximo_estado = ação(estado_atual)

# calcula o custo do novo caminho

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

se next_state não estiver explorado e next_state não estiver em [estado para (h, estado) na fronteira]:

# adiciona o novo estado à fronteira

heapq.heappush(frontier, (heuristic_func(next_state, goal_state), next_state))

path[next_state] = current_state

custo[próximo_estado] = novo_custo

# retorna None se o estado do objetivo não for alcançável

retornar nenhum

Como você pode ver, você precisará definir as seguintes funções:

• heuristic_func(current_state, goal_state): Esta função recebe o estado atual e o estado objetivo como entradas e retorna uma estimativa do custo de atingir o estado objetivo a partir do estado atual.
• action_func(current_state): Esta função recebe o estado atual como entrada e retorna uma lista de ações que podem ser realizadas a partir do estado atual.
• cost_func(current_state, action, next_state): Esta função usa o estado atual, uma ação e o próximo estado como entradas e retorna o custo de executar a ação do estado atual para o próximo estado.

Exemplo de melhor primeira pesquisa

estado_inicial = (0, 0)

meta_estado = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(estado_atual[0] – estado_objetivo[0]) + abs(estado_atual[1] – estado_objetivo[1])

def action_func(current_state):

ações = []

se estado_atual[0] > 0:

ações.append(lambda estado: (estado[0]-1, estado[1]))

se estado_atual[0] < 4:

ações.append(lambda estado: (estado[0]+1, estado[1]))

se estado_atual[1] > 0:

ações.append(lambda estado: (estado[0], estado[1]-1))

se estado_atual[1] < 4:

ações.append(lambda estado: (estado[0], estado[1]+1))

ações de retorno

def cost_func(current_state, action, next_state):

retornar 1

path = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

se caminho:

# construa o caminho do estado inicial até o estado objetivo

estado_atual = estado_meta

enquanto current_state != start_state:

print(estado_atual)

estado_atual = caminho[estado_atual]

print(start_state)

outro:

print(“O estado da meta não é alcançável.”)

Vantagens da melhor primeira pesquisa

• Em comparação com a busca em largura, a complexidade de tempo da busca pelo melhor primeiro é menor.
• A melhor primeira busca obtém e implementa as vantagens dos algoritmos BFS e DFS

Desvantagens da melhor primeira pesquisa

• Às vezes, pode cobrir mais distância do que o considerado.
• As chances de ficar preso em um loop são altamente prováveis.

Uma pesquisa

A* search é um algoritmo de busca que usa tanto o custo de alcançar um nó a partir do nó inicial quanto uma estimativa do custo restante para alcançar o nó objetivo para guiar sua busca. O algoritmo começa no nó inicial e examina todos os seus nós filhos, escolhendo o filho com o menor custo combinado e custo restante estimado como o próximo nó a explorar. Este processo continua até que o nó objetivo seja encontrado ou todos os nós tenham sido explorados.

Pesquisa A* – um exemplo ilustrado

Vamos reexaminar o exemplo anterior de você tentando encontrar a rota mais curta de sua casa até um supermercado próximo. Agora, você poderia:

1. Comece no local de sua casa e calcule o custo total para chegar a cada local próximo como a soma da distância de sua casa até esse local e o custo restante estimado para chegar ao supermercado a partir desse local.
2. Escolha o local próximo com o menor custo total como o próximo nó a explorar.
3. A partir desse local próximo, calcule o custo total para cada um de seus locais filhos como a soma da distância desse local até o local filho, o custo para chegar a esse local a partir do nó inicial e o custo restante estimado para chegar ao supermercado daquele local filho. Escolha o local filho com o menor custo total como o próximo nó a explorar.
4. Repita esse processo até chegar ao supermercado.

Uma coisa importante a observar aqui é que A* Search é um algoritmo de busca ideal que garante encontrar o caminho mais curto para o estado objetivo. É eficiente em problemas com grande espaço de busca e é amplamente utilizado em videogames, robótica e planejamento de rotas. No entanto, requer uma função heurística bem definida para ser eficaz. Por esse motivo, o algoritmo pode consumir muita memória e ser lento em problemas complexos com muitos nós.

Pesquisa A* – implementação do Python

Aqui está como você pode implementar o algoritmo de busca A* usando a programação Python:

importar heapq

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# inicializa a fronteira e o conjunto explorado

fronteira = [(heuristic_func(start_state, goal_state), start_state)]

explorado = set()

# inicializa o caminho e o custo

caminho = {}

custo = {}

path[start_state] = Nenhum

custo[estado_inicial] = 0

enquanto fronteira:

# obtém o nó com o menor valor f da fronteira

(f, current_state) = heapq.heappop(fronteira)

if current_state == goal_state:

# retorna o caminho se o estado objetivo for atingido

caminho de volta

explorado.add(current_state)

# gera possíveis ações a partir do estado atual

para ação em action_func(current_state):

próximo_estado = ação(estado_atual)

# calcula o custo do novo caminho

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

se next_state não estiver explorado e next_state não estiver em [estado para (f, estado) na fronteira]:

# adiciona o novo estado à fronteira

heapq.heappush(frontier, (new_cost + heuristic_func(next_state, goal_state), next_state))

path[next_state] = current_state

custo[próximo_estado] = novo_custo

elif next_state in [state for (f, state) in frontier] e new_cost < cost[next_state]:

# atualiza o custo do estado existente na fronteira

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontier[index] = (new_cost + heuristic_func(next_state, goal_state), next_state)

path[next_state] = current_state

custo[próximo_estado] = novo_custo

# retorna None se o estado do objetivo não for alcançável

retornar nenhum

Principais cursos de aprendizado de máquina e cursos de IA on-line

Exemplo de Pesquisa A*

Aqui está um exemplo de como você pode usar a função astar_search com estas funções:

estado_inicial = (0, 0)

meta_estado = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(estado_atual[0] – estado_objetivo[0]) + abs(estado_atual[1] – estado_objetivo[1])

def action_func(current_state):

ações = []

se estado_atual[0] > 0:

ações.append(lambda estado: (estado[0]-1, estado[1]))

se estado_atual[0] < 4:

ações.append(lambda estado: (estado[0]+1, estado[1]))

se estado_atual[1] > 0:

ações.append(lambda estado: (estado[0], estado[1]-1))

se estado_atual[1] < 4:

ações.append(lambda estado: (estado[0], estado[1]+1))

ações de retorno

def cost_func(current_state, action, next_state):

retornar 1

path = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

se caminho:

# construa o caminho do estado inicial até o estado objetivo

estado_atual = estado_meta

enquanto current_state != start_state:

print(estado_atual)

estado_atual = caminho[estado_atual]

print(start_state)

outro:

print(“O estado da meta não é alcançável.”)

Vantagens da Pesquisa A*

• É uma das principais técnicas heurísticas.
• Uma pesquisa * pode ser aproveitada para resolver problemas de pesquisa complexos

Habilidades de aprendizado de máquina em alta

Desvantagens da Pesquisa A*

• O desempenho da pesquisa A* depende muito da precisão dos algoritmos heurísticos.
• Tem baixa eficiência de pesquisa.

Blogs populares de IA e ML e cursos gratuitos

Remover

Algoritmos de busca informados são essenciais em inteligência artificial, pois permitem que o computador procure um estado de objetivo de forma eficiente e eficaz. Esses algoritmos usam funções heurísticas para estimar o custo de cada movimento possível e guiar o processo de busca em direção ao estado objetivo. Best First Search e A* Search são exemplos de algoritmos de pesquisa informada amplamente utilizados em vários campos. No entanto, uma função heurística bem definida é fundamental para o sucesso dos algoritmos de busca informados.

Se você estiver interessado em aprender mais sobre inteligência artificial e aprendizado de máquina, confira o programa de mestrado em aprendizado de máquina e inteligência artificial da upGrad, oferecido pela Liverpool John Moores University . Este programa abrange vários tópicos de aprendizado de máquina e IA, incluindo algoritmos como pesquisa informada. Ao fazer este programa, você pode obter as habilidades e os conhecimentos necessários para ter sucesso em uma variedade de carreiras relacionadas à IA.

Você também pode conferir nossoscursos gratuitosoferecidos pela upGrad em Gestão, Ciência de Dados, Machine Learning, Marketing Digital e Tecnologia.Todos esses cursos têm recursos de aprendizado de alto nível, palestras ao vivo semanais, atribuições do setor e um certificado de conclusão do curso - tudo gratuito!