Vocabulário Francês e Algoritmos de Busca

Vocabulário

• "el último z el proximo" traduz-se para "le dernier & le prochain" (o último e o próximo).
• "une edificio" significa "un édifice" (um edifício).
• "inmenso" é o mesmo que "imense" (imenso).
• "lagugllama la atención" expressa "ce qui attire l'attention" (o que atrai a atenção).
• "la calavera" corresponde a "la tête de mort" (a caveira ou a cabeça da morte).
• "unt peligro" significa "un danger" (um perigo).
• "peligroso" é traduzido como "dongaarcuх" (perigoso).
• "el número" significa "le nombre" (o número).
• "denunciar" corresponde a "dimoncer" (denunciar).
• "los riesgos" são "les risques" (os riscos).
• "sensibilizar" equivale a "sensibiliser" (sensibilizar) e "fair prende" (tornar consciente).

Algoritmos de Busca

Busca Não-Informada

• Não usa informações heurísticas sobre o problema.

Busca em Largura (BFS)

• Usada para encontrar o caminho mais curto em grafos não ponderados.
• É completa e ótima se o custo por passo é constante.
• A complexidade de espaço é $$O(b^d)$$.
  • b = fator de ramificação
  • d = profundidade da solução
• Implementada com uma fila FIFO (First-In-First-Out).
• Expande os nós em ordem de proximidade da raiz.

Busca de Custo Uniforme

• Encontra o caminho de menor custo.
• É completa se o custo do passo for maior que 0.
• É ótima.
• A complexidade de espaço é $$O(b^{\lceil C*/\epsilon \rceil})$$.
  • C* = custo da solução ótima
  • epsilon = menor custo do passo
• Usa uma fila de prioridade ordenada pelo custo do caminho.
• Expande sempre o nó de menor custo na borda.

Busca em Profundidade (DFS)

• Pode ser usada para testar a conectividade de um grafo.
• Não é completa e nem ótima.
• A complexidade de espaço é $$O(bm)$$.
  • b = fator de ramificação
  • m = profundidade máxima da árvore de busca.
• Implementada com uma pilha LIFO (Last-In-First-Out).
• Expande o nó mais profundo na borda atual.

Busca com Aprofundamento Iterativo (IDS)

• Útil em espaços de busca grandes com profundidade desconhecida.
• É completa e ótima se o custo for constante por passo.
• A complexidade de espaço é $$O(bd)$$.
  • b = fator de ramificação
  • d = profundidade da solução
• Realiza buscas em profundidade limitadas com profundidade crescente.
• Combina os benefícios da busca em largura e em profundidade.

Busca Informada (Heurística)

• Usa informações heurísticas sobre o problema para guiar a busca.

Busca Gulosa (Greedy)

• Expande o nó que parece estar mais próximo do objetivo.
• A função heurística $$h(n)$$ estima o custo do caminho mais barato de n até o objetivo.
• Não é completa e nem ótima.
• A complexidade de espaço é $$O(b^m)$$.
  • b = fator de ramificação
  • m = profundidade máxima da árvore de busca

Busca A*

• Minimiza o custo total do caminho, dado por $$f(n) = g(n) + h(n)$$.
  • $$g(n)$$ = custo do caminho da partida até o nó n
  • $$h(n)$$ = estima o custo do caminho mais barato de n até o objetivo
• Para garantir a otimalidade, a heurística deve ser admissível e consistente.
  • Admissibilidade: $$h(n)$$ nunca superestima o custo para alcançar o objetivo.
  • Consistência: Para todo nó n e toda ação a, $$h(n) \le c(n, a, sucessor(n, a)) + h(sucessor(n, a))$$.
• É completa e ótima.
• A complexidade de espaço é $$O(b^d)$$.
  • b = fator de ramificação
  • d = profundidade da solução