Busca em Profundidade (DFS)

• Explora um caminho completamente antes de retroceder.
• Utiliza uma pilha (LIFO).
• Pode ser implementada recursivamente.
• Ideal quando soluções estão em grande profundidade.

Funcionamento do DFS

1. Visita o nó inicial.
2. Seleciona um sucessor ainda não visitado.
3. Repete até atingir folha ou objetivo.
4. Retrocede (backtracking) quando necessário.

Pseudocódigo DFS

def dfs(no, visitados):
    if no in visitados:
        return

    visitados.add(no)

    if objetivo(no):
        return no

    for vizinho in no.vizinhos:
        resultado = dfs(vizinho, visitados)
        if resultado:
            return resultado

Complexidade do DFS

• Tempo: O(b^m)
• Memória: O(bm)

Onde:

• b = fator de ramificação
• m = profundidade máxima

Vantagens do DFS

• Baixo consumo de memória.
• Implementação simples.
• Excelente para espaços muito profundos.
• Útil em backtracking e detecção de ciclos.

Desvantagens do DFS

• Não garante solução ótima.
• Pode entrar em loops sem controle de visitados.
• Pode explorar caminhos muito longos desnecessariamente.
• Não é completo em espaços infinitos.

Aplicações do DFS

• Resolução de labirintos.
• Ordenação topológica.
• Componentes conectados.
• Problemas de backtracking.
• Busca em jogos.

Busca em Largura (BFS)

• Explora todos os nós de um nível antes do próximo.
• Utiliza uma fila (FIFO).
• Encontra o caminho mais curto em grafos não ponderados.
• É completa e ótima sob custo uniforme.

Funcionamento do BFS

1. Insere o nó inicial na fila.
2. Remove o primeiro nó.
3. Expande seus sucessores.
4. Repete até encontrar o objetivo.

Pseudocódigo BFS

from collections import deque

def bfs(inicio):
    fila = deque([inicio])
    visitados = {inicio}

    while fila:
        no = fila.popleft()

        if objetivo(no):
            return no

        for vizinho in no.vizinhos:
            if vizinho not in visitados:
                visitados.add(vizinho)
                fila.append(vizinho)

Complexidade do BFS

• Tempo: O(b^d)
• Memória: O(b^d)

Onde:

• b = fator de ramificação
• d = profundidade da solução

Vantagens do BFS

• Completo.
• Ótimo para custos uniformes.
• Encontra a solução mais rasa.
• Excelente para caminhos mínimos.

Desvantagens do BFS

• Consome muita memória.
• Torna-se inviável em espaços grandes.
• Expansão exponencial.

Aplicações do BFS

• Menor caminho em grafos.
• Redes sociais.
• Web crawling.
• Propagação em redes.
• Roteamento.

Comparação Direta

* Em grafos não ponderados.

2. Heurísticas

"Uma heurística estima o quão próximo estamos da solução."

• Função h(n)
• Estimativa de custo restante
• Guia a busca

Exemplo de Heurística

Problema das cidades:

• h(n) = distância em linha reta até o destino
• Quanto menor, melhor

3. Hill Climbing

• Busca gulosa local
• Sempre escolhe o melhor vizinho
• Não considera caminhos alternativos

Algoritmo

enquanto houver melhoria:
    gerar vizinhos
    escolher melhor vizinho
    mover para ele

Vantagens

• Muito rápido
• Baixo consumo de memória
• Simples de implementar

Problemas

• Máximos locais
• Platôs
• Cristas
• Dependência do ponto inicial

Solução

• Random Restart
• Simulated Annealing
• Múltiplas inicializações

4. Beam Search

• Generalização da BFS
• Mantém apenas os k melhores nós
• k = largura do feixe

Funcionamento

1. Expande todos os nós do nível atual
2. Ordena pela heurística
3. Mantém somente os melhores

Trade-off

Busca A* (A-Star)

A* é um dos algoritmos de busca heurística mais importantes da Inteligência Artificial. Ele combina o custo já percorrido com uma estimativa do custo restante.

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

Componentes da Função

• g(n): custo real do início até o nó atual.
• h(n): estimativa heurística até o objetivo.
• f(n): custo total estimado.

O algoritmo sempre expande o nó com menor valor de f(n).

Ideia Central

• Une busca de custo uniforme com heurísticas.
• Balanceia exploração e direcionamento.
• Reduz drasticamente o espaço de busca.
• Quando a heurística é adequada, encontra a solução ótima rapidamente.

Algoritmo

1. Inserir o estado inicial na fila de prioridade.
2. Selecionar o nó com menor f(n).
3. Se for o objetivo, encerrar.
4. Expandir sucessores.
5. Atualizar custos e reinserir quando necessário.

Pseudocódigo

