В информатике алгоритм поиска — это алгоритм , предназначенный для решения задачи поиска . Алгоритмы поиска работают для извлечения информации, хранящейся в определенной структуре данных или рассчитанной в пространстве поиска проблемной области, с дискретными или непрерывными значениями .
Хотя поисковые системы используют поисковые алгоритмы, они относятся к изучению поиска информации , а не к алгоритмике.
Подходящий алгоритм поиска часто зависит от искомой структуры данных и может также включать предварительные знания о данных. Алгоритмы поиска можно сделать быстрее и эффективнее с помощью специально созданных структур базы данных, таких как деревья поиска , хэш-карты и индексы базы данных . [1] [2]
Алгоритмы поиска можно разделить в зависимости от механизма поиска на три типа алгоритмов: линейные, двоичные и хеширующие. Алгоритмы линейного поиска линейно проверяют каждую запись на наличие записи, связанной с целевым ключом. [3] Бинарный или полуинтервальный поиск неоднократно нацелен на центр структуры поиска и делит пространство поиска пополам. Алгоритмы поиска по сравнению улучшают линейный поиск за счет последовательного исключения записей на основе сравнения ключей до тех пор, пока не будет найдена целевая запись, и могут применяться к структурам данных с определенным порядком. [4] Алгоритмы цифрового поиска работают на основе свойств цифр в структурах данных с использованием числовых ключей. [5] Наконец, хеширование напрямую сопоставляет ключи с записями на основе хэш-функции . [6]
Алгоритмы часто оцениваются по их вычислительной сложности или максимальному теоретическому времени выполнения. Например, функции двоичного поиска имеют максимальную сложность O (log n ) или логарифмическое время. Проще говоря, максимальное количество операций, необходимых для поиска цели поиска, является логарифмической функцией размера пространства поиска.
Конкретные применения алгоритмов поиска включают:
Алгоритмы поиска виртуальных пространств используются в задаче удовлетворения ограничений , где цель состоит в том, чтобы найти набор присвоений значений определенным переменным, который будет удовлетворять конкретным математическим уравнениям и неравенствам /равенствам. Они также используются, когда цель состоит в том, чтобы найти назначение переменных, которое максимизирует или минимизирует определенную функцию этих переменных. Алгоритмы решения этих задач включают базовый поиск методом грубой силы (также называемый «наивным» или «неинформированным» поиском) и различные эвристики , которые пытаются использовать частичные знания о структуре этого пространства, такие как линейная релаксация, генерация ограничений, и распространение ограничений .
Важным подклассом являются методы локального поиска , которые рассматривают элементы пространства поиска как вершины графа с ребрами, определяемыми набором эвристик, применимых к данному случаю; и сканировать пространство, переходя от элемента к элементу по краям, например по критерию наикрутейшего спуска или критерию best-first , или в стохастическом поиске . В эту категорию входит большое разнообразие общих метаэвристических методов, таких как имитация отжига , табу-поиск , A-команды и генетическое программирование , которые определенным образом комбинируют произвольные эвристики. Противоположностью локальному поиску будут методы глобального поиска. Этот метод применим, когда пространство поиска не ограничено и все аспекты данной сети доступны объекту, запускающему алгоритм поиска. [7]
Этот класс также включает в себя различные алгоритмы поиска по дереву , которые рассматривают элементы как вершины дерева и обходят это дерево в определенном порядке. Примеры последних включают в себя исчерпывающие методы, такие как поиск в глубину и поиск в ширину , а также различные эвристические методы обрезки дерева поиска , такие как возврат и ветвление и граница . В отличие от общей метаэвристики, которая в лучшем случае работает только в вероятностном смысле, многие из этих методов поиска по дереву гарантированно найдут точное или оптимальное решение, если уделить достаточно времени. Это называется « полнота ».
Другой важный подкласс составляют алгоритмы исследования дерева игр с несколькими игроками, таких как шахматы или нарды , узлы которых состоят из всех возможных игровых ситуаций, которые могут возникнуть в результате текущей ситуации. Целью этих задач является нахождение хода, обеспечивающего наилучшие шансы на победу, принимая во внимание все возможные ходы противника(ов). Подобные проблемы возникают, когда людям или машинам приходится принимать последовательные решения, результаты которых не полностью находятся под их контролем, например, при управлении роботами или при планировании маркетинговой , финансовой или военной стратегии. Такого рода задачи — комбинаторный поиск — широко изучаются в контексте искусственного интеллекта . Примерами алгоритмов этого класса являются минимаксный алгоритм , альфа-бета-обрезка , а также алгоритм A* и его варианты.
Название «комбинаторный поиск» обычно используется для алгоритмов, которые ищут определенную подструктуру данной дискретной структуры , например граф, строку , конечную группу и т. д. Термин комбинаторная оптимизация обычно используется, когда цель состоит в том, чтобы найти подструктуру с максимальным (или минимальным) значением некоторого параметра. (Поскольку подструктура обычно представляется в компьютере набором целочисленных переменных с ограничениями, эти проблемы можно рассматривать как частные случаи удовлетворения ограничений или дискретной оптимизации; но они обычно формулируются и решаются в более абстрактной постановке, где внутреннее представление явно не упоминается.)
Важным и широко изученным подклассом являются графовые алгоритмы , в частности алгоритмы обхода графа , для поиска конкретных подструктур в данном графе — таких как подграфы , пути , схемы и т. д. Примеры включают алгоритм Дейкстры , алгоритм Краскала , алгоритм ближайшего соседа и алгоритм Прима .
Другим важным подклассом этой категории являются алгоритмы поиска строк , которые ищут шаблоны внутри строк. Двумя известными примерами являются алгоритмы Бойера-Мура и Кнута-Морриса-Пратта , а также несколько алгоритмов, основанных на структуре данных суффиксного дерева .
В 1953 году американский статистик Джек Кифер разработал поиск Фибоначчи , который можно использовать для поиска максимума унимодальной функции и который имеет множество других приложений в информатике.
Существуют также методы поиска, разработанные для квантовых компьютеров , такие как алгоритм Гровера , которые теоретически быстрее, чем линейный поиск или поиск методом грубой силы, даже без помощи структур данных или эвристики. Хотя идеи и приложения, лежащие в основе квантовых компьютеров, все еще являются полностью теоретическими, исследования проводились с использованием алгоритмов, подобных алгоритму Гровера, которые точно воспроизводят гипотетические физические версии квантовых вычислительных систем. [8]
Категории: