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 b é finito e a solução tem profundidade finita d. 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 g(n) e heurística h(n).
  • 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 h(n) \le custo mínimo real de n 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, O(\cdot)) e parâmetros padrão: fator de ramificação b, profundidade da solução d, profundidade máxima m.
  • Exemplos clássicos:
    • BFS: tempo aproximado O(b^d) (expande todos os nós nível a nível até d).
    • DFS: tempo pode ser O(b^m) no pior caso (onde m é profundidade máxima) — pode ser melhor ou pior dependendo da instância.
    • A*: no pior caso também é exponencial, mas um bom h(n) reduz muito o número de nós expandidos.
  • Dica de prova: quando pedirem comparar algoritmos, explique com b e d 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 O(b^d) — precisa manter toda a fronteira de nível d.
    • DFS: espaço O(b\cdot m) — guarda apenas um caminho de profundidade mais os irmãos imediatos (muito menor que BFS se m não for grande).
    • A*: geralmente exige espaço similar ao tempo (pode ser O(b^d) na piora), porque mantém a fronteira ordenada por f(n).
  • 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 b, d, m e mencione se há heurística h (e se é admissível/consistente).
  • Exemplos rápidos:
    • BFS vs DFS: BFS é completo e ótimo (se custos unitários) e tem tempo/espaco O(b^d); DFS tem espaço melhor O(bm) mas pode não ser completo/ótimo.
    • UCS vs A*: UCS é ótimo e completo (com custos positivos) e explora por custo; A* é ótimo se h admissível e normalmente expande menos nós que UCS se h 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.
  • Observação de prova: sempre explique condições (por exemplo, “A* é ótima se \,h é 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 b,d,m 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)

Exercícios relacionados