Módulo IV - Buscas (não informadas) no Espaço de Estados

Prévia do material em texto

29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 1/6
Breadth­First Search (Busca em Largura ou Busca em Amplitude)
O processo de busca em Largura inicia­se com a expansão do nó que representa o estado inicial escolhido para o problema. A partir deste
momento, todos os nós gerados pelo nó inicial são expandidos. Este processo continuar até o fim da árvore.
 
Exemplo da expansão de nós para a busca em Largura
 
Figura 1: Nó inicial "Arad"criado.
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern   Approach. 2.Edition. New Jersey: Prentice Hall, 2003
 
Figura 2: Nós: [Sibiu, Timisoara, Zerind] expandidos.
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern   Approach. 2.Edition. New Jersey: Prentice Hall, 2003
 
 
 
Figura 3: Nós: [Arad, Fagaras, Oradea, Rummicu Vilcea] expandidos
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern   Approach. 2.Edition. New Jersey: Prentice Hall, 2003
 
 
 
 Algoritmo de Busca em Largura
 
 (1) Escolher o problema e estratégia
(2) Se não há mais candidatos (Fila Vazia) retorna Falso
      Senão: Escolha o nó para a expansão, de acordo com a estratégia
(3) Se o nó é o nó objetivo (goal) retorna a solução
      Senão: Expandir o nó e adicionar os nós resultados na árvore de pesquisa.
(4) Continua o processo até encontrar o estado objetivo ou termino sem solução.
 
 
 Análise da Complexidade do Algoritmo
Completo: Caso a solução existir, o algoritmo encontra a solução;
Ótimo: A solução de menor custo é encontrada pelo algoritmo;
Tempo: É a medida de tempo em que o algoritmo leva para encontrar a solução no pior caso;
Espaço: quanto o algoritmo ocupa de memória.
      Cada um dos itens acima podem ser referenciado para comparar os diversos algoritmos quanto a sua complexidade com o intuito de
estabelecer uma tabela comparativa para cada problema.
Análise da Complexidade do Algoritmo Busca em Largura
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 2/6
Completo: OK;
Ótimo: OK;
Tempo: explorar O(bd+1) nós (=estados)
b = fator de ramos (ramificação)
d = profundidade do estado meta
O(bd+1) = b + b2 + b3 + ... + bd + (bb+1 ­ b)
Espaço: salvar O(bd+1) nós (=estados)
A figura abaixo expressa de forma significativa a explicação das informações acima.
Depth­First Search (Busca em Profundidade)
Na busca em profundidade o nó que foi expandido primeiro será explorado, assim como todos os seus predecessores;
Nó expandidos são colocados em uma Pilha (LILO ­ Last in Last out)
Exemplo:
 
                                  
                          (a)                                                                    (b)                                                                (c)                                                                     (d)
                                   
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 3/6
                           (e)                                                                 (f)                                                                     (g)                                                                (h)
                                       
                         (i)                                                                     (j)                                                                      (k)                                                                    (l)
 Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern Approach. 2.Edition. New Jersey: Prentice Hall, 2003.
 
 
 
 
 
 A figura demonstra uma busca em profundidade máxima de cada ramo da árvore. Após terminar o ramo mais a esquerda, a busca segue o caminho do próximo
item da Pilha, localizado a direita de acordo com a figura acima item (f), por exemplo.
 
Análise da Complexidade do algoritmo
Completo: não. Caso o espaço de estados possuir uma profundidade infinita.
Ótimo: não.
Tempo: explorar O(bd+1) nós
b = fator de ramos (ramificação)
d = profundidade do estado meta
O(bd) = b + b2 + b3 + .... + bd + (bd – b)
Pode ser melhor do que Breadth­First Search (Busca em largura)
Espaço: guardar O(bm) nós.
Busca em profundidade requer menos espaço em memória do que a busca em largura
 
 
 Depth­Limited Search (Busca em profundidade limitada)
Representa uma Pesquisa com profundidade limitada, pré­estabelecida e fixa.
Iterative Deepening Search (Busca em profundidade iterativa)
Representa uma busca em profundidade com profundidade que se altera ao longo de cada intereção (Soma + 1).
Combina os beneficios de Depth­First e Breadth­First Search.
Em geral, a busca em profundidade interativa é a pesquisa não informada preferida quando existe um largo espaço de pesquisa e a profundidade não é
conhecida.
Exemplo de utilização: 
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 4/6
 
 
 Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern Approach. 2.Edition. New Jersey: Prentice Hall, 2003.
A medida que o algoritmo realiza a iteração, os nós são expandidos no limite de profundidade estipulado pela iteração. A partir deste momento em que o limite
de profundidade foi alcançado, a escolha do proximo nó é constituida de forma semelhante à busca em largura. Este processo continua até não haver mais nós a
serem expandidos, ou o nó objetivo ser encontrado.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 5/6
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercício 1:
Tendo com base o gráfo abaixo. Qual é o caminho que leva do estado inicial "A" p[ara o "B" com o uso de uma política de busca em
largura?
 
 
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 6/6
A ­ Caminho = {A,B,C,G} 
B ­ Caminho = {A,B,E, F,C,G} 
C ­ Caminho = {A,C,G} 
D ­ Caminho = {A,B,E,F,J,L,C,G} 
E ­ Caminho = {A,B,C,D,E,F,G} 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 2:
A busca em largura é classificada como uma "busca cega", onde o conhecimento sobre o problema não é considerado. Entretanto este
tipo de busca pode ser util em problemas com algumas caracteristicas. Quais caracteristicas podemos enunciar?
A ­ Espaço de estados infinito e as ações tem o mesmo custo 
B ­ Espaço de estados finito e as ações tem custo diferente para cada transição de estados 
C ­ Espaço de estados infinito e as ações possuem custo diferenciado 
D ­ Espaço de estados finito e as ações tem o mesmo custo 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 3:
Para resolver um problema cujo espaço de estados tende ao infinito, qual das estratégias de buscas cegas seriam mais apropriadas, caso o nó
objetivo encontra­se em profunidade próxima à superfície do espaço de estados? 
A ­ Busca em Profundidade 
B ­ Busca em profundidade iterativa 
C ­ busca em largura 
D ­ busca em em profundidade iterativa acrescentando apenas uma iteração. 
Comentários:
Essa disciplina não é ED ou você não fez comentários