ALGORITMOS DE INTELIGÊNCIA ARTIFICIAL (IA) NAS ESTRATÉGIAS DE BUSCAS:

Definições, aplicações práticas e exemplos de códigos em linguagem Python

Por Ricardo Costa Val do Rosario

1 - Introdução

 As estratégias de busca são a espinha dorsal de muitos sistemas inteligentes. 

- No campo da IA, elas são utilizadas para encontrar soluções em espaços de estados, ou seja, 
em ambientes onde decisões precisam ser tomadas com base em condições e regras específicas. 

- Desde os primórdios da IA simbólica até os modernos sistemas de navegação e robótica autônoma, algoritmos de busca 
vêm desempenhando papel central na resolução de problemas complexos, muitas vezes invisíveis aos olhos do usuário final.

- A lógica desses algoritmos é simples, mas poderosa: explorar possibilidades de forma sistemática para alcançar um 
objetivo definido. 

- A escolha entre buscas não informadas, que não utilizam conhecimento prévio do problema, e buscas informadas, que se apoiam
em heurísticas, determina o desempenho e a eficiência de muitas aplicações práticas.

Entender como funcionam algoritmos como Busca em Largura (BFS), Busca em Profundidade (DFS), A* e Busca Gulosa 
(Greedy Search) é essencial para projetar sistemas de IA eficientes, desde jogos e simulações até sistemas críticos, 
como planejamento hospitalar, logística, sistemas embarcados e robótica médica.

Este documento propõe revisar suas definições e apresentar aplicações reais e exemplos em Python, 
contribuindo para o desenvolvimento de soluções inteligentes com base sólida.

2 – Exemplos

Exemplo 1: Busca em Largura (BFS – Breadth-First Search)

• Esse algoritmo explora todos os vizinhos de um nó antes de descer de nível.
• Ideal para encontrar o caminho mais curto em grafos não ponderados.

from collections import deque

def bfs(grafo, inicio, objetivo):
    fila = deque([[inicio]])
    visitados = set()

    while fila:
        caminho = fila.popleft()
        no = caminho[-1]
        
        if no == objetivo:
            return caminho
        
        elif no not in visitados:
            for vizinho in grafo.get(no, []):
                novo_caminho = list(caminho)
                novo_caminho.append(vizinho)
                fila.append(novo_caminho)
            
            visitados.add(no)

    return None

Exemplo de uso
grafo = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("Caminho encontrado:", bfs(grafo, 'A', 'F'))
Saída esperada:
Caminho encontrado: ['A', 'C', 'F']

Exemplo 2: Busca em Profundidade (DFS – Depth-First Search)

• Esse algoritmo vai fundo em um caminho antes de tentar outros.
• É útil para explorar todas as possibilidades ou encontrar soluções em profundidade.

def dfs(grafo, inicio, objetivo, caminho=None, visitados=None):
    if caminho is None:
        caminho = [inicio]
    if visitados is None:
        visitados = set()

    visitados.add(inicio)

    if inicio == objetivo:
        return caminho

    for vizinho in grafo.get(inicio, []):
        if vizinho not in visitados:
            novo_caminho = dfs(grafo, vizinho, objetivo, caminho + [vizinho], visitados)
            if novo_caminho:
                return novo_caminho

    return None

Exemplo de uso
print("Caminho encontrado:", dfs(grafo, 'A', 'F'))
Saída esperada (pode variar):
Caminho encontrado: ['A', 'B', 'E', 'F']

Exemplo 3: A*

• O A* é uma busca informada que combina o custo do caminho até o momento (g) com uma estimativa heurística do custo até o objetivo (h).
• É eficiente e geralmente retorna à solução ótima, quando a heurística é admissível.
• A heurística será a distância em linha reta até o destino.

import heapq

def a_estrela(grafo, inicio, objetivo, heuristica):
    fila = []
    heapq.heappush(fila, (0, [inicio]))
    visitados = set()

    while fila:
        custo_total, caminho = heapq.heappop(fila)
        no_atual = caminho[-1]

        if no_atual == objetivo:
            return caminho

        if no_atual in visitados:
            continue

        visitados.add(no_atual)

        for vizinho, custo in grafo.get(no_atual, []):
            if vizinho not in visitados:
                novo_caminho = caminho + [vizinho]
                g = custo_total - heuristica[no_atual] + custo
                f = g + heuristica[vizinho]
                heapq.heappush(fila, (f, novo_caminho))

    return None

Heurística (distância estimada até F)
heuristica = {
    'A': 7,
    'B': 6,
    'C': 2,
    'D': 4,
    'E': 1,
    'F': 0
}

print("Caminho encontrado:", a_estrela (heuristica))
Saída esperada:
Caminho encontrado: ['A', 'C', 'F']