Busca Cega

Prévia do material em texto

Inteligência Artificial:
Busca
Profa. Andréia Gentil Bonfante
07/10/14 2
Espaços de Problemas e Busca
 Para ter um sistema que solucione um 
problema é necessário:
1. Definir o problema precisamente
 especificar precisamente qual será a situação inicial e 
qual situação final será considerada a solução do 
problema.
07/10/14 3
Espaços de Problemas e Busca
2. Analisar o problema
3. Isolar e representar o conhecimento de tarefa 
necessário para solucionar o problema
4. Escolher a melhor ou as melhores técnicas de 
solução de problemas e aplicá-las ao problema.
07/10/14 4
O problema como uma busca em um 
espaço de estados
 jogar xadrez = problema de movimentação 
num espaço de estados
 cada espaço corresponde a uma posição 
legal do tabuleiro.
 podemos então, jogar xadrez começando de 
um estado inicial, usando um conjunto de 
regras para ir de um estado para outro e tentar 
terminar num estado final.
07/10/14 5
O problema como uma busca em um 
espaço de estados
 A estrutura de solução de problemas tem dois 
aspectos importantes:
 permite a definição formal de um problema como 
sendo a necessidade de converter uma dada 
situação desejada num conjunto de operações 
permitidas
 permite a definição de um processo de solução de 
um determinado problema como uma combinação 
de técnicas conhecidas (regras) e a busca 
(exploração) dessas técnicas.
07/10/14 6
O problema como uma busca em um 
espaço de estados
 Outro exemplo de representação em espaço 
de estados:
 Problema das jarras de água: você tem duas 
jarras, uma de 4 litros e outra de 3 litros. 
Nenhuma delas tem qualquer marcação de 
medidas. Há uma bomba que pode ser usada 
para encher as jarras com água. Como é que 
você consegue colocar exatamente 2 litros de 
água na jarra de 4 litros?
07/10/14 7
O problema como uma busca em um 
espaço de estados
 Espaço de estados:
 Pares ordenados de inteiros (x,y)
 onde x = 0,1,2,3,4 e y = 0,1,2,3
 Estado inicial: (0,0)
 Estado-meta: (2,n), sendo que n pode assumir 
qualquer valor
07/10/14 8
O problema como uma busca em um 
espaço de estados
 Ações possíveis para resolver o problema
1. (x,y), se x < 4 → (4,y) encher a jarra de 4 
litros
2. (x,y), se y < 3 → (4,3) encher a jarra de 3 
litros
3. (x,y), se x > 0 → (x-d,y) despejar parte da 
água jarra de 4 litros
4. (x,y), se y > 0 → (x,y-d) despejar parte da 
água jarra de 3 litros
07/10/14 9
O problema como uma busca em um 
espaço de estados
5. (x,y), se x > 0 → (0,y) esvaziar a jarra 
de 4 litros no chão
6. (x,y), se y > 0 → (x,0) esvaziar a jarra 
de 3 litros no chão
7. (x,y), se (x+y) ≥ 4 e y > 0 
 → (4,y-(4-x)) despejar água da jarra de 3 
litros na jarra de 4 litros até a jarra de 4 
litros encher
07/10/14 10
O problema como uma busca em um 
espaço de estados
8. (x,y), se (x+y) ≥ 3 e y > 0 
 → (x-(3-y),3) despejar água da jarra de 4 litros na 
jarra de 3 litros até a jarra de 3 litros encher
9. (x,y), se x+y ≤ 4 e y > 0 → (x+y,0)
 despejar toda a água da jarra de 3 litros na jarra de 4 
litros.
10. (x,y), se x+y ≤ 3 e y > 0 → (x+y,0)
 despejar toda a água da jarra de 4 litros na jarra de 3 
litros.
07/10/14 11
O problema como uma busca em um 
espaço de estados
11. (0, 2) → (2,0)
 despejar 2 litros de água da jarra de 3 litros na 
jarra de 4 litros
12. (2, y) → (0,y)
 esvaziar no chão os 2 litros que estão na jarra 
de 4 litros
07/10/14 12
O problema como uma busca em um 
espaço de estados
Uma solução para o problema:
Jarra 4 litros Jarra 3 litros Regra
 0 0 2
