Busca em Grafos

Grafos

• Um grafo consiste em um conjunto de nós conectados por arestas.
• Busca é usada em diversos domínios do mundo real:
• Navegação: encontrar o caminho mais curto ou rápido entre dois pontos.
• Robótica: planejar trajetórias de movimento.
• Resolução de puzzles: encontrar sequências de movimentos para atingir uma configuração.

Nós de um grafos - pt. 1

• Grau:
• n.º de arestas conectadas

Nós de um grafos - pt. 2

• Grau:
• De entrada (direcionado, n.º de arestas de entrada)

Nós de um grafos - pt. 3

• Grau:
• De saída (direcionado, número de arestas de saída)

Caminhos em grafos - pt. 1

• Caminho:
• Sequência de nós/arestas de um nó a outro

Caminhos em grafos - pt. 2

• Caminho:
• Nó x é acessível a partir do nó y se existir um caminho de y a x

Caminhos em grafos - pt. 3

• Caminho:
• Um ciclo é um caminho que começa etermina no mesmo nó

Caminhos em grafos - pt. 4

• Caminho:
• Um laço é uma aresta que conecta um nó a si mesmo

Buscando caminhos entre dois vértices

• Qualquer caminho (ou queremos saber se existe um caminho).
• Minimizar o comprimento do caminho (número de arestas).
• Minimizar o custo do caminho (soma dos pesos das arestas)

Força bruta e Backtracking

• Força bruta: tentar todas as possibilidades, retornar a solução
• Backtracking é uma técnica algorítmica que constrói uma solução passo a passo.
• A cada etapa, o algoritmo escolhe entre várias alternativas possíveis
• Solução
• Se uma escolha não levar a uma solução válida, ele retorna à decisão anterior e tenta outro caminho.

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.

Busca em Profundidade (DFS)

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.

Buscar caminho de a\(\to\) h, prioridade alfabética

• a \(\to\) b \(\to\)e \(\to\)f \(\to\)c \(\to\)i
• a \(\to\) d \(\to\)h

Características do DFS

O DFS garante encontrar um caminho, caso exista. É fácil recuperar exatamente qual é o caminho (a sequência de arestas percorridas) quando o encontramos
• escolher - explorar - desmarcar
• Não é ótimo. O DFS garante encontrar um caminho, mas não necessariamente o melhor/mais curto
• dfs(a, i) retorna {a, b, e, f, c, i} em vez de {a, d, h, i}.

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.
• É completo 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.

Funcionamento do BFS

• Começo: {a}
• Alvo: {f}

• Começo: {a}
• Alvo: {f}

1. Empilha: {b, d}

• Começo: {a}
• Pilha: {b, d}
• Alvo: {f}

1. Desempilha {b}
2. Empilha {e}

• Começo: {a}
• Pilha: {d, e}
• {Alvo: f}

1. Desempilha {d}
2. Empilha {g, h}

• Começo: {a}
• Pilha: {e, g, h}
• {f}

1. Desempilha {e}
2. Acha {f}

Características do BFS

Comparação BFS e DFS

Heurísticas

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

• Hill Climbing
• Busca A*
• Computação Evolutiva

Como elas funcionam?

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

Por que usar heurísticas?

• Problemas NP-difíceis são comuns.
• Soluções exatas podem ser lentas demais.
• Uma boa solução agora vale mais do que a ótima depois.
• Aplicações reais exigem velocidade.

Hill Climbing

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

Procedimento

• enquanto houver melhoria:
1. gerar vizinhos
2. escolher melhor vizinho
3. 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
• Computação evolutiva

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.

• Busca exata quando a heurística é admissível.
• Busca aproximada quando priorizamos velocidade.
• Excelente equilíbrio entre custo e desempenho.

A* como Heurística

g(n): g(n) é o custo do caminho do nó inicial até n

h(n): é uma função heurística que estima o custo do caminho mais barato de n até o destino.

Qualidade da Heurística

Algoritmo

• Inserir o estado inicial na fila de prioridade.

Repetir:

1. Selecionar o nó com menor f(n)=g(n)+h(n).
• Se for o objetivo, encerrar.
2. Adicionar sucessores na fila.
3. Atualizar custos e reinserir nós.

Exemplos - diferentes distâncias

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 1: 1100110111

Filho 2: 0011011010

• 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 = mutação(filhos)

        populacao = substituir(populacao, filhos)

    return melhor_individuo(populacao)

Exemplo Prático

Maximizar:

f(x) = \(\Sigma\)(x)

com x ∈ [-1, 1]

• Representação: array de 5 números reais
• Fitness = \(\Sigma\)(x)

1. [-0.28, -1.16,-1.94, 0.86, 0.15] \(\to\) f(x) = -2.37
2. [ 0.71, -0.24, -1.58, -1.40, -0.31] \(\to\) f(x) = -2.83
3. [1.03, 0.18, 1.15, 0.60, 1.63] \(\to\) f(x) = 4.60
4. [-0.54, -0.04, 1.85, 1.24, -0.06] \(\to\) f(x) = 2.44
5. [-0.10, 0.73, -0.71, -0.53, 1.18] \(\to\) f(x) = 0.57

Crossover e mutação

• Crossover:
• Pai 1: [1.03, 0.18, 1.15, 0.60, 1.63]\(\to\) f(x) = 4.60
• Pai 2: [-0.54, -0.04, 1.85, 1.24, -0.06] \(\to\) f(x) = 2.44

---

• Filho 1: [1.03, 0.18, 1.15, 1.24, -0.06] \(\to\) f(x) = 3.54
• Filho 2: [-0.54, -0.04, 1.85, 0.60, 1.63] \(\to\) f(x) = 3.50

• Mutação:
• Filho 2: [-0.54, -0.04, 1.85, 0.60, 1.63]\(\to\) f(x) = 3.50
• Novo: [-0.54, -0.04, 1.85, 0.60, 2.78]\(\to\) f(x) = 4.64