Estratégias de Busca Cega - .Os primeiros três níveis do espaço de estados do jogo-da-velha reduzidos

  • View
    212

  • Download
    0

Embed Size (px)

Text of Estratégias de Busca Cega - .Os primeiros três níveis do espaço de estados do jogo-da-velha...

Estratgias de Busca Cega

Encontram solues para problemas pela gerao sistemtica de novos estados, que so comparados ao objetivo.

So ineficientes na maioria dos casos:

utilizam apenas o custo de caminho do n atual ao n inicial

(funo g(n)) para decidir qual o prximo n da fronteira a ser

expandido.

Essa medida nem sempre conduz a busca na direo do

objetivo.

Estratgias de Busca Heurstica

Utilizam conhecimento especfico do problema que

pode ser usada para guiar o processo de busca.

Aplicam uma funo que avalia a um n particular e prediz a qualidade dos seus ns sucessores: A funo avaliao f(n) estima o custo de caminho do n

atual at o objetivo mais prximo utilizando uma funo heurstica.

A funo heurstica h(n) estima o custo do caminho mais barato do estado atual at o estado final mais prximo.

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

Busca Heurstica

Os problemas de IA empregam heursticas, basicamente, em duas

situaes:

1. Um problema pode no ter uma soluo exata por causa das ambiguidades inerentes na sua formulao ou pela disponibilidade dos dados. Exemplos: Diagnstico mdico, Sistemas de viso.

2. Um problema pode ter uma soluo exata, mas o custo computacional para encontr-la pode ser proibitivo. Exemplo: Jogo de xadrez.

Busca Heurstica Uma heurstica apenas uma conjectura informada

sobre o prximo passo a ser tomado na soluo de um problema.

A heurstica baseada na experincia e na intuio.

Uma heurstica pode levar um algoritmo de busca a uma soluo sub-tima ou, inclusive, lev-lo a no conseguir encontrar uma soluo.

As heursticas podem falhar.

George Polya define heurstica como o estudo dos mtodos e das regras de

descoberta e inveno (Polya, 1945) relacionada com o termo grego original, o

verbo eurisco (Eu descubro). Quando Arquimedes emergiu de seu famoso banho

segurando a coroa de ouro, ele gritou Eureka! (Eu descobri!).

5

Busca Heurstica Exemplo ... Poro do espao de estados para o jogo-da-velha

9

8

7

.

.

.

N0 de

caminhos

= 9!

6

Busca Heurstica Exemplo ...

Os primeiros trs nveis do espao de estados do jogo-da-velha reduzidos por simetria.

3 movimentos iniciais:

Para o canto

Para o centro de um lado

Para o centro da grade

A heurstica do maior nmero de vitrias aplicada aos primeiros filhos do jogo-da-velha.

Maior nmero de vitrias: maior nmero de linhas, colunas e diagonais ainda disponveis.

Busca Heurstica Exemplo ...

8

Espao de estados reduzido heuristicamente para o jogo-da-velha.

Busca Heurstica Exemplo

Busca Heurstica

Classes de algoritmos para Busca Heurstica:

1. Busca pela melhor escolha (Best-First search):

Greedy best-first search (Busca gulosa pela melhor escolha)

A*

2. Busca com limite de memria (Memory Bounded Search):

IDA* (Iterative Deepening A*)

RBFS (Busca recursiva de melhor escolha)

SMA* (Simplified Memory-Bounded A*)

Busca Heurstica

Algoritmo geral: Busca pela Melhor Escolha - BME (Best-first search)

Seleciona para expanso o n que tiver o menor custo estimado at a meta (objetivo), segundo uma funo de avaliao f(n).

Tipicamente f(n) usa uma funo heurstica h(n) = custo estimado do caminho mais econmico do n n at um n objetivo (Restrio inicial: se n um n objetivo, h(n) = 0).

Busca Heurstica

Uma forma de uso da informao heurstica sobre um problema consiste em computar estimativas numricas para os ns no espao de estados;

Uma estimativa indica o quanto um n promissor com relao ao alcance de um n-objetivo;

A ideia continuar a busca sempre a partir do n mais promissor no conjunto de candidatos;

O programa de busca do melhor caminho (escolha) baseado neste princpio.

Busca Heurstica

A Busca do melhor caminho pode ser derivada de um refinamento da busca em largura.

A Busca em largura sempre escolhe para expanso os menores caminhos-candidatos (isto , os ns extremos menos profundos da busca).

A Busca do melhor caminho refina este princpio calculando uma estimativa heurstica para cada candidato e escolhe para expanso o melhor candidato de acordo com esta estimativa.

Busca Heurstica

Greedy best-first search (Busca gulosa pela melhor escolha)

Tenta expandir o n mais prximo meta, na suposio de que isso provavelmente levar a uma soluo rpida.

Avalia ns para expandir com base unicamente na funo heurstica: f(n) = h(n)

Exemplo: encontrar a melhor rota (rota mais curta) de uma cidade a outra, num mapa usando a Funo heurstica hDLR(n) (DLR: distncia em linha reta entre as cidades e a cidade-meta).

14

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Um mapa rodovirio simplificado de parte da Romnia.

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando hDLR(n)

f(n) = hDLR(n)

Objetivo: Bucareste

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurstica de

distncia em linha reta hDLR. Os ns so identificados por seus valores de h.

Exemplo Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurstica de

distncia em linha reta hDLR. Os ns so identificados por seus valores de h.

Exemplo Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurstica de

distncia em linha reta hDLR. Os ns so identificados por seus valores de h.

Exemplo Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurstica de

distncia em linha reta hDLR. Os ns so identificados por seus valores de h.

Exemplo Passo a Passo ...

Fases de uma busca gulosa pela melhor escolha para Bucareste, usando-se a heurstica de

distncia em linha reta hDLR. Os ns so identificados por seus valores de h.

Busca Heurstica

Busca pela melhor escolha - Busca Gulosa No completa

Pode entrar em ciclos e no encontrar a soluo se no detectar estados repetidos;

Pode se perder em um caminho infinito e nunca retroceder para tentar outras opes.

No tima

No exemplo encontrou caminho (Arad, Sibiu, Fagaras, Bucareste) que 32km maior que (Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucareste)

Dependendo do problema e da qualidade da heurstica a complexidade pode ter uma reduo substancial.

Busca Heurstica

BME mais famoso: Busca A*

Objetivo: Minimizar o custo total estimado da soluo.

Funo de avaliao: f(n) = g(n) + h(n) g(n) = custo do caminho (distncia) do n inicial ao n n h(n) = custo estimado do caminho (distncia ) de menor custo de n

ao n final f(n) = custo estimado da soluo de menor custo que passa por n.

A* expande o n de menor valor de f na fronteira do espao de

estados.

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Um mapa rodovirio simplificado de parte da Romnia.

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Busca Heurstica Exemplo: Localizao de rotas na Romnia, usando a Busca A*

f(n) = g(n) + hDLR(n) Objetivo: Bucareste

Exemplo Passo a Passo ...

Exemplo Passo a Passo ...

Exemplo Passo a Passo ...

Exemplo Passo a Passo ...

Exemplo Passo a Passo ...

Exemplo Passo a Passo

38

Estgios em uma busca

A* por Bucareste. Os

ns esto rotulados

f = g + h. Os valores de

h so distncias em

linha reta para

Bucareste.

Busca Heurstica

A funo heurstica h(n) deve satisfazer as seguintes condies, para que a busca A* seja tima:

Admissibilidade.

Consistncia

Busca Heurstica Admissibilidade

Uma heurstica admissvel se nunca superestima o custo de atingir o objetivo.

Como g(n) o custo real para atingir n ao longo do caminho atual e

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

ento f(n) nunca ir a superestimar o verdadeiro custo de uma soluo ao longo do caminho atual atravs de n

A distncia em linha reta uma heurstica admissvel, pois, o caminho mais curto entre dois pontos quaisquer uma linha reta

Um algoritmo de busca que garantidamente encontre um percurso ideal para um objetivo, se este existir, chamado de admissvel (Nilsson, N. K. Pri