0 3 9
3 0 2
3 3 7
4 2 5 ou 12
0 2 9 ou 11
2 0
07/10/14 13
 Para resolver o problema das jarras de água, tudo o 
que precisamos é de uma estrutura de controle que 
execute um loop em torno de um ciclo simples, no 
qual se escolhe uma regra cujo lado esquerdo 
combine com o estado corrente, faz-se a mudança 
apropriada para o estado, conforme descreve o lado 
direito correspondente, e verifica-se o estado 
corrente para ver se corresponde ao estado-meta.
 Se não há correspondência, o ciclo continua.
07/10/14 14
Outro exemplo: problema do 
fazendeiro
1) Representação para estados: lista de quatro 
elementos representando a posição (norte ou 
sul) em que estão o fazendeiro, o lobo, a 
cabra, e o repolho, respectivamente.
2) Estado inicial: [norte,norte,norte,norte]
3) Estado Final: [sul,sul,sul,sul]
07/10/14 15
Outro exemplo: problema do 
fazendeiro
% Representação Prolog
estado_inicial([norte,norte,norte,norte]).
[sul,sul,sul,sul] e_a_meta.
07/10/14 16
Outro exemplo: problema do 
fazendeiro
4) Operações: com quem o fazendeiro atravessa.
% Representação Prolog
operacao('fazendeiro atravessa sozinho')
transforma [Saida,L,C,R] em [Chegada,L,C,R] :- 
permitido_ir_de([Saida,L,C,R] a [Chegada,L,C,R]).
operacao('fazendeiro atravessa com lobo')
transforma [Saida,Saida,C,R] em [Chegada,Chegada,C,R] :- 
permitido_ir_de([Saida,Saida,C,R] a [Chegada,Chegada,C,R]).
07/10/14 17
Outro exemplo: problema do 
fazendeiro
operacao('fazendeiro atravessa com cabra')
transforma [Saida,L,Saida,R] em [Chegada,L,Chegada,R] 
:- 
permitido_ir_de([Saida,L,Saida,R] a 
[Chegada,L,Chegada,R]).
operacao('fazendeiro atravessa com repolho')
transforma [Saida,L,C,Saida] em [Chegada,L,C,Chegada] 
:- 
permitido_ir_de([Saida,L,C,Saida] a 
[Chegada,L,C,Chegada]).
07/10/14 18
Outro exemplo: problema do 
fazendeiro
permitido_ir_de([F,L,C,R] a [F1,L1,C1,R1]) :- 
opostas(F,F1),
 nao_oferece_perigo(F1,L1,C1,R1).
% Faz. com cabra e’ok pois faz. protege cabra do lobo e
% repolho da cabra
nao_oferece_perigo(FC,L,FC,R).
07/10/14 19
Outro exemplo: problema do 
fazendeiro
% Cabra sozinha e’ok pois ela nao pode comer rep.
% Nem ser comida pelo lobo 
nao_oferece_perigo(FLR,FLR,C,FLR) :- opostas(FLR,C).
opostas(sul,norte).
opostas(norte,sul).
07/10/14 20
Outro exemplo: problema do 
fazendeiro
OBS: Neste caso temos condições de aplicação 
associadas aos operadores.
5) Tipo da solução: caminho no grafo. Custo = nro 
de travessias = tamanho do caminho
07/10/14 21
Exercício: 8-puzzle
 1) Representação para estados: 
??
 2) Estado inicial: ??
 3) Estado Final: ??
 4) Operações: ??
 5) Tipo da solução:?? Custo??
8 1
4 3
56
2
7
2 3
4
56
8
7
1
07/10/14 22
1)Representação para estados: 
 Estados tem a forma A/B/C/D/E/F/G/H/I 
 onde {A .. I} = {0..8} com 0 representando a 
posição vazia
2) Estado inicial: 
 por exemplo: 0/8/1/2/4/3/7/6/5
