07 buscaeresolu odeproblemas

Busca e Resolução de Problemas
Prof. Rodolfo Chiaramonte [e-mail] 1

Etapas para a solução de problemas 

Formulação dos Objetivos:
 Organizar

o comportamento;
 Devem ser definidos de acordo com a medida de desempenho; 

Formulação de Problemas:
 Decidir

que ações e estados devem ser considerados; 

Busca da solução:
 Busca

por uma sequência de ações que levem ao objetivo; 

Execução:
 Sequência

de Ações encontradas é executada;
2

Definição de Problemas



Estado inicial: onde o agente começa.
Função Sucessor – SUCESSOR(x):
 Dado

um estado x, retorna um conjunto de pares ordenados <ação, sucessor> possíveis a partir do estado x;





Espaço de estados: Conjunto de todos os estados acessíveis a partir do estado inicial;
Caminho: sequência de estados conectados por uma sequência de ações;
Teste de Objetivo: Determina se um estado é o estado objetivo;
3

Definição de Problemas


Custo:
 De



 De






Caminho:
Custo numérico a atribuído cada caminho;
Reflete a medida de desempenho;

passo:
Custo resultante ao adotar uma ação a para ir do estado x ao estado y;
Denotado por: c(x,a,y);

Solução Ótima:
 Tem

o menor custo de caminho entre todas as soluções; 4

Exemplo:

5

Exemplo:



Um agente se encontra em férias na cidade de
Arad;
Sua medida de desempenho possui muitos fatores:  Melhorar

o bronzeado, melhorar o conhecimento do idioma, ver paisagens, ...



Mas ele possui uma passagem não reembolsável para partir de Bucarest na manhã seguinte;  Nesse

caso, faz sentido o agente adotar o objetivo de chegar a Bucarest;
6

Exemplo (Definição do Problema):


Estado inicial: Em(Arad);



SUCESSOR(Em(Arad));
 {<Ir(Sibiu),

Em(Sibiu)>, <Ir(Timisoara),
Em(Timisoara)>, <Ir(Zerind), Em(Zerind)>}



Espaço de estados: Figura no slide 5 pode ser interpretada com um grafo do espaço de estados se visualizarmos cada estrada como duas possíveis ações de dirigir;
7

Em busca de soluções


Árvore de Busca:




Gerada