Busca de Soluções
• Uma solução é uma sequencia de ações
• Algoritmos de busca consideram várias
sequencias de ações possíveis.
• As sequencias de ações possíveis que
começam a partir do estado inicial formam
uma árvore de busca
1
Gerando sequencia de ações
• Começa-se pelo estado inicial.
• Em cada ponto, deve-se testar para checar se a solução foi encontrada.
• Se não for o caso, deve-se aplicar os operadores e gerar novos estados: expansão de estados.
• Se há somente um caminho, ele deve ser tomado.
• Se há múltiplos caminhos, deve-se escolher uma opção a ser considerada primeiro.
• Busca: escolhe-se uma opção e deixa-se as demais para serem consideradas posteriormente, se a escolhida não levar à uma solução.
Gerando sequencia de ações
• Qual estado expandir primeiro?
• Processo de busca: uma árvore de busca é colocada sobre o espaço de estados: – Raiz: estado inicial
– Folhas: estados sem sucessores: • Por não terem sucessores, ou
• Por não terem sido expandidos ainda.
• OBS: Espaço de estados árvore de busca
Infraestrutura para algoritmos de busca
Para cada nó n da árvore tem-se:
• n. ESTADO: o estado no espaço de estado a que o nó corresponde.
• n.PAI: o nó na árvore de busca que gerou esse nó.
• n.AÇÃO: a ação que foi aplicada ao pai para gerar o nó.
• n . CUSTO DO CAMINHO: o custo, denotado por g(n), do caminho do estado inicial até o nó.
Estrutura de dados do nó
• Um nó é uma anotação da estrutura de dados usada para representar a árvore na busca.
• Um estado corresponde a uma configuração do mundo. • Os nós estão em caminhos particulares (definidos por
ponteiros NÓ-PAI), enquanto os estados não estão.
Infraestrutura para algoritmos de busca
• Nó: Estrutura de dados usada para representar a árvore de busca para uma instancia particular de um problema, gerada por um algoritmo específico.
• Estado: configuração ou conjunto de configurações do mundo.
• Borda: conjunto de todos os nós folhas disponíveis para expansão em um dado ponto.
• OBS: Dois nós diferentes podem conter o mesmo estado, se tiverem sido gerados por meio de duas sequencias diferentes de ações
Critérios para avaliar o desempenho do algoritmo de busca
• Completeza: O algoritmo oferece a garantia de encontrar uma solução quando ela existir?
• Otimização: A estratégia encontra a solução ótima (tem o menor custo de caminho entre todas as soluções)?
• Complexidade de tempo: Quanto tempo ele leva para encontrar uma solução?
• Complexidade de espaço: Quanto de memória é necessário para executar a busca?
10
Critérios para avaliar o desempenho do algoritmo de busca
• A complexidade de tempo e de espaço de memória são considerados em relação a alguma medida da dificuldade do problema.
• Para o problema representado por grafos, a medida é o
tamanho do grafo do espaço de estados, |V|+|E| onde: – |V| conjunto de vértices (nós) do grafo – |E| conjunto de arestas (arcos) do grafo
• Em IA, o grafo é representado de forma implícita pelo estado inicial e pela função sucessor e com frequência é infinito.
11
Critérios para avaliar o desempenho do algoritmo de busca
• A complexidade para IA é expressa em termos de três quantidades:
– b: o fator de ramificação ou número máximo de
sucessores de qualquer nó. – d: a profundidade do nó objetivo menos profundo
(número de passos do estado raiz até o estado objetivo mais próximo).
– m: comprimento máximo de qualquer caminho no espaço
de estados.
12
Critérios para avaliar o desempenho do algoritmo de busca
• O tempo é medido em termos do número de nós gerados durante a busca.
• O espaço é medido em termos do número
máximo de nós armazenados na memória. • Para avaliar a efetividade de um algoritmo de
busca pode-se considerar: – Custo de busca – Custo total
13
Critérios para avaliar o desempenho do algoritmo de busca
• Custo de busca: – Depende da complexidade de tempo
– Pode incluir um termo para uso da memória
• Custo total: – Combina custo de busca e o custo de caminho de
solução encontrada
– Exemplo: rota Arad-Bucarest, custo de busca é o tempo exigido pela busca; custo de caminho é o comprimento total em km da solução encontrada.
14
Solução para o Problema
• Um problema pode ser visto como uma tripla: {I,O,B} – I = estado ou estados iniciais – O = conjunto de operações – B = estado ou estados objetivo
• Sair do estado inicial e através de uma sequencia de operações chegar ao estado final
15
I B O
Estratégias de Busca
• Busca Cega (Sem informação/Não informada) – Não tem informação sobre qual sucessor é mais promissor
para atingir a meta.
• Busca Heurística (Busca Informada/Com Informação) – Possui informação (estimativa) de qual sucessor é mais
promissor para atingir a meta.
– É uma busca cega com algum guia ou orientação.
• Todas as estratégias de busca se distinguem pela ordem em que os nós são expandidos.
16
Estratégias de Busca Cega
• Busca em Largura
• Busca de Custo Uniforme
• Busca em Profundidade
• Busca em Profundidade Limitada
• Busca em Profundidade Iterativo
• Busca Bidirecional
17
Busca em Largura ...
• BFS – Breadth-first search
• Ordem de expansão dos nós:
1. Nó raiz
2. Todos os nós de profundidade 1
3. Todos os nós de profundidade 2, etc …
18
20
Busca em Largura ...
• Faz uma busca sistemática examinando primeiro os módulos próximos à raiz.
• Exemplo: Caminho para encontrar o nó G, usando a Busca em Largura: Caminho = { B, F, D, A, C, E, G }
Avaliação da Busca em Largura...
• A busca é completa se o nó objetivo mais raso estiver em alguma profundidade finita d (desde que o fator de ramificação b seja finito).
• A busca será ótima se o custo do caminho for uma função não-decrescente da profundidade do nó (todas as ações têm o mesmo custo).
21
Observação: se a função for decrescente, o nó mais raso não será o ótimo pois não terá o menor custo caminho
Avaliação da Busca em Largura ...
Supor uma árvore binária
• O nó raiz cria no espaço de estados 2 sucessores, no nível seguinte 4, e assim por diante
22
Avaliação da Busca em Largura ...
Complexidade do tempo e do espaço:
• Se cada nó no espaço de estados tem b sucessores: o número de nós gerados no nível 1 é b, no nível 2 é b2...
• Supondo que a solução esteja na profundidade d. Então, o número total de nós gerados é:
b + b2 + b3 .... + bd = O(bd)
23
Avaliação da Busca em Largura ...
• Se a aplicação do teste de objetivo para nós for ao serem selecionados para a expansão, em vez de ao serem gerados, toda a camada de nós na profundidade d seria expandida antes que o objetivo fosse detectado então no nível d+1 seriam gerados bd+1-b nós:
b + b2 + b3 .... + bd + (bd +1-b) = O(bd +1)
24
Avaliação da Busca em Largura ...
• A complexidade de espaço será O(bd) ou O(bd +1), será dominada pelo tamanho da borda.
• A complexidade de espaço é igual à complexidade de tempo (mais um nó para a raiz).
25
Busca em largura para vários valores de profundidade d com fator de ramificação b =10;
1.000.000 nós/segundo e 1.000 bytes/nó
Busca de Custo Uniforme • No lugar de expandir o nó mais raso, expande o nó n com o
custo de caminho g(n) mais baixo:
Busca de Custo Uniforme
• Esta busca não se importa com o número de passos que um caminho tem, mas apenas com seu custo total.
• Pode ficar pressa a um laço infinito se existir um caminho com sequencia infinita de ações a custo zero.
Avaliação da Busca de Custo Uniforme
• A completeza será garantida se o custo de cada passo exceder uma constante positiva pequena (o custo de uma ação não é zero ).
• Devido aos custos de passo serem não negativos, o custo de
um caminho sempre aumenta à medida que se percorre o caminho (nós são adicionados).
• Assim, a busca de custo uniforme expande os nós na ordem
de seu custo de caminho ótimo. • Portanto, o primeiro nó objetivo que foi selecionado para
expansão deverá ser a solução ótima.
Verificando a Busca de Custo Uniforme • O teste objetivo é aplicado a um nó quando ele é selecionado
para a expansão e não quando é gerado pela primeira vez.
• Sempre que seleciona um nó para expansão, o caminho ideal para esse nó foi encontrado.
• É adicionado um teste, caso seja encontrado um caminho melhor para um nó atualmente na borda.
(1)80 (3) 99
(2) 80+97
(3) 99+211
(4) 80+97+101
Avaliação da Busca de Custo Uniforme
• Esta busca esta orientada por custos de caminho e não em profundidades, sua complexidade não esta caracterizada por b e d, senão por C* e :
– C* é o custo da solução ótima.
– é o custo de toda ação.
Avaliação da Busca de custo uniforme
• A complexidade de tempo e espaço do pior caso é O(b 𝐶∗/ε ) que pode ser maior que bd
• Pode explorar grandes árvores de pequenos passos antes de explorar caminhos envolvendo passos grandes.
• Quando todos os custos de passos forem iguais b 𝐶∗/ε será bd.
Obs:Função chão: 𝑥 = o maior inteiro que é menor ou igual a 𝑥
Avaliação da Busca de custo uniforme
• Quando o custos de passos forem iguais: – A Busca em largura pára logo que gerar um
objetivo, enquanto que a busca de custo uniforme examina todos os nós à profundidade do objetivo para verificar se algum deles tem custo mais baixo.
– A busca de custo uniforme tem mais trabalho, expandindo os nós à profundidade d desnecessariamente.
Busca em Profundidade ...
• DFS - Depht-first search
• Ordem de expansão dos nós:
1. Nó raiz
2. Primeiro nó de profundidade 1
3. Primeiro nó de profundidade 2, etc …
34
Busca em Profundidade ...
• Começa na raiz e avança para baixo em níveis cada vez mais profundos.
• Um operador é aplicado a um nó para gerar o próximo nó mais profundo na sequência.
• O processo continua até que uma solução é encontrada ou um retrocesso é forçado ao atingir-se um nó terminal que não é solução.
35
Busca em profundidade: Os nós explorados sem descendentes na borda são removidos da memória. Os nós na profundidade 3 não têm sucessores e M é o único nó objetivo.
Busca em Profundidade ... • Busca em profundidade com uma função recursiva incluindo um limite de
profundidade
Avaliação da Busca em Profundidade..
• Problema:
Garante uma solução, mas a busca pode ser muito demorada.
• Motivo:
muitas ramificações diferentes podem ter que ser consideradas até o nível mais profundo antes de uma solução ser atingida.
39
Avaliação da Busca em Profundidade..
• Busca em profundidade depende se é utilizada a busca em grafos ou a busca em árvore.
• A busca em grafos que evita estados repetidos e caminhos redundantes, é completa em estados finitos porque acabará por expandir cada nó.
• A busca em árvore não é completa, pode entrar em laços.
40
Avaliação da Busca em Profundidade..
• A busca em árvore modificada pode evitar laços em espaço de estados finitos, mas não evita a proliferação de caminhos redundantes.
• A complexidade temporal da busca em profundidade em grafo é limitada pelo tamanho de espaços de estado.
41
Avaliação da Busca em Profundidade..
• A busca em profundidade em árvore poderá gerar todos os nós O(bm) na árvore de busca (m é a profundidade máxima de qualquer nó) e isso pode ser muito maior do que o tamanho do espaço de estados.
• m pode ser maior que d (a profundidade da solução mais rasa) e é infinito se a árvore for ilimitada.
1
Avaliação da Busca em Profundidade..
• Para um espaço de estados com fator de ramificação b e profundidade máxima m, a busca exige o armazenamento de O(bm) nós.
2
Observações ...
• As buscas em profundidade e em largura não precisam ser realizadas em uma ordem específica.
• Em se tratando de memória utilizada, na busca em
profundidade é preciso armazenar todos os filhos não visitados de cada nó entre nó atual e nó inicial.
• Na busca em largura, antes de examinar nó a uma
profundidade d, é necessário examinar e armazenar todos os nodos a uma profundidade d – 1.
• Quanto ao tempo, a busca em profundidade é geralmente
mais rápida.
44
Busca em profundidade limitada
• O problema de caminhos infinitos da busca em profundidade pode ser atenuada pela busca em profundidade com um limite predeterminado l
• Dificuldades na escolha do l : – Se l < d (o objetivo mais raso esta além do limite de
profundidade)
– Se l > d , a busca não será ótima.
– A complexidade de tempo é O(bl) e de espaço O(bl)
– A busca em profundidade é um caso particular de busca em profundidade limitada com l =
1
Busca em profundidade limitada
• Os limites de profundidade podem se basear no conhecimento que se tem do problema.
• Mapa da Romênia: 20 cidades. A solução pode ter o comprimento 19 no caso mais longo, então l = 19.
46
Busca em profundidade limitada
• Verifica-se no mapa que uma cidade ‘a’ qualquer pode ser alcançada de outra cidade ‘b’ qualquer em no máximo nove passos.....
• O número 9 é conhecido como diâmetro do
espaço de estados e fornece um limite de profundidade para uma busca mais eficiente.
• Infelizmente, na maioria dos problemas, não se
conhece um bom limite de profundidade antes de se resolver o problema.
47
Busca em profundidade limitada
• A busca em profundidade limitada pode ser implementada como uma modificação simples do algoritmo geral de busca em árvore ou em grafos.
48
Busca em profundidade iterativa
• IDS - Iterative Deepening Search
• Busca que encontra o melhor limite de profundidade, usada com frequência em combinação com a busca em profundidade em árvore.
• O limite de profundidade (d) aumenta gradualmente até encontrar um objetivo.
Busca em profundidade iterativa
• Esta busca combina os benefícios da busca em profundidade e da busca em largura.
• Requisitos de memória é O(bd), equivalente à busca em profundidade.
• Como a busca em largura é completo quando o fator de ramificação é finito, e ótimo quando o custo de caminho é uma função não decrescente da profundidade do nó.
Busca em profundidade iterativa
• Nesta busca, os nós no nível inferior (d) são gerados uma vez, no penúltimo nível inferior duas vezes, ...., até os filhos da raiz, que são gerados d vezes. O número total de nós gerados é:
N(IDS) = (d)b + (d – 1)b2 +…+ (1)bd
Busca em profundidade iterativa
• Se b=10 e d=5, o número de nós gerados para este tipo de busca e para a busca em largura será:
N(IDS) = 50 + 400 + 3.000 + 20.000 + 100.000 = 123.450
N(BFS) = 10 + 100 + 1.000 + 10.000 + 100.000 = 111.100.
• Em geral, o aprofundamento iterativo é o método de busca sem informação preferido quando o espaço de busca é grande e a profundidade da solução não é conhecida.
Busca bidirecional
• Duas buscas simultâneas:
– Uma direta, a partir do estado inicial, e
– Outra inversa, a partir do objetivo.
Espera-se que as duas buscas se encontrem em um ponto intermediário.
Busca bidirecional
• A motivação é que bd/2 + bd/2 é muito menor que bd.
• A área dos dois círculos pequenos é menor que a área do único círculo grande com centro no início e que chega até o objetivo.
Busca bidirecional
• Na busca bidirecional substitui-se o teste de objetivo por uma verificação para ver se as bordas das duas buscas se cruzam, se isso ocorre, foi encontrada uma solução.
• Se um problema tem solução à profundidade d = 6 e cada direção executa a busca em largura de um nó por vez, no pior caso, as duas buscas se encontram quando tiverem gerado todos os nós à profundidade 3, para b = 10 tem-se: – Busca bidirecional 2.220 gerações de nós. – Busca em largura 1.111.110 gerações de nós.
Busca bidirecional
• A complexidade de tempo da busca bidirecional usando a busca em largura nas duas direções é O(bd/2). A complexidade do espaço é também O(bd/2).
• A redução da complexidade de tempo torna a busca bidirecional atraente, mas como realizaremos a busca inversa?
Busca bidirecional
• A busca inversa não é tão fácil quanto parece: – Sejam os predecessores de um estado x todos
aqueles estados que têm x como sucessor.
– A busca bidirecional requer um método de cálculo dos predecessores.
– Quando todas as ações no espaço de estados forem reversíveis, os predecessores de x serão apenas seus sucessores.
Outros casos podem exigir uma engenhosidade substancial.
Busca bidirecional
• No caso da localização de uma rota na Romênia, existe apenas um estado objetivo; assim, a busca inversa é muito semelhante à busca direta.
• Se houver vários estados objetivos, p.e., os dois estados objetivo livres de sujeira (aspirador de pó), pode-se construir um novo estado objetivo fictício cujos predecessores imediatos serão todos os estados objetivo reais.
Avaliação de estratégias de busca
b - fator de ramificação; d - profundidade da solução mais "rasa"; m - profundidade máxima da árvore de busca; l - limite de profundidade.
Anotações sobrescritas: a - completa se b é finito; b - completa se o custo do passo é ≥ para positivo; c - ótima se os custos dos passos são todos idênticos; d - se ambos os
sentidos utilizam busca em largura.
Observações ...
• Métodos de busca cega:
– Não examinam a árvore de forma ótima, o que poderia minimizar o tempo gasto para resolver o problema.
– Não fazem uso de nenhum conhecimento para encontrar sua solução, fazendo uma busca exaustiva dentro do seu espaço.
• Para contornar estes problemas, podem-se usar os métodos heurísticos.
62