3) Estado Final: 1/2/3/8/0/4/7/6/5
07/10/14 23
4) Operações: mover branco para cima, 
esquerda, direita, e baixo
5) Tipo da solução: caminho no grafo. Custo = 
tam. do caminho
07/10/14 24
Em prolog
% Representação Prolog
 esq(A/0/C/D/E/F/H/I/J , 0/A/C/D/E/F/H/I/J ).
 esq( A/B/0/D/E/F/H/I/J , A/0/B/D/E/F/H/I/J ).
 esq( A/B/C/D/00/F/H/I/J , A/B/C/0/D/F/H/I/J ).
 esq( A/B/C/D/E/0/H/I/J , A/B/C/D/0/E/H/I/J ).
 esq( A/B/C/D/E/F/H/0/J , A/B/C/D/E/F/0/H/J ).
 esq( A/B/C/D/E/F/H/I/0 , A/B/C/D/E/F/H/0/I ).
07/10/14 25
Em prolog
 cima( A/B/C/0/E/F/H/I/J , 0/B/C/A/E/F/H/I/J ).
 cima( A/B/C/D/0/F/H/I/J , A/0/C/D/B/F/H/I/J ).
 cima( A/B/C/D/E/0/H/I/J , A/B/0/D/E/C/H/I/J ).
 cima( A/B/C/D/E/F/0/I/J , A/B/C/0/E/F/D/I/J ).
 cima( A/B/C/D/E/F/H/0/J , A/B/C/D/0/F/H/E/J ).
 cima( A/B/C/D/E/F/H/I/0 , A/B/C/D/E/0/H/I/F ).
07/10/14 26
Em prolog
dir( A/0/C/D/E/F/H/I/J , A/C/0/D/E/F/H/I/J ).
dir( A/B/C/D/0/F/H/I/J , A/B/C/D/F/0/H/I/J ).
dir( A/B/C/D/E/F/H/0/J , A/B/C/D/E/F/H/J/0 ).
dir( 0/B/C/D/E/F/H/I/J, B/0/C/D/E/F/H/I/J ).
dir( A/B/C/0/E/F/H/I/J , A/B/C/E/0/F/H/I/J ).
dir( A/B/C/D/E/F/0/I/J , A/B/C/D/E/F/I/0/J ).
07/10/14 27
Em prolog
baixo( A/B/C/0/E/F/H/I/J , A/B/C/H/E/F/0/I/J ).
baixo( A/B/C/D/0/F/H/I/J , A/B/C/D/I/F/H/0/J ).
baixo( A/B/C/D/E/0/H/I/J , A/B/C/D/E/J/H/I/0 ).
baixo( 0/B/C/D/E/F/H/I/J , D/B/C/0/E/F/H/I/J ).
baixo( A/0/C/D/E/F/H/I/J , A/E/C/D/0/F/H/I/J ).
baixo( A/B/0/D/E/F/H/I/J , A/B/F/D/E/0/H/I/J ). 
move(P,C,esq) :- esq(P,C).
move(P,C,cima) :- cima(P,C).
 move(P,C,dir) :- dir(P,C).
 move(P,C,baixo) :- baixo(P,C).
?- resolve(0/8/1/2/4/3/7/6/5, S).
 
 S = [dir, dir, baixo, esq, esq, cima, dir, baixo] ;
07/10/14 28
8 1
2 4 3
7 6 5 
 8 1
2 4 3
7 6 5
1 2 3
8 4
7 6 5
DIR
...
BAIXO
07/10/14 29
Resumindo: para fazer uma 
descrição formal de um problema
1. Definir um espaço de estados que contenha 
todas as configurações possíveis dos 
objetos relevantes.
2. Especificar um ou mais estados dentro 
daquele espaço que descrevem possíveis 
situações a partir das quais o processo de 
solução possa começar. São os estados 
iniciais
07/10/14 30
Resumindo: para fazer uma 
descrição formal de um problema
3. Especificar um ou mais estados que seriam 
aceitáveis como soluções. São os estados-
meta.
4. Especificar um conjunto de regras que 
descrevem ações disponíveis.
07/10/14 31
E...
 A velocidade com que o problema é resolvido 
depende do mecanismo usado para selecionar 
a próxima operação a ser realizada (BUSCA).
07/10/14 32
 Requisitos: Definir o problema de forma precisa: 
1) o que constitui um estado, 
2) o estado inicial,
3) o final, 
4) o conjunto de operadores; as condições para se aplicar 
operadores (regras) se necessário, 
5) o custo do caminho (é zero quando a solução é apenas o 
estado meta).
 OBS: No processo de resolução, primeiro formula-se a meta 