def a_star(inicio, objetivo):
    aberta = PriorityQueue()
    aberta.put((0, inicio))

    g = {inicio: 0}
    pai = {}

    while not aberta.empty():
        _, atual = aberta.get()

        if atual == objetivo:
            return reconstruir_caminho(pai, atual)

        for vizinho, custo in atual.vizinhos:
            novo_g = g[atual] + custo

            if vizinho not in g or novo_g < g[vizinho]:
                g[vizinho] = novo_g
                f = novo_g + heuristica(vizinho)
                aberta.put((f, vizinho))
                pai[vizinho] = atual

Exemplo Prático

Encontrar rota entre duas cidades.

• g(n): distância percorrida.
• h(n): distância em linha reta.
• f(n): estimativa total.

Heurística Admissível

Uma heurística é admissível quando nunca superestima o custo real.

h(n) ≤ h*(n)

• Garantia de optimalidade.
• Nunca ignora o melhor caminho.

Heurística Consistente

h(n) ≤ c(n,n') + h(n')

• Satisfaz desigualdade triangular.
• Evita reexpansões desnecessárias.
• Melhora eficiência prática.

Optimalidade

• Completo, desde que os custos sejam positivos.
• Ótimo com heurística admissível.
• Eficiência superior à busca de custo uniforme.

Complexidade

• Pior caso: exponencial.
• Depende fortemente da qualidade da heurística.
• Quanto melhor a heurística, menor a expansão.

Comparação com Outros Algoritmos

Aplicações

• Roteamento GPS.
• Planejamento robótico.
• Pathfinding em jogos.
• Logística e otimização.
• Planejamento automático.

Exemplo em Jogos

• Movimentação de NPCs.
• Navegação em mapas com obstáculos.
• Busca eficiente em grids.

Limitações

• Consumo elevado de memória.
• Dependência da heurística.
• Pode degradar para Dijkstra.

6. Minimax

• Escolha ótima contra adversário perfeito
• Propaga valores da folha para a raiz

Regra

• MAX escolhe maior valor
• MIN escolhe menor valor

Pseudocódigo

minimax(nó):
    se folha:
        retorna valor
    se MAX:
        retorna máximo dos filhos
    se MIN:
        retorna mínimo dos filhos

Complexidade

O(b^d)

• b = fator de ramificação
• d = profundidade

7. Poda Alpha-Beta

• Otimiza Minimax
• Evita explorar ramos inúteis

Parâmetros

• α: melhor valor para MAX
• β: melhor valor para MIN

Critério de Corte

Se α ≥ β, pode podar.

Benefícios

• Mesmo resultado do Minimax
• Muito menos avaliações
• Permite maior profundidade

Computação Evolutiva

Meta-Heurísticas Inspiradas na Natureza

A Computação Evolutiva reúne técnicas de otimização baseadas nos princípios da evolução biológica, como seleção natural, reprodução e mutação.

O que é uma Meta-Heurística?

• Estratégia geral de busca e otimização.
• Aplicável a uma grande variedade de problemas.
• Não garante optimalidade global.
• Busca soluções de alta qualidade em tempo viável.

"Boas soluções, rapidamente, para problemas difíceis."

Principais Meta-Heurísticas

• Algoritmos Genéticos
• Simulated Annealing
• Particle Swarm Optimization
• Ant Colony Optimization
• Evolution Strategies

Algoritmos Genéticos

Propostos por John Holland na década de 1970, simulam a evolução de uma população de soluções candidatas.

• População de indivíduos
• Seleção natural
• Cruzamento
• Mutação
• Sobrevivência dos mais aptos

Representação dos Indivíduos

• Cada solução é um cromossomo.
• Pode ser binário, inteiro ou real.
• Genes representam variáveis do problema.

Exemplo:
1011010110010101

Ciclo Evolutivo

1. Inicialização da população
2. Avaliação (fitness)
3. Seleção
4. Cruzamento
5. Mutação
6. Substituição
7. Critério de parada

Função de Fitness

Mede a qualidade de cada indivíduo.

Quanto maior o fitness, melhor a solução.

• Objetivo da otimização
• Base para seleção

Seleção

• Roleta (Roulette Wheel)
• Torneio
• Rank Selection

Indivíduos mais aptos possuem maior probabilidade de reprodução.

Cruzamento (Crossover)

Combina características de dois pais.

Pai 1: 110011|1010
Pai 2: 001101|0111

Filho: 1100110111

• Ponto único
• Dois pontos
• Uniforme

Mutação

Introduz diversidade genética.

Antes: 1100110111
Depois:1100100111

• Evita convergência prematura.
• Permite explorar novas regiões.

Algoritmo Genético Populacional

def genetic_algorithm():
    populacao = inicializar()

    while not criterio_parada():
        fitness = avaliar(populacao)

        pais = selecionar(populacao, fitness)

        filhos = crossover(pais)

        filhos = mutacao(filhos)

        populacao = substituir(populacao, filhos)

    return melhor_individuo(populacao)

Exemplo Prático

Maximizar:

f(x) = x²

com x ∈ [0, 31]

• Representação binária de 5 bits
• Fitness = x²

Evolução da População

Parâmetros Importantes

• Tamanho da população
• Taxa de crossover
• Taxa de mutação
• Número de gerações
• Elitismo