Glossário IA
O dicionário completo da Inteligência Artificial
Busca em Largura (BFS)
Algoritmo de travessia de grafo que explora os nós nível por nível, utilizando uma fila para visitar sistematicamente todos os vértices acessíveis a partir de um ponto de partida.
Busca em Profundidade (DFS)
Técnica de travessia recursiva que explora o mais longe possível em cada ramo antes de retroceder, geralmente implementada com uma pilha ou recursivamente.
Algoritmo de Dijkstra
Algoritmo guloso que determina o caminho mais curto de um vértice de origem para todos os outros vértices em um grafo ponderado com pesos não negativos.
Algoritmo A*
Algoritmo de busca de caminho ótimo que combina heurística e custo real, utilizando uma função de avaliação f(n) = g(n) + h(n) para guiar eficientemente a exploração.
Algoritmo de Bellman-Ford
Algoritmo de caminho mais curto capaz de detectar ciclos de peso negativo, relaxando iterativamente todas as arestas para propagar as distâncias mínimas.
Algoritmo de Floyd-Warshall
Algoritmo de programação dinâmica que calcula os caminhos mais curtos entre todos os pares de vértices, considerando sucessivamente cada vértice como ponto intermediário.
Busca Bidirecional
Técnica que otimiza a busca de caminho realizando simultaneamente duas travessias a partir dos vértices de origem e destino até sua interseção.
Ordenação Topológica
Ordenação linear dos vértices de um grafo acíclico direcionado onde cada aresta u→v respeita a restrição de que u aparece antes de v na ordem final.
Algoritmo de Tarjan
Algoritmo linear que identifica os componentes fortemente conectados de um grafo direcionado usando uma busca em profundidade com numeração e pilhas.
Componentes Fortemente Conectados
Subgrafos maximais onde cada vértice é acessível a partir de qualquer outro vértice do mesmo subgrafo por caminhos direcionados.
Ponto de Articulação
Vértice cuja remoção aumenta o número de componentes conectados do grafo, identificado por algoritmos de busca em profundidade com numeração.
Pontes em um Grafo
Arestas críticas cuja remoção desconecta o grafo, aumentando o número de componentes conectados, detectadas por buscas em profundidade especializadas.
Algoritmo de Kosaraju
Algoritmo em duas fases que utiliza duas buscas em profundidade para identificar os componentes fortemente conectados de um grafo direcionado.
Busca em Profundidade Limitada
Variante do DFS que restringe a profundidade de exploração a um limite predefinido, evitando a explosão combinatória em grafos profundos.
Busca Iterativa em Profundidade
Estratégia de busca que combina as vantagens de BFS e DFS, realizando séries de buscas em profundidade limitada com profundidades crescentes.
Algoritmo de Johnson
Algoritmo eficiente para os caminhos mais curtos entre todos os pares em grafos esparsos ponderados, combinando Dijkstra e reponderação de Bellman-Ford.
Busca de Custo Uniforme
Variante de Dijkstra que explora o nó de custo acumulado mínimo sem heurística, garantindo a otimalidade para grafos com custos positivos.
Ciclo Euleriano
Caminho que atravessa cada aresta exatamente uma vez, existindo se e somente se cada vértice possuir um grau par em um grafo conectado.
Ciclo Hamiltoniano
Caminho que visita cada vértice exatamente uma vez, problema NP-completo sem condição necessária e suficiente simples para a existência.