depois o problema como um todo.
caminho no grafo (seqüência de 
operadores aplicados )
Problemas: missionários & canibais, 
fazendeiro, 8-puzzle, tabuleiro com
cinco fichas, etc.
somente o estado objetivo/meta 
Problemas:8-rainhas,etc. 
Solução do
 problema
07/10/14 33
Busca
 Dada a formulação do problema como um 
espaço de estados, existem várias estratégias 
--- chamadas busca --- para encontrar o 
caminho solução. As duas estratégias básicas 
são: busca em profundidade primeiro e busca 
em largura primeiro.
07/10/14 34
Busca
 OBS: 
 um mesmo problema pode ser resolvido 
utilizando-se diferentes estratégias. Cabe a 
nós saber escolher qual a mais apropriada.
07/10/14 35
Algoritmos de Busca 
 Problemas de busca são 
freqüentemente descritos 
utilizando diagramas de 
árvores
Nó inicial = 
 onde a busca começa
Nó objetivo = 
 onde ela termina
Ni
No
07/10/14 36
Algoritmos de Busca 
 Exploração simulada do 
espaço de busca através da 
geração de sucessores dos 
estados já explorados --- 
expansão de estados.
Ni
No
07/10/14 37
Estados X Nós
 Um estado é uma representação de 
uma configuração física
 Um nó é uma estrutura de dados 
consistindo de parte da árvore de 
busca e inclui nó pai, filhos, 
profundidade, custo do caminho.
07/10/14 38
Nó
Pai
Filhos
Prof. = 6
custo = 6
Estado
8 
1
2 4 
3
7 6 
5
Estado
07/10/14 39
Tipos de Problemas
 Único estado inicial
 Múltiplos estados iniciais: escolhe um deles.
 Único estado final
 Múltiplos estados finais: encontrar qualquer 
caminho OU encontrar melhor caminho.
07/10/14 40
Algoritmo básico de busca
1 Definir um conjunto L de nós iniciais;
2 Se L é vazio
 Então Busca não foi bem sucedida
 Senão Escolher um nó n de L;
3 Se n é um nó objetivo
Então Retornar caminho do nó inicial até n;
 Parar 
 Senão Remover n de L;
 Adicionar a L todos os filhos de n, rotulando cada 
 um com o seu caminho até o nó inicial;
 Voltar ao passo 2
07/10/14 41
Algoritmos de Busca
 São distinguidos pela maneira como o nó n é 
escolhido no passo 2/como são expandidos 
no passo 3.
 São avaliados através das seguintes 
dimensões:
 Completeza - o algoritmo sempre encontra uma 
solução se ela existe?
07/10/14 42
Algoritmos de Busca
 Complexidade de tempo - nro de nós 
gerados/expandidos
 Complexidade de espaço - número máximo de 
nós na memória
 Admissibilidade - um algoritmo é admissível se 
ele garante encontrar uma solução ótima, 
quando ela existe.
07/10/14 43
Complexidade de Tempo & Espaço
 b - largura máxima da árvore de busca (filhos de 
um nó)
 d - profundidade da solução de custo mínimo
 m - profundidade máxima do espaço de 
estados
07/10/14 44
Métodos de Busca
 Busca cega/não informada: baseada somente 
na posição do nó na árvore de busca. Não há 
nenhuma informação sobre o nro de 
passos/custo do caminho do estado atual até a 
meta. A única coisa que sabe é distinguir um 
estado que é meta de outro qualquer. 
Importante, pois existem problemas para os 
quais não existe informação adicional a se 
considerar. 
07/10/14 45
Métodos de Busca
 Busca heurística/informada: A escolha 
utiliza informações específicas do domínio 
para ajudar na decisão. Mais eficiente.
07/10/14 46
Busca cega
 Busca em Profundidade Primeiro
 Busca em Largura Primeiro
 Busca em Prof. Limitada
 Busca de Custo Uniforme
 “Iterative Deepening”
 Busca Bidirecional
 
07/10/14 47
Algoritmos básicos de busca cega
 Busca em Profundidade (BP)
 A árvore é examinada de cima para baixo
 Aconselhável nos casos onde os caminhos 
