bugorwiki.info
на главную

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

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

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

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

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

Классы

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

Смотри также: Солвер

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

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

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

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

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

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

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

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

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

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

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

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


просмотров: 17