Алгоритм поиска - Search algorithm

Визуальное представление хеш-таблицы , структуры данных, которая позволяет быстро извлекать информацию.

В информатике , А алгоритм поиска является алгоритм ( как правило , с участием множества других, более конкретных алгоритмов) , который решает проблему поиска . Алгоритмы поиска работают для извлечения информации, хранящейся в некоторой структуре данных или вычисленной в пространстве поиска проблемной области, либо с дискретными , либо с непрерывными значениями .

Хотя описанные выше проблемы поиска и веб-поиск являются проблемами при поиске информации, они обычно изучаются как отдельные подполя и решаются и оцениваются по-разному. Задачи веб-поиска обычно сосредоточены на фильтрации и поиске документов, наиболее релевантных человеческим запросам. Классические алгоритмы поиска обычно оцениваются по тому, насколько быстро они могут найти решение и гарантированно ли это решение будет оптимальным. Хотя алгоритмы поиска информации должны быть быстрыми, качество ранжирования , а также то, не учитываются ли хорошие результаты и включаются ли плохие результаты, является более важным.

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

Алгоритмы поиска можно классифицировать по механизму поиска на 3 типа алгоритмов: линейный, двоичный и хеширующий. Алгоритмы линейного поиска проверяют каждую запись на предмет той, которая связана с целевым ключом, линейно. Двоичный поиск или поиск с половинным интервалом неоднократно нацеливается на центр структуры поиска и делит пространство поиска пополам. Алгоритмы сравнительного поиска улучшают линейный поиск за счет последовательного исключения записей на основе сравнения ключей до тех пор, пока целевая запись не будет найдена, и могут применяться к структурам данных в определенном порядке. Алгоритмы цифрового поиска работают на основе свойств цифр в структурах данных, использующих цифровые ключи. Наконец, хеширование напрямую сопоставляет ключи с записями на основе хеш-функции .

Алгоритмы часто оцениваются по их вычислительной сложности или максимальному теоретическому времени выполнения. Например, функции двоичного поиска имеют максимальную сложность O (log n ) или логарифмическое время. Это означает, что максимальное количество операций, необходимых для поиска цели поиска, является логарифмической функцией размера области поиска.

Применение алгоритмов поиска

Конкретные применения алгоритмов поиска включают:

Классы

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

См. Также: Решатель

Алгоритмы поиска виртуальных пространств используются в задаче удовлетворения ограничений , где цель состоит в том, чтобы найти набор присвоений значений определенным переменным, которые будут удовлетворять конкретным математическим уравнениям и неравенствам / равенствам. Они также используются, когда цель состоит в том, чтобы найти присвоение переменной, которое максимизирует или минимизирует определенную функцию этих переменных. Алгоритмы решения этих проблем включают в себя базовый поиск методом перебора (также называемый «наивным» или «неинформированным» поиском) и различные эвристики, которые пытаются использовать частичные знания о структуре этого пространства, такие как линейная релаксация, создание ограничений и т. Д. и распространение ограничений .

Важным подклассом являются методы локального поиска , которые рассматривают элементы пространства поиска как вершины графа с ребрами, определяемыми набором эвристик, применимых к данному случаю; и сканировать пространство, перемещаясь от элемента к элементу по краям, например, в соответствии с критерием наискорейшего спуска или наилучшим первым , или при стохастическом поиске . Эта категория включает большое количество общих метаэвристических методов, таких как имитация отжига , поиск запретов , A-команды и генетическое программирование , которые комбинируют произвольные эвристики определенным образом. Противоположностью локальному поиску будут методы глобального поиска. Этот метод применим, когда пространство поиска не ограничено и все аспекты данной сети доступны для объекта, выполняющего алгоритм поиска.

Этот класс также включает в себя различные алгоритмы поиска по дереву , которые рассматривают элементы как вершины дерева и обходят это дерево в определенном порядке. Примеры последних включают в себя исчерпывающие методы , такие как поиска в глубину и поиск в ширину , а также различных эвристической на основе дерева поиска обрезка методов , таких как возвратов и ветвей и границ . В отличие от общей метаэвристики, которая в лучшем случае работает только в вероятностном смысле, многие из этих методов поиска по дереву гарантированно найдут точное или оптимальное решение, если им будет уделено достаточно времени. Это называется « полнота ».

Другой важный подкласс состоит из алгоритмов для исследования дерева игр для многопользовательских игр, таких как шахматы или нарды , узлы которых состоят из всех возможных игровых ситуаций, которые могут возникнуть в текущей ситуации. Цель этих задач - найти ход, обеспечивающий наилучшие шансы на победу, с учетом всех возможных ходов соперника (ов). Подобные проблемы возникают, когда людям или машинам приходится принимать последовательные решения, результаты которых не полностью находятся под их контролем, например, при управлении роботами или при планировании маркетинговой , финансовой или военной стратегии. Проблема такого рода - комбинаторный поиск - широко изучалась в контексте искусственного интеллекта . Примерами алгоритмов для этого класса являются минимаксный алгоритм , альфа – бета отсечение , а также алгоритм A * и его варианты.

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

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

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

Другой важный подкласс этой категории - алгоритмы поиска строк , которые ищут шаблоны в строках. Двумя известными примерами являются алгоритмы Бойера – Мура и Кнута – Морриса – Пратта , а также несколько алгоритмов, основанных на структуре данных суффиксного дерева .

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

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

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

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

Поисковая оптимизация

Алгоритмы поиска, используемые в такой поисковой системе, как Google, упорядочивают релевантные результаты поиска на основе множества важных факторов. Поисковая оптимизация (SEO) - это процесс, в котором любой конкретный результат поиска будет работать вместе с поисковым алгоритмом, чтобы естественным образом привлечь больше внимания, внимания и кликов к своему сайту. Это может доходить до попытки настроить алгоритм поисковых систем так, чтобы он более отдавал предпочтение конкретному результату поиска, но стратегия, основанная на SEO, стала невероятно важной и актуальной в деловом мире.

Смотрите также

Категории:

использованная литература

Цитаты

Библиография

Книги

Статьи

внешние ссылки