Busca Uniforme

 

 

A estratégia de busca uniforme é uma pequena modificação da estratégia de busca em largura. Na busca em largura primeiro expande-se o nó raiz, depois todos os nós gerados por esse, e assim por diante até que se chegue ao estado meta. Ou seja, todos os nós que estão numa profundidade d da árvore serão expandidos e visitados antes que os nós que estão numa profundidade d+1.

A estratégia de busca uniforme é basicamente a mesma coisa. Mas ao invés de pegar o primeiro nó expandido que está na lista aguardando processamento, o nó que possui o menor custo (g(N)) será escolhido para ser expandido. Se certas condições sempre forem cumpridas, garante-se que a primeira solução encontrada será a mais barata. Uma condição é a seguinte: o custo do caminho nunca deve ir diminuindo conforme avançamos por ele, em outras palavras, é importante que:

g(Sucessor)>=g(N)

em todos os nós N, g(N) é o custo conhecido de ir-se da raiz até o nódulo N.

 

Abaixo está sendo apresentado o pseudocódigo do mesmo.

 

Algoritmo Busca - Uniforme

1. 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;

Parar

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.

 

Análise da Complexidade

 

O custo de espaço e tempo referente a estratégia de busca uniforme pode ser visualizado no quadro abaixo:

 

 

Profundidade

Nós

Tempo

Memória

0

1

1 milisegundo

100 bytes

2

111

0.1 segundos

11 kilobytes

4

11,111

11 segundos

1 megabytes

6

106

18 minutos

111 megabytes

8

108

31 horas

11 gigabytes

10

1010

128 dias

1 terabyte

12

1012

35 anos

111 terabytes

14

1014

3500 anos

11,111 terabytes

Quadro 1: Tempo, memória e nós gerados para se chegar ao estado meta

de acordo a profundidade em que se encontra a solução

 

Conteúdo