Algoritmo de Busca para Grafos

Completo: Para qualquer problema ele encontrará a solução?
Ótimo: Se tem a solução, ele encontra o melhor caminho
Complexidade de Tempo: Projeção de crescimento da quantos nós forem espandidos.
Complexidade de Espaço: Algum nó é retirado da memoria durante a busca? Se não complexidade é igual a complexidade de tempo.

Busca em Largura (BFS)
Utiliza a estrutura de fila. Coloca em uma fila todos os nos visitados e também seus vizinhos, realizando assim uma busca nivel a nivel.
Caracteristicas do Algoritmo:
Completo;
Ótimo;
Complexidade de Tempo: O(b^d);
Complexidade de Espaço: O(b^d).

Busca em Profundidade (DFS)
Nessa estratégia de busca um dos nós do nível mais profundo da árvore de busca
sempre é expandido. Somente quando a busca atinge um nó cujos filhos possuem estados
que já foram expandidos outrora é que a busca expandirá algum dos nós pertencentes aos
níveis acima deste, processo este conhecido como backtrack.

Completo: não (Falha com caminhos infinitos ou loops)
Completa: sim, se L >= d! (Determinar uma profundidade máxima L, no qual a DFS deve parar.)
Ótimo: não


Busca em Aprofundamento Iterativo (IDS)
Faz repetidas buscas em profundidade, aumentando o limite a cada iteração.
Combina os benefícios da BFS e DFS
Completo;
Ótimo;
Não gasta muita memória. Repetição da expansão de estados.
Não é tão ruim, pois a maior parte dos estados está nos níveis mais baixos
Na verdade, gera menos estados que o BFS, pois não gera estados no nível d+1



Exercios e Exemplos de Algoritmos para Grafos