Jump to content

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

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

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

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

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

См. также

[ редактировать ]

Категории:

  1. ^ Beame & Fich 2002 , с. 39.
  2. ^ Кнут 1998 , §6.5 («Поиск по вторичным ключам»).
  3. ^ Кнут 1998 , §6.1 («Последовательный поиск»).
  4. ^ Кнут 1998 , §6.2 («Поиск путем сравнения ключей»).
  5. ^ Кнут 1998 , §6.3 (Цифровой поиск).
  6. ^ Кнут 1998 , §6.4, (Хеширование).
  7. ^ Хантер, АХ; Пиппенджер, Николас (4 июля 2013 г.). «Локальный и глобальный поиск в графах каналов». Сети: международное путешествие . arXiv : 1004.2526 .
  8. ^ Лопес, Г.В.; Горин, Т; Лара, Л. (26 февраля 2008 г.). «Моделирование алгоритма квантового поиска Гровера в квантовом компьютере Изинга с ядерной спиновой цепочкой и связями первого и второго ближайших соседей». Журнал физики B: атомная, молекулярная и оптическая физика . 41 (5): 055504. arXiv : 0710.3196 . Бибкод : 2008JPhB...41e5504L . дои : 10.1088/0953-4075/41/5/055504 . S2CID   18796310 .

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 5e9321973bed37e7f8364bb0043fcf94__1720499700
URL1:https://arc.ask3.ru/arc/aa/5e/94/5e9321973bed37e7f8364bb0043fcf94.html
Заголовок, (Title) документа по адресу, URL1:
Search algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)