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

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

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

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

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

Приложения алгоритмов поиска Алгоритмы поиска, в частности, используются в таких задачах, как:

Задачи комбинаторной оптимизации, например: , вид задачи о кратчайшем пути Задача о рюкзаке: Определение количества каждого предмета из заданного набора, имеющего вес и ценность, для включения в коллекцию таким образом, чтобы общий вес не превышал установленного лимита, а общая ценность была максимально возможной.

Задачи удовлетворения ограничений, такие как: Теорема о четырёх красках Заполнение судоку или кроссворда В теории игр и, в частности, в комбинаторной теории игр, выбор наилучшего хода (например, алгоритм минимакса) Поиск комбинации или пароля из всего набора возможностей Разложение целого числа на множители (важная задача в криптографии) Оптимизация поисковой системы и оптимизация контента для поисковых роботов Оптимизация индустриальных процессов, таких как химическая реакция, путём изменения параметров процесса (температуры, давления, pH) Извлечение записи из базы данных Нахождение максимального или минимального значения в списке или массиве Проверка присутствия заданного значения в наборе значений

Классы

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

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

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

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

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

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

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

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

См. также Обратная индукция — процесс рассуждения в обратном порядке Ассоциативная память — тип аппаратной компьютерной памяти  — процесс, управляющий самоорганизацией в сложных адаптивных системах Задача линейного поиска на прямой — задача поиска Теорема «Бесплатных обедов не бывает» в поиске и оптимизации — средняя стоимость решения одинакова для любого метода. Рекомендательная система — система для прогнозирования предпочтений пользователей, также использующая статистические методы для ранжирования результатов в очень больших наборах данных. Поисковая машина — системы помощи поиска информации Игра на поиск — игра двух лиц с нулевой суммой Алгоритм выбора — метод нахождения k-го наименьшего значения  — программное обеспечение для класса математических задач Алгоритм сортировки — алгоритм, упорядочивающий списки, необходимый для выполнения некоторых алгоритмов поиска Поисковая система — программная система для поиска релевантной информации в Интернете.

Примечания

Литература Книги

Статьи

Категория:Алгоритмы интернет-поиска Категория:Функции ранжирования Категория:Алгоритмы поиска