Arquivo da tag: inteligência artificial

Busca em largura

A busca em largura é um método de busca que expande e examina sistematicamente todos os nós da árvore, em busca de uma solução, é um método de busca que não utiliza informação(busca cega). Em outras palavras podemos dizer que o algoritmo realiza uma busca exaustiva em toda a árvore, sem considerar seu alvo de busca, até que ele o encontre(ele não utiliza uma heurística).

Este método de busca é muito simples, ele expande o nó raiz primeiramente e em seguida todos os sucessores do nó raiz são expandidos, depois os sucessores desses nós e assim por diante até encontrar a informação procurada na árvore.

Do ponto de vista do algoritmo, todos os nós filhos obtidos pela expansão de um nó são adicionados a uma fila (FIFO). Em implementações típicas, nós que ainda não foram examinados por seus vizinhos são colocados numa lista (como por exemplo uma fila ou lista ligada) que é chamado de “aberto”. Uma vez examinados, são colocados numa lista “fechado”.

Veja como funciona a lógica da busca em largura nas imagens abaixo primeiramente expande o primeiro nó e todos seus sucessores:


Em seguida os sucessores do nó raiz e assim por diante até finalizar a busca:

Veja o algoritmo utilizado para resolver o método de busca por largura:

Busca-em-Largura (nAdjr)
1  para u ← 1 até n faça
2  cor[u] ← branco
3  cor[r] ← cinza
4  F ← Cria-Fila(r)
5  enquanto  F não está vazia faça
6  u ← Sai-da-Fila(F)
7  para cada v em Adj[u] faça
8  se cor[v] = branco
9  então  cor[v] ← cinza
10  Entra-na-Fila(vF)
11  cor[u] ← preto
12  devolva  cor[1..n]