Алгоритмы поиска: типы, классификация и эффективность.

Введение

Любой алгоритм, решающий поисковую задачу.

В информатике поисковый алгоритм — это алгоритм, разработанный для решения поисковой задачи. Поисковые алгоритмы работают для извлечения информации, хранящейся в определенной структуре данных или вычисленной в пространстве поиска предметной области, с дискретными или непрерывными значениями. Хотя поисковые системы используют поисковые алгоритмы, они относятся к области информационного поиска, а не алгоритмики. Выбор подходящего поискового алгоритма часто зависит от структуры данных, в которой производится поиск, и может учитывать предварительные знания о данных. Эффективность поисковых алгоритмов можно повысить за счет использования специально созданных структур баз данных, таких как деревья поиска, хеш-таблицы и индексы баз данных. Поисковые алгоритмы классифицируются на основе механизма поиска на три типа: линейный, бинарный и хеширование. Линейные алгоритмы поиска последовательно проверяют каждую запись на соответствие целевому ключу. Бинарные, или алгоритмы поиска с делением пополам, многократно определяют центр структуры поиска и делят пространство поиска на две части. Алгоритмы поиска сравнением улучшают линейный поиск, последовательно исключая записи на основе сравнения ключей до тех пор, пока не будет найдена целевая запись, и могут применяться к структурам данных с определенным порядком. Алгоритмы цифрового поиска работают на основе свойств цифр в структурах данных, используя числовые ключи. Наконец, хеширование напрямую сопоставляет ключи с записями на основе хеш-функции. Алгоритмы часто оцениваются по их вычислительной сложности, или максимальному теоретическому времени работы. Например, функции двоичного поиска имеют максимальную сложность O(log n), или логарифмическое время. Проще говоря, максимальное количество операций, необходимых для нахождения целевого элемента, является логарифмической функцией размера пространства поиска.

Для виртуальных поисковых пространств

Алгоритмы для поиска в виртуальных пространствах используются в задаче поиска решения при ограничениях, где целью является нахождение набора значений, присвоенных определенным переменным, удовлетворяющих заданным математическим уравнениям и неравенствам / равенствам. Они также применяются, когда необходимо найти такое присваивание переменных, которое максимизирует или минимизирует определенную функцию этих переменных. Алгоритмы для решения этих задач включают в себя базовый поиск полным перебором (также называемый «наивным» или «неинформированным» поиском) и различные эвристики, стремящиеся использовать частичные знания о структуре этого пространства, такие как линейная релаксация, генерация ограничений и распространение ограничений. Важным подклассом являются методы локального поиска, рассматривающие элементы пространства поиска как вершины графа, ребра которого определяются набором эвристик, применимых к конкретному случаю; они осуществляют сканирование пространства, перемещаясь от элемента к элементу по ребрам, например, в соответствии с методом наискорейшего спуска или критерием «лучший первый», либо в рамках стохастического поиска. Эта категория включает в себя большое разнообразие общих метаэвристических методов, таких как имитация отжига, табу-поиск, алгоритмы, основанные на командах, и генетическое программирование, которые комбинируют произвольные эвристики определенным образом. Противоположностью локального поиска являются методы глобального поиска. Этот метод применим, когда пространство поиска не ограничено и все аспекты рассматриваемой сети доступны сущности, выполняющей алгоритм поиска. Этот класс также включает в себя различные алгоритмы поиска по дереву, рассматривающие элементы как вершины дерева и осуществляющие обход этого дерева в определенном порядке. Примеры последних включают исчерпывающие методы, такие как поиск в глубину и поиск в ширину, а также различные эвристические методы обрезки дерева поиска, такие как возврат и метод ветвей и границ. В отличие от общих метаэвристик, которые в лучшем случае работают только в вероятностном смысле, многие из этих методов поиска по дереву гарантированно находят точное или оптимальное решение, если им выделено достаточно времени. Это называется «полнотой». Другой важный подкласс составляют алгоритмы для исследования игрового дерева многопользовательских игр, таких как шахматы или нарды, узлы которых представляют все возможные игровые ситуации, которые могут возникнуть из текущей ситуации. Целью в этих задачах является нахождение хода, обеспечивающего наилучшие шансы на победу, с учетом всех возможных ходов противников. Схожие проблемы возникают, когда люди или машины должны принимать последовательные решения, результаты которых не полностью под их контролем, например, при управлении роботами или при планировании маркетинговой, финансовой или военной стратегии. Этот вид задачи — комбинаторный поиск — широко изучался в контексте искусственного интеллекта. Примерами алгоритмов этого класса являются алгоритм минимакс, альфа-бета отсечение и алгоритм A* и его варианты.

