- Busca de Custo Uniforme (Busca Ordenada)
*Apostila 1: Algoritmos e Problemas de Busca (24/25)
Expande o nó de menor custo da trajetória a cada visita.
Usa-se fila de prioridades (como visto em S.O. no 3º Período) : menor valor, maior prioridade.
Completo? Sim
Ótimo? Sim, pois encontra a solução que possuir o menor valor (custo)
Complexidade de Tempo? Número de nós com custo <= d
Complexidade de Espaço? Número de nós com custo <= d
- Greedy Search (Algoritmo Guloso)
Trabalha partindo dos valores informados pela heurística (ou pelo conjunto de heurísticas), sem enxergar o problema como um todo, por isso, ele pode tomar decisões incorretas (como cair em um loop infinito).
Também utiliza fila de prioridades: menor valor, maior prioridade.
A heurística guia a busca, mas não representa o custo real.
Completo? Não
Ótimo? Não, mas pode ser dependendo da heurística utilizada
Complexidade de Tempo? O(b^m), mas pode variar de acordo com a heurística utilizada
Complexidade de Espaço? O(b^m)
Observação:
Profundidade -> Pilha
Largura -> Fila
Assinar:
Postar comentários (Atom)
Nenhum comentário:
Postar um comentário