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