Cincia da computação

Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1

Aula 3 -­‐ 31/08/2010

1

Busca com informação (ou heurísIca) • UIliza conhecimento específico sobre o problema para encontrar soluções de forma mais eficiente do que a busca cega. – Conhecimento específico além da definição do problema.

• Abordagem geral: busca pela melhor escolha. – UIliza uma função de avaliação para cada nó. – Expande o nó que tem a função de avaliação mais baixa. – Dependendo da função de avaliação, a estratégia de busca muda.

Aula 3 -­‐ 31/08/2010

2

Busca pela melhor escolha • Idéia: usar uma função de avaliação f(n) para cada nó. – esImaIva do quanto aquele nó é desejável  Expandir nó mais desejável que ainda não foi expandido

• Implementação: Ordenar nós na borda em ordem decrescente de acordo com a função de avaliação • Casos especiais: – Busca gulosa pela melhor escolha – Busca A*

Aula 3 -­‐ 31/08/2010

3

Busca gulosa pela melhor escolha • Função de avaliação f(n) = h(n) (heurísIca) = esImaIva do custo de n até o objeIvo ex., hDLR(n) = distância em linha reta de n até Bucareste. • Busca gulosa pela melhor escolha expande o nó