Algorithms for searching virtual spaces are used in the constraint satisfaction problem, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical equations and inequations / equalities. They are also used when the goal is to find a variable assignment that will maximize or minimize a certain function of those variables. Algorithms for these problems include the basic brute force search (also called "naïve" or "uninformed" search), and a variety of heuristics that try to exploit partial knowledge about the structure of this space, such as linear relaxation, constraint generation, and constraint propagation. An important subclass are the local search methods, that view the elements of the search space as the vertices of a graph, with edges defined by a set of heuristics applicable to the case; and scan the space by moving from item to item along the edges, for example according to the steepest descent or best first criterion, or in a stochastic search. This category includes a great variety of general metaheuristic methods, such as simulated annealing, tabu search, A teams, and genetic programming, that combine arbitrary heuristics in specific ways. The opposite of local search would be global search methods. This method is applicable when the search space is not limited and all aspects of the given network are available to the entity running the search algorithm. This class also includes various tree search algorithms, that view the elements as vertices of a tree, and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as depth first search and breadth first search, as well as various heuristic based search tree pruning methods such as backtracking and branch and bound. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called "completeness". Another important sub class consists of algorithms for exploring the game tree of multiple player games, such as chess or backgammon, whose nodes consist of all possible game situations that could result from the current situation. The goal in these problems is to find the move that provides the best chance of a win, taking into account all possible moves of the opponent(s). Similar problems occur when humans or machines have to make successive decisions whose outcomes are not entirely under one's control, such as in robot guidance or in marketing, financial, or military strategy planning. This kind of problem — combinatorial search — has been extensively studied in the context of artificial intelligence. Examples of algorithms for this class are the minimax algorithm, alpha–beta pruning, and the A* algorithm and its variants.

Для подструктур данной структуры

Название "комбинаторный поиск" обычно используется для алгоритмов, которые ищут конкретную подструктуру заданной дискретной структуры, такой как граф, строка, конечная группа и так далее. Термин "комбинаторная оптимизация" обычно применяется, когда целью является нахождение подструктуры с максимальным (или минимальным) значением некоторого параметра. (Поскольку подструктура обычно представляется в компьютере набором целочисленных переменных с ограничениями, эти задачи можно рассматривать как частные случаи задач удовлетворения ограничений или дискретной оптимизации; однако они обычно формулируются и решаются в более абстрактном контексте, где внутреннее представление не указывается явно.) Важным и широко изученным подклассом являются алгоритмы на графах, в частности, алгоритмы обхода графов, предназначенные для поиска конкретных подструктур в заданном графе, таких как подграфы, пути, циклы и так далее. Примеры включают алгоритм Дейкстры, алгоритм Крускала, алгоритм ближайшего соседа и алгоритм Прима. Другим важным подклассом этой категории являются алгоритмы поиска строк, которые ищут шаблоны внутри строк. Два известных примера — алгоритмы Бойера — Мура и Кнута — Морриса — Пратта, а также несколько алгоритмов, основанных на структуре данных «дерево суффиксов».

Поиск максимума функции

В 1953 году американский статистик Джек Кифер разработал метод поиска Фибоначчи, который можно использовать для нахождения максимума унимодальной функции и имеет множество других применений в компьютерных науках.

Для квантовых компьютеров

Существуют также методы поиска, разработанные для квантовых компьютеров, такие как алгоритм Гровера, которые теоретически быстрее, чем линейный или полный перебор, даже без использования структур данных или эвристик. Несмотря на то, что идеи и области применения квантовых компьютеров пока остаются полностью теоретическими, исследования с алгоритмами вроде алгоритма Гровера позволяют точно моделировать гипотетические физические реализации квантовых вычислительных систем.