A Inteligência Artificial

...

de tempo e memória

Alto fator de ramificação O desempenho depende de outros fatores Funciona precariamente

O problema de caminhos infinitos pode ser evitado na busca em profundidade pela aplicação de um limiar de profundidade

Propriedades dos métodos de busca

● Complexidade:

● Ligado ao tempo e espaço utilizados na busca; ● Completude:

● Se é completo, ou seja, se sempre acha o objetivo;

● Obs.: se houver objetivo; ● Quanto a ser ótimo:

● Garantir achar a melhor solução que exista; ● Não garante que seja pelo menor caminho ou tempo. ● Admissibilidade:

● Garantir achar a melhor solução pelo melhor caminho. ● Irrevogabilidade:

● Não retrocedem, examinando assim somente um caminho.

Humanos utilizam busca em profundidade

● É o modo mais fácil e natural;

● Exemplos:

● Percorrendo um labirinto;

● Comprando um presente em um shopping;

Implementando a busca...

Profundidade:

Lista = []

Estado = no_raiz; Repita:

Se eh_objetivo( estado ) Então retorne SUCESSO

Senão inserirNaFrenteDaLista(sucessores(estado))

Se Lista estiverVazia

Então retorne FALHA

Estado = Lista[0]

RemoverPrimeiroItemDaLista

_____________________________________________________

Largura:

substituir a função inserirNaFrenteDaLista

por inserirAtrásDaLista

Aprofundamento Iterativo (BPAI)

● Também chamado de:

● Busca com Aprofundamento Iterativo (BAI), ● Depth-First Iterative Deepening (DFID), ● Iterative Deepening Search (IDS).

● Técnica exaustiva;

● Combina buscas em profundidade e em largura; ● Conduz buscas com profundidade limitada:

com profundidade de um;

depois com profundidade de dois;

depois com profundidade de três; e

assim por diante, até encontrar um nó objetivo.

Aprofundamento Iterativo (BPAI)

Árvore com fator de ramificação b e profundidade d

Profundidade BPAI

● Total de nós: ● Como os nós devem

● 1 + b + b2 + … + bd ser examinados mais de uma vez, temos: Prog. Geom.:

( 1 – b d+1 ) / ( 1 – b ) (d+1)+b(d)+b2(d-1)+b3(d-2)+...+bd

● Complexidade de O(bd) ● Ex: com d = 2 e b = 2:

(1 – 8)/(1 – 2) = 7 nós

Aprofundamento Iterativo (BPAI)

● Ruim para árvores pequenas e com bons resultados em árvores grandes

Heurísticas de Busca

● Heurística pode ser definida como:

● A utilização de informações que indicam melhor qual caminho a seguir.

Ex: pesquisar em todas as lojas por calças, ou somente nas lojas que trabalham com tecidos?

● Possui uma função de avaliação heurística

● É aplicada a um nó e retorna um valor que representa:

– uma boa estimativa da distância entre o nó e o objetivo

● Ex: Se para dois nós m e n, a função retorna f(m) < f(n), então deve ser o caso que m é mais provável de estar em um caminho ótimo para o nó objetivo

Heurísticas de Busca

● Métodos Informados:

● Utilizam informação adicional sobre os nós não explorados para decidir qual escolher.

● Que utilizam Heurísticas.

● Métodos Não Informados ou Cegos:

● Não utilizam informação adicional sobre os nós não explorados.

● Que não utilizam Heurísticas.

● Quanto melhor a heurística for, menos nós ela precisará examinar na árvore.

Monotonicidade

● Método de busca é monótono

● se ele sempre chega a um dado nó pelo caminho mais curto possível

● Uma heurística monotônica é uma heurística com essa propriedade

● Heurística admissível

● Heurística que nunca superestime a distância verdadeira entre um nó e o objetivo

Métodos de busca informados 

Subida na colina

● Caso de estudo

● Se tentar escalar uma montanha em dia de neblina, com um altímetro, mas sem mapa, você utilizaria uma abordagem de subida na colina ● Abordagem Gerar e Testar; ● Como proceder:

– Verificar a altura a alguns centímetros de sua posição em cada direção: norte, sul, oeste e leste.

– Assim que encontrar uma posição que o leve para uma altura maior que a atual, vá para lá e repita esses passos.

– Se todas as posições o levam para mais baixo de onde está, assuma que chegou ao topo.

Você