Faculdade

#Busca Em largura
@Busca Em largura Básica = Definição A busca em largura se substituimos ACRESCENTAR-NA-FILA por ACRESCENTAR-NOFIM no algoritmo geral de busca.
Algoritmo
nodos <-- CRIAR-FILA(estado-inicial) loop se nodos é vazio retorna falha nodo <-- TIRAR-PRIMEIRO(nodos) se TESTE-SUCESSO(nodo) tem sucesso retorna nodo novos-nodos <-- EXPANDIR(nodo) nodos <-- ACRESCENTAR-NO-FIM(nodos,novos-nodos) fim Análise de Complexidade Oculpa Muita Memória e Não Carrega em “pouco” tempo (complexidade exponencial): O(bp) onde b é o fator de ramificação e p a profundidade.
@Busca Em largura a Custo Uniforme
Definição Modificação do algoritmo de busca em largura para aumentar o conjunto de problemas pelos quais o método retorna uma solução ótima. Ao invés de dar prioridade aos nodos que se encontram no nível menos profundo, o algoritmo escolhe o nodo que tem o menor custo. Agora, a condição para obter uma solução ótima é que o custo para passar ao próximo estado nunca seja negativo.
Algoritmo nodos <-- CRIAR-FILA(estado-inicial) loop se nodos é vazio retorna falha nodo <-- TIRAR-PRIMEIRO(nodos) se TESTE-SUCESSO(nodo) tem sucesso retorna nodo novos-nodos <-- EXPANDIR(nodo) nodos <-- ORDENAR(ACRESCENTAR-NA-FILA(nodos, novos-nodos)) fim Análise de complexidade Com esse Algoritmo de busca encontra-se primeiro o caminho mais curto até o objetivo.
Complexidade em memória e tempo igual à da busca em largura: O(bp) onde b é o fator de ramificação e p a profundidade.
#Busca em Profundidade
Definição Conhecido também como Depth-First.
A busca em profundidade é a técnica mais vantajosa em termos de uso da memória.
Infelizmente, ela apresenta a desvantagem de não necessáriamente retornar uma solução (ou mergulhar demais antes de voltar a un nível de profundidade mais baixa onde se encontra a solução).
Algoritmo
nodos <-- CRIAR-FILA(estado-inicial) loop se nodos é vazio retorna falha nodo <--