improdutivos não são muito longos
07/10/14 48
Algoritmos básicos de busca cega
 Busca em Largura (BL)
 A árvore é examinada da esquerda para a direita 
 Aconselhável quando o número de ramos não é muito 
grande
07/10/14 49
Algoritmo BP
1 Definir um conjunto L de nós iniciais
2 Se L é vazio
 Então Busca não foi bem sucedida
 Senão seja n o primeiro nó de L;
3 Se n é um nó objetivo
 Então Retornar caminho do nó inicial até n;
 Senão Remover n de L;
 Adicionar ao início de L todos os filhos de n,
 rotulando cada um com o seu caminho até o nó inicial;
 Voltar ao passo 2;
07/10/14 50
 Busca em profundidade
d = 1
d = 2
d = 3
d = 4
d = 0 1
2 15
3
4
5 6 7
8
9
10 13 16 17
11 12 14 18
07/10/14 51
Propriedades do BP
 Completo?? Não. Falha em espaços de 
profundidade infinita. Completo se o espaço de 
estados é finito.
 Tempo?? O(bm). Ruim se m é muito maior que d.
 Espaço?? O(bm). Linear.
 Admissível?? Não.
07/10/14 52
Algoritmo BL
1 Definir um conjunto L de nós iniciais
2 Se L é vazio
 Então Busca não foi bem sucedida
 Senão seja n o primeiro nó de L;
3 Se n é um nó objetivo
 Então Retornar caminho do nó inicial até n;
 Parar 
 Senão Remover n de L;
 Adicionar ao final de L todos os filhos de n, rotulando 
 cada um com o seu caminho até o nó inicial;
 Voltar ao passo 2;
07/10/14 53
 Busca em largura
d = 1
d = 2
d = 3
d = 4
d = 0 1
2 3 4
5 6 7 8 9 10
11 12 13 14 15
07/10/14 54
Propriedades do BL
 Completo?? Sim (se b é finito)
 Tempo?? 1 + b + b2 + b3 + ... + bd = O(bd) 
exponencial em d.
 Espaço?? O(bd) (mantém todos os nós na 
memória
 Admissível?? Sim. 
Espaço é um grande problema.
07/10/14 55
Exemplo 1: Dada a árvore abaixo, utilizando 
BP, indique: a) Memória máxima e b) 
Número mínimo de passos necessáriospara 
atingir um dos nós objetivo
432
7 8 10965
1511 16
d = 1
d = 2
d = 3
d = 4
d = 0
17
2120
13 14
 1
201918
12
07/10/14 56
Resposta ao exemplo 1
a) 1 L = {1}
 2 L = {21, 31,41}
 3 L = {52 1,62 1,31,41}
 4 L = {115 2 1, 62 1,31,41}
 5 L = {1811 5 2 1, 1911 5 2 1, 2011 5 2 1 62 1,31,41}
 6 L = {1911 5 2 1, 2011 5 2 1 62 1,31,41}
 7 L = {2011 5 2 1, 62 1,31,41}
 8 L = {62 1,31,41}
 9 L = {31,41}
 ... 18 L = {1510 4 1,1610 4 1,1710 4 1}
07/10/14 57
 Exemplo 2: Dada a árvore abaixo, utilizando 
BL, indique: a) Memória máxima e b) 
Número mínimo de passos necessários 
para atingir um dos nós objetivo
432
7 8 10965
1511 16
d = 1
d = 2
d = 3
d = 4
d = 0
17
2120
13 14
 1
201918
12
07/10/14 58
Busca de custo uniforme
 BL modificado
 Expande o nó de menor custo
 Insere nós em L em ordem ascendente do custo 
do caminho
 Exemplo: Cálculo da melhor rota
