Quais são as principais propriedades que são usadas para avaliar e podem ser usadas para comparação entre os algoritmos de busca? (4 escores)
Passo 1
O enunciado pede que eu indique as quatro principais propriedades (escores) usadas para avaliar e comparar algoritmos de busca. Vou listar claramente o que preciso entregar:
- Deve apresentar 4 propriedades (escores) principais.
- Cada propriedade precisa ser explicada de modo que eu entenda o que significa, como medir e por que importa na hora da prova.
Não me foram dadas outras informações; então vou assumir o contexto padrão de algoritmos de busca em grafos/árvores (como BFS, DFS, UCS, A*, busca gulosa).
Passo 2
Primeira propriedade: completude.
- O que é: dizer que um algoritmo é completo significa que, se existir pelo menos uma solução no espaço de busca, o algoritmo vai encontrá‑la em tempo finito.
- Como medir / verificar: em exercícios, verifica‑se condições do espaço (por exemplo, fator de ramificação finito) e do algoritmo (se percorre sistematicamente todos os nós até achar a solução).
- Quando vale: BFS é completo quando o fator de ramificação
é finito e a solução tem profundidade finita . DFS pode não ser completo se houver ciclos ou caminhos infinitos, a menos que haja limitação de profundidade. - Por que importa: numa prova você justifica que um método é adequado quando é essencial garantir encontrar alguma solução (por exemplo, caminhos em labirintos).
Passo 3
Segunda propriedade: optimalidade (otimalidade).
- O que é: um algoritmo é ótimo se, quando encontra uma solução, ela tem custo mínimo segundo a função custo do problema (por exemplo, soma dos pesos das arestas).
- Conceitos úteis: custo do caminho
e heurística . - Condições típicas:
- Busca de custo uniforme (Uniform Cost Search) é ótima quando expande caminhos em ordem de custo crescente.
- A* é ótima se a heurística usada for admissível (isto é, nunca superestima o custo real até a meta) e, idealmente, consistente (monótona).
- Como demonstrar em prova: mostre que a ordenação de expansão garante que nenhum caminho mais barato à meta foi ignorado; com A* mencione que
custo mínimo real de até a meta (admissibilidade).
Passo 4
Terceira propriedade: complexidade de tempo.
- O que é: mede quanto trabalho o algoritmo faz — normalmente contado como número de nós gerados ou expandidos antes de encontrar a solução.
- Como expressar: usa‑se notação assintótica (por exemplo,
) e parâmetros padrão: fator de ramificação , profundidade da solução , profundidade máxima . - Exemplos clássicos:
- BFS: tempo aproximado
(expande todos os nós nível a nível até ). - DFS: tempo pode ser
no pior caso (onde é profundidade máxima) — pode ser melhor ou pior dependendo da instância. - A*: no pior caso também é exponencial, mas um bom
reduz muito o número de nós expandidos.
- BFS: tempo aproximado
- Dica de prova: quando pedirem comparar algoritmos, explique com
e e, se possível, diga se a heurística melhora ou piora a complexidade prática.
Passo 5
Quarta propriedade: complexidade de espaço (memória).
- O que é: mede a memória máxima usada pelo algoritmo, normalmente o número máximo de nós armazenados simultaneamente (fronteira + nós gerados não expandidos).
- Fórmulas/valores típicos:
- BFS: espaço
— precisa manter toda a fronteira de nível . - DFS: espaço
— guarda apenas um caminho de profundidade mais os irmãos imediatos (muito menor que BFS se não for grande). - A*: geralmente exige espaço similar ao tempo (pode ser
na piora), porque mantém a fronteira ordenada por .
- BFS: espaço
- Por que importa: em problemas grandes a memória costuma ser o limitador prático; um algoritmo rápido mas que consome toda a RAM é inútil.
Passo 6
Como usar essas 4 propriedades na comparação (passo a passo prático para a prova)
- Ao comparar dois algoritmos, sempre discuta: completude, optimalidade, tempo e espaço — nessa ordem se quiser convencer o examinador.
- Use parâmetros
, , e mencione se há heurística (e se é admissível/consistente). - Exemplos rápidos:
- BFS vs DFS: BFS é completo e ótimo (se custos unitários) e tem tempo/espaco
; DFS tem espaço melhor mas pode não ser completo/ótimo. - UCS vs A*: UCS é ótimo e completo (com custos positivos) e explora por custo; A* é ótimo se
admissível e normalmente expande menos nós que UCS se for informativa. - Busca gulosa (greedy): rápido em muitas instâncias (bom tempo prático) mas não é ótima nem completa em geral; usa pouca memória comparada a A*? Depende.
- BFS vs DFS: BFS é completo e ótimo (se custos unitários) e tem tempo/espaco
- Observação de prova: sempre explique condições (por exemplo, “A* é ótima se
é admissível”) — mostrar essas condições ganha pontos.
Passo 7
Resumo final e dica motivacional
- Memorize as quatro propriedades e as definições curtas: completude, optimalidade, tempo, espaço.
- Na prova: escreva primeiro a definição, depois aplique aos algoritmos pedidos, mencionando
e se há heurística (admissível/consistente). - Respira fundo — com essas quatro ferramentas você consegue justificar quase qualquer comparação entre algoritmos de busca. Tô torcendo por você!
Resposta
Completude
Optimalidade
Complexidade de tempo (número de nós gerados/expandidos)
Complexidade de espaço (memória máxima usada)
Optimalidade
Complexidade de tempo (número de nós gerados/expandidos)
Complexidade de espaço (memória máxima usada)