Глоссарий ИИ
Полный словарь искусственного интеллекта
Обход в ширину (BFS)
Алгоритм обхода графа, исследующий узлы уровень за уровнем, использующий очередь для систематического посещения всех достижимых вершин из начальной точки.
Обход в глубину (DFS)
Техника рекурсивного обхода, исследующая как можно дальше в каждой ветви перед возвратом назад, обычно реализуется с использованием стека или рекурсивно.
Алгоритм Дейкстры
Жадный алгоритм, определяющий кратчайший путь от исходной вершины ко всем остальным вершинам во взвешенном графе с неотрицательными весами.
Алгоритм A*
Алгоритм поиска оптимального пути, сочетающий эвристику и реальную стоимость, использующий функцию оценки f(n) = g(n) + h(n) для эффективного направления исследования.
Алгоритм Беллмана-Форда
Алгоритм кратчайшего пути, способный обнаруживать циклы отрицательного веса, итеративно расслабляя все рёбра для распространения минимальных расстояний.
Алгоритм Флойда-Уоршелла
Алгоритм динамического программирования, вычисляющий кратчайшие пути между всеми парами вершин, последовательно рассматривая каждую вершину как промежуточную точку.
Двунаправленный поиск
Техника, оптимизирующая поиск пути, выполняя одновременно два обхода от исходной и целевой вершин до их пересечения.
Топологическая сортировка
Линейное упорядочение вершин ациклического ориентированного графа, где каждое ребро u→v соблюдает ограничение, что u появляется перед v в конечном порядке.
Алгоритм Тарьяна
Линейный алгоритм для выявления сильно связных компонент в ориентированном графе с использованием поиска в глубину, нумерации и стеков.
Сильно связные компоненты
Максимальные подграфы, в которых каждая вершина достижима из любой другой вершины того же подграфа по направленным путям.
Точка сочленения (шарнир)
Вершина, удаление которой увеличивает количество связных компонент графа; определяется алгоритмами поиска в глубину с нумерацией.
Мосты в графе
Критические рёбра, удаление которых увеличивает количество связных компонент графа, разрывая его связность; выявляются специализированными обходами в глубину.
Алгоритм Косараджу
Двухфазный алгоритм, использующий два обхода в глубину для нахождения сильно связных компонент в ориентированном графе.
Поиск в глубину с ограничением
Вариант DFS, ограничивающий глубину обхода заранее заданным пределом для предотвращения комбинаторного взрыва в глубоких графах.
Итеративный углубляющийся поиск в глубину
Стратегия поиска, сочетающая преимущества BFS и DFS путём выполнения серии обходов в глубину с ограничением и последовательно увеличивающейся глубиной.
Алгоритм Джонсона
Эффективный алгоритм для поиска кратчайших путей между всеми парами вершин в разреженных взвешенных графах, комбинирующий алгоритмы Дейкстры и Беллмана-Форда с репондерированием.
Поиск по равномерной стоимости
Вариант алгоритма Дейкстры, исследующий узел с минимальной накопленной стоимостью без эвристики, гарантирующий оптимальность для графов с положительными весами.
Эйлеров цикл
Маршрут, проходящий по каждому ребру ровно один раз, существует тогда и только тогда, когда каждая вершина имеет четную степень в связном графе.
Гамильтонов цикл
Путь, посещающий каждую вершину ровно один раз, NP-полная задача без простого необходимого и достаточного условия для существования.