Busca Local

BUSCA LOCAL
(PARTE 4 – Resolução de problemas por meio de busca)

(C)Russell & Norvig, capítulo 4
1

Roteiro
• Algoritmos de Busca Local
– Subida de encosta (Hill-climbing)
– Têmpera Simulada (Simulated Anealing)
– Feixe Local (Local beam)
– Algoritmos Genéticos

2

Resolução de problemas por meio de busca local

INTRODUÇÃO

3

Algoritmos de Busca Local
• Em muitos problemas de otimização o caminho ao objetivo é irrelevante (a sequência de ações), interessa-nos o estado objetivo = solução
– problemas de otimização
– satisfação de restrições (ex. N-Rainhas – configuração final)

• Espaço de estados = conjunto de configurações “completas” do mundo
– Ex. um arranjo das n-rainhas no tabuleiro

• Nestes casos, podem ser usados algoritmos de busca local

4

Vantagens da Busca Local
Vantagens em relação às buscas cega e informada:
1. usam pouca memória (normalmente, uma quantidade constante de memória) 2. podem encontrar soluções razoáveis/factíveis em espaços de estados grandes ou infinitos (e também contínuos) para os quais algoritmos sistemáticos como os de busca cega e informada não são adequados. 5

Algoritmos de Busca Local
Estratégia:

Manter um só estado (ou poucos) como o “atual" e tentar melhorar o mesmo movimentando-se para estados vizinhos imediatos

Estado corrente
Vizinho escolhido

6

Algoritmos de Busca Local
Função objetivo

elevação

Máximo global

objetivo

planície
Máximo local máx. local em platô

Estado corrente

Espaço de estados localização
7

Algoritmos de Busca Local
Se o objetivo é maximizar temos que encontrar o maior pico, se for minimizar, o vale mais profundo. Completo: se o algoritmo consegue atingir um estado objetivo desde que ele exista.
Ótimo: se consegue encontrar o mínimo/máximo para a função de custo.

8

Solução de problemas por busca

SUBIDA DE ENCOSTA
(HILL CLIMBING)
9

Subida de Encosta (Hill-climbing)
Metáfora: