Busca

Resolução de problemas por meio de busca Capítulo 3 – Russell & Norvig Seções 3.4 e 3.5

Formulação de problemas Um problema é definido por quatro itens:

1. Estado inicial ex., em Arad" 2. Ações ou função sucessor S(x) = conjunto de pares ação-­‐estado – ex., S(Arad) = {, … }

3. Teste de objeUvo, pode ser

– explícito, ex., x = em Bucareste" – implícito, ex., Cheque-­‐mate(x)

4. Custo de caminho (adiUvo)

– ex., soma das distâncias, número de ações executadas, etc. – c(x,a,y) é o custo do passo, que deve ser sempre ≥ 0

•
•

Uma solução é uma seqüência de ações que levam do estado inicial para o estado objeUvo. Uma solução óUma é uma solução com o menor custo de caminho. Aula 4 -­‐ 20/08/2010

2

Algoritmo geral de busca em árvore

Aula 4 -­‐ 20/08/2010

3

Estratégias de Busca

Sem Informação (ou Busca Cega) • Estratégias de busca sem informação usam apenas a informação disponível na definição do problema. – Apenas geram sucessores e verificam se o estado objeUvo foi aUngido.

• As estratégias de busca sem informação se disUnguem pela ordem em que os nós são expandidos. –
–
–
–
–

Busca em extensão (Breadth-­‐first)