Algoritmos de Busca Cega e Agentes Inteligentes

Busca cega: conceitos e tipos

Busca cega — estratégias para determinar a ordem de expansão dos nós. Principais estratégias:

• Busca em largura
• Busca de custo uniforme
• Busca em profundidade
• Busca com aprofundamento iterativo

Direção da expansão:

1. Do estado inicial para o estado objetivo
2. Do estado objetivo para o estado inicial
3. Busca bidirecional

Critérios de avaliação das estratégias de busca

Os critérios usados para avaliar estratégias de busca incluem:

• Completude — se a estratégia encontra uma solução quando esta existe
• Custo de tempo — tempo de execução
• Custo de memória — uso de memória durante a busca
• Qualidade — por exemplo, menor custo do caminho

Busca em largura

A ordem de expansão dos nós na busca em largura é:

1. Nó raiz
2. Todos os nós de profundidade 1
3. Todos os nós de profundidade 2
4. e assim por diante

Descrição: A busca em largura é um algoritmo para busca em grafos e árvores. Intuitivamente, começa pelo vértice raiz e explora todos os vértices vizinhos; depois, para cada um desses vértices, explora os seus vizinhos ainda não visitados, e assim por diante, até encontrar o alvo da busca.

Busca de custo uniforme

Descrição: A busca de custo uniforme modifica a busca em largura: ela expande o nó da fronteira com menor custo de caminho (na fronteira do espaço de estados). Cada operador pode ter um custo associado diferente, medido pela função g(n), onde g(n) dá o custo do caminho desde a origem até o nó n. Na busca em largura, g(n) = profundidade(n).

Busca em profundidade

Descrição: A busca em profundidade é usada para travessia em árvores ou grafos. O algoritmo começa em um nó raiz (ou em algum nó escolhido como raiz no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos antes de retroceder.

Busca bidirecional

Descrição: Busca em duas direções: para frente, a partir do nó inicial, e para trás, a partir do nó final (objetivo). A busca termina quando os dois processos geram um mesmo estado intermediário. É possível utilizar estratégias diferentes em cada direção.

Aprofundamento iterativo

Descrição: Estratégia geral para encontrar o menor limite de profundidade. O limite é incrementado até d (desconhecido). A meta é encontrada na profundidade d, a profundidade do nó meta mais raso. Combina os benefícios da busca em profundidade (baixo uso de espaço) e da busca em largura (possível completude e otimalidade). Semelhante à busca em profundidade, possui custo de memória reduzido; tal como a busca em largura: é completa quando o fator de ramificação é finito e é ótima quando o custo do caminho é uma função não decrescente da profundidade do nó.

Agente inteligente

Agente inteligente é um software desenvolvido para automatizar e executar tarefas em uma rede para o usuário. É uma ferramenta que economiza tempo no monitoramento e na coleta de informações solicitadas pela empresa. O usuário define os parâmetros da missão que o agente irá executar autonomamente e comunicar os seus resultados.

Propriedades de agentes

• Autonomia: capacidade de agir independentemente de intenção humana.
• Racionalidade: capacidade de avaliar a melhor decisão a ser tomada.

Exemplo de cálculo de nós e memória

Ex.: b^n = n^0
nós = (10)^0 + (10)^1 + (10)^2 + (10)^3
nós = 1 + 10 + 100 + 1000
nós = 111100 * 100 (cada nó ocupa na memória) = 11mb

Em que situação é recomendado esse tipo de busca? Quando eu tenho uma largura de busca pequena.