07/10/14 59
Busca de custo uniforme
1 10
5 5
15 5
s
a
g
b
c
[a(1),b(5),c(15)]
[b(5),g(11),c(15)]
[g(10),g(11),c(15)]
Pára, pois g é meta e mais barata que as 3
07/10/14 60
Algoritmo Busca Custo-Uniforme1. Definir um conjunto L de nós iniciais
2. Ordene L em ordem crescente de custo
3. Se L é vazio
Então Busca não foi bem sucedida
Senão seja n o primeiro nó de L;
4. Se n é um nó objetivo
Então Retornar caminho do nó inicial até N;
Senão Remover n de L;
Adicionar em L todos os nós filhos de n, rotulando 
cada nó com o seu caminho até o nó inicial; Ordene 
L em ordem crescente de custo; Volte ao passo 3.
07/10/14 61
Propriedades do custo uniforme
 Completo?? Sim.
 Tempo?? O(bd)
 Espaço?? O(bd)
 Admissível?? Sim.
07/10/14 62
Busca em Profundidade Limitada
 BP com limite l
 Nós à profundidade l não tem sucessores.
 Completo?? Sim se l >= d
 Tempo?? O(bl)
 Espaço?? O(bl)
 Admissível?? Não.
07/10/14 63
Iterative Deepening
 Escapa da necessidade de escolher o 
melhor limite de profundidade, tentando 
todos os limites possíveis: primeiro 0, depois 
1, então 2,...
 Chama BP limitada várias vezes.
 Combina as vantagens do BL e BP
 Tempo?? O(bd) Espaço?? O(bd)
 Completo?? Sim. Admissível?? Sim.
07/10/14 64
Códigos Prolog para BL e BP
:- op(35,xf,e_a_meta).
:- op(35,xf,atinge_a_meta).
:- op(35,xfx,transforma).
:- op(30,xfx,a).
:- op(30,xfx,em).
:- op(35,xfx,nao_produz_circulos_em).
% programas auxiliares
ap([],X,X).
ap([X|Y],Z,[X|W]) :- ap(Y,Z,W).
membro(X,[X|_]):-!.
membro(X,[_|Y]) :- membro(X,Y).
ache_todos(X,Y,Z) :- findall(X,Y,Z), !.
ache_todos(_,_,[]).
imprima([r(raiz,Raiz)]) :- !,
 write('Estado Inicial: '),
 write(Raiz), write('.').
imprima([r(Ramo,Nodo)|R]) :-
 imprima(R), nl,
 write(Ramo), write(' e, portanto, temos: '), nl,
 write(Nodo), write('.').
Auxiliar.pl
07/10/14 65
% busca em largura primeiro
resolva :- estado_inicial(E),
 busca([[r(raiz,E)]],Solucao),
 imprima(Solucao), nl.
busca([T|_],Solucao) :- T atinge_a_meta, !, Solucao = T.
busca([T|Fila], Solucao) :-
 
ache_todos(ExtensaoAteUmFilho,estende_ate_filho(T,ExtensaoAteUmFil
ho), Extensoes),
 ap(Fila,Extensoes,FilaEstendida),
 busca(FilaEstendida,Solucao).
estende_ate_filho([r(Ramo,N)|Trajetoria], 
 [r(Op,Filho),r(Ramo,N)|Trajetoria]) :-
 operacao(Op) transforma N em Filho,
 Filho nao_produz_circulos_em Trajetoria.
Estado nao_produz_circulos_em Trajetoria :- 
 not membro(r(Operacao,Estado),Trajetoria).
[r(Ramo,M)|_] atinge_a_meta :- M e_a_meta.
Busca_l.pl
07/10/14 66
% busca em profundidade primeiro
resolva :- estado_inicial(E),
 busca([r(raiz,E)],Solucao),
 imprima(Solucao), nl.
busca([T|_],Solucao) :- T atinge_a_meta, !, Solucao = T.
busca([T|Pilha], Solucao) :-
 ache_todos(ExtensaoAteUmFilho,
 estende_ate_filho(T,ExtensaoAteUmFilho),Extensoes),
 ap(Extensoes,Pilha,PilhaEstendida),
 busca(PilhaEstendida,Solucao).
estende_ate_filho([r(Ramo,N)|Trajetoria], 
 [r(Op,Filho),r(Ramo,N)|Trajetoria]) :-
 operacao(Op) transforma N em Filho,
 Filho nao_produz_circulos_em Trajetoria.
Estado nao_produz_circulos_em Trajetoria :- 
 not membro(r(Operacao,Estado),Trajetoria).
[r(Ramo,M)|_] atinge_a_meta :- M e_a_meta.
Busca_p.pl
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66