В информатике , А алгоритм поиска является алгоритмом ( как правило , с участием множества других, более конкретных алгоритмов [1] ) , который решает проблему поиска . Алгоритмы поиска работают для поиска информации, хранящейся в некоторой структуре данных или вычисленной в пространстве поиска проблемной области, либо с дискретными , либо с непрерывными значениями .
Хотя описанные выше проблемы поиска и веб-поиск являются проблемами при поиске информации, они обычно изучаются как отдельные подполя и решаются и оцениваются по-разному. Задачи веб-поиска обычно сосредоточены на фильтрации и поиске документов, наиболее релевантных запросам людей. Классические алгоритмы поиска обычно оцениваются по тому, насколько быстро они могут найти решение и гарантированно ли это решение будет оптимальным. Хотя алгоритмы поиска информации должны быть быстрыми, качество ранжирования , а также то, не учитываются ли хорошие результаты и включаются ли плохие результаты, является более важным.
Подходящий алгоритм поиска часто зависит от структуры данных, в которой выполняется поиск, и может также включать предварительные знания о данных. Некоторые структуры базы данных, такие как дерево поиска , хэш-карта или индекс базы данных, специально созданы для ускорения или повышения эффективности алгоритмов поиска . [2] [ требуется полная ссылка ] [3]
Алгоритмы поиска можно классифицировать по механизму поиска на 3 типа алгоритмов: линейный, двоичный и хеширующий. Алгоритмы линейного поиска проверяют каждую запись на предмет той, которая связана с целевым ключом, линейно. [4] Двоичный поиск или поиск с половинным интервалом многократно нацеливается на центр структуры поиска и делит пространство поиска пополам. Алгоритмы сравнительного поиска улучшают линейный поиск, последовательно удаляя записи на основе сравнений ключей до тех пор, пока целевая запись не будет найдена, и могут применяться к структурам данных в определенном порядке. [5] Алгоритмы цифрового поиска работают на основе свойств цифр в структурах данных, использующих цифровые ключи. [6] Наконец, хеширование напрямую сопоставляет ключи с записями на основе хеш-функции . [7]
Алгоритмы часто оцениваются по их вычислительной сложности или максимальному теоретическому времени выполнения. Например, функции двоичного поиска имеют максимальную сложность O (log n ) или логарифмическое время. Это означает, что максимальное количество операций, необходимых для поиска цели поиска, является логарифмической функцией размера области поиска.
Применение алгоритмов поиска
Конкретные применения алгоритмов поиска включают:
- Проблемы комбинаторной оптимизации , такие как:
- Проблема маршрута транспорта , форма задачи кратчайшего пути
- Задача о рюкзаке : учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, которое нужно включить в коллекцию, чтобы общий вес был меньше или равнялся заданному пределу, а общее значение было таким же большим. насколько возможно.
- Проблема расписания медсестры
- Проблемы с удовлетворением ограничений , такие как:
- Проблема раскраски карты
- Заполнение судоку или кроссворда
- В теории игр и особенно в комбинаторной теории игр выбор лучшего хода для следующего (например, с помощью алгоритма minmax )
- Поиск комбинации или пароля из всего набора возможностей
- Факторинг целого числа (важная проблема в криптографии )
- Оптимизация промышленного процесса, например химической реакции , путем изменения параметров процесса (например, температуры, давления и pH)
- Получение записи из базы данных
- Поиск максимального или минимального значения в списке или массиве
- Проверка, присутствует ли данное значение в наборе значений
Классы
Для виртуальных пространств поиска
Алгоритмы поиска виртуальных пространств используются в задаче удовлетворения ограничений , где цель состоит в том, чтобы найти набор присвоений значений определенным переменным, которые будут удовлетворять конкретным математическим уравнениям и неравенствам / равенствам. Они также используются, когда цель состоит в том, чтобы найти присвоение переменной, которое максимизирует или минимизирует определенную функцию этих переменных. Алгоритмы для этих проблем включают в себя базовый поиск методом перебора (также называемый «наивным» или «неинформированным» поиском) и различные эвристики, которые пытаются использовать частичные знания о структуре этого пространства, такие как линейная релаксация, создание ограничений, и распространение ограничений .
Важным подклассом являются методы локального поиска , которые рассматривают элементы пространства поиска как вершины графа с ребрами, определяемыми набором эвристик, применимых к данному случаю; и сканировать пространство, перемещаясь от элемента к элементу по краям, например, в соответствии с критерием наискорейшего спуска или наилучшим первым , или при стохастическом поиске . Эта категория включает большое количество общих метаэвристических методов, таких как моделирование отжига , поиск запретов , A-команды и генетическое программирование , которые комбинируют произвольные эвристики определенным образом. Противоположностью локальному поиску будут методы глобального поиска. Этот метод применим, когда пространство поиска не ограничено и все аспекты данной сети доступны для объекта, выполняющего алгоритм поиска. [8]
Этот класс также включает в себя различные алгоритмы поиска по дереву , которые рассматривают элементы как вершины дерева и обходят это дерево в определенном порядке. Примеры последних включают в себя исчерпывающие методы , такие как поиска в глубину и поиск в ширину , а также различных эвристической на основе дерева поиска обрезка методов , таких как возвратов и ветвей и границ . В отличие от общей метаэвристики, которая в лучшем случае работает только в вероятностном смысле, многие из этих методов поиска по дереву гарантированно найдут точное или оптимальное решение, если им будет уделено достаточно времени. Это называется « полнота ».
Другой важный подкласс состоит из алгоритмов для исследования дерева игр для многопользовательских игр, таких как шахматы или нарды , узлы которых состоят из всех возможных игровых ситуаций, которые могут возникнуть в текущей ситуации. Цель этих задач - найти ход, обеспечивающий наилучшие шансы на победу с учетом всех возможных ходов соперника (ов). Подобные проблемы возникают, когда люди или машины должны принимать последовательные решения, результаты которых не полностью находятся под их контролем, например, в руководстве роботом или в маркетинговом , финансовом или военном стратегическом планировании. Такого рода проблемы - комбинаторный поиск - широко изучались в контексте искусственного интеллекта . Примерами алгоритмов для этого класса являются минимаксный алгоритм , альфа-бета-отсечение , а также алгоритм A * и его варианты.
Для подконструкций данной конструкции
Название «комбинаторный поиск» обычно используется для алгоритмов, которые ищут определенную подструктуру данной дискретной структуры , например граф, строку , конечную группу и т. Д. Термин комбинаторная оптимизация обычно используется, когда цель состоит в том, чтобы найти подструктуру с максимальным (или минимальным) значением некоторого параметра. (Поскольку подструктура обычно представлена в компьютере набором целочисленных переменных с ограничениями, эти проблемы можно рассматривать как частные случаи удовлетворения ограничений или дискретной оптимизации; но они обычно формулируются и решаются в более абстрактной обстановке, где внутреннее представление явно не упоминается.)
Важным и широко изученным подклассом являются алгоритмы графа , в частности алгоритмы обхода графа , для поиска определенных подструктур в данном графе, таких как подграфы , пути , схемы и т. Д. Примеры включают в себя алгоритм Дейкстры , алгоритм Крускала , в ближайший алгоритм соседа , и алгоритм Прима .
Другой важный подкласс этой категории - алгоритмы поиска строк , которые ищут шаблоны в строках. Двумя известными примерами являются алгоритмы Бойера – Мура и Кнута – Морриса – Пратта , а также несколько алгоритмов, основанных на структуре данных суффиксного дерева .
Поиск максимума функции
В 1953 году американский статистик Джек Кифер изобрел поиск Фибоначчи, который можно использовать для нахождения максимума унимодальной функции и найти множество других приложений в компьютерных науках.
Для квантовых компьютеров
Существуют также методы поиска, разработанные для квантовых компьютеров , такие как алгоритм Гровера , которые теоретически быстрее, чем линейный поиск или поиск методом перебора, даже без помощи структур данных или эвристики. Хотя идеи и приложения, лежащие в основе квантовых компьютеров, все еще полностью теоретические, были проведены исследования с такими алгоритмами, как алгоритм Гровера, которые точно воспроизводят гипотетические физические версии квантовых вычислительных систем. [9]
Поисковая оптимизация
Алгоритмы поиска, используемые в такой поисковой системе, как Google, упорядочивают релевантные результаты поиска на основе множества важных факторов. [10] Поисковая оптимизация (SEO) - это процесс, в котором любой конкретный результат поиска будет работать вместе с поисковым алгоритмом, чтобы естественным образом привлечь больше внимания, внимания и кликов к своему сайту. Это может доходить до попытки настроить алгоритм поисковых систем так, чтобы он более отдавал предпочтение конкретному результату поиска, но стратегия, основанная на SEO, стала невероятно важной и актуальной в деловом мире. [10]
Смотрите также
- Обратная индукция
- Аппаратное обеспечение памяти с адресацией по содержимому
- Двухфазная эволюция - процесс, который стимулирует самоорганизацию в сложных адаптивных системах.
- Задача линейного поиска
- Никакого бесплатного обеда в поиске и оптимизации - Стоимость решения, усредненная по всем задачам в классе, одинакова для любого метода решения.
- Рекомендательная система - система фильтрации информации для прогнозирования предпочтений пользователей, а также использование статистических методов для ранжирования результатов в очень больших наборах данных.
- Поисковая система (вычисления)
- Поисковая игра - игра для двух человек с нулевой суммой
- Алгоритм выбора
- Решатель
- Алгоритм сортировки - алгоритм, который упорядочивает списки по порядку, необходимый для выполнения определенных алгоритмов поиска.
- Поисковая система в Интернете
Категории:
- Категория: Алгоритмы поиска
Рекомендации
Цитаты
- ↑ Дэвис, Дэйв (25 мая 2020 г.). «Как работают алгоритмы поисковых систем: все, что вам нужно знать» . Журнал поисковых систем . Проверено 27 марта 2021 года .
- ^ Beame & Fich 2002 , стр. 39.
- ^ Knuth 1998 , §6.5 («Поиск вторичных ключей»).
- ^ Knuth 1998 , §6.1 («Последовательный поиск»).
- ^ Knuth 1998 , §6.2 («Поиск путем сравнения ключей»).
- ^ Knuth 1998 , §6.3 (Цифровой поиск).
- ^ Knuth 1998 , §6.4, (Хеширование).
- ^ Хантер, AH; Пиппенгер, Николас (4 июля 2013 г.). «Локальный поиск в сравнении с глобальным поиском в графиках каналов». Сети: международное путешествие .
- ^ López, GV; Горин, Т; Лара, Л. (26 февраля 2008 г.). "Моделирование алгоритма квантового поиска Гровера в квантовом компьютере изинговской ядерной спиновой цепочки с взаимодействиями первого и второго ближайших соседей". Журнал физики B: атомная, молекулярная и оптическая физика . 41 (5): 055504. arXiv : 0710.3196 . Bibcode : 2008JPhB ... 41e5504L . DOI : 10.1088 / 0953-4075 / 41/5/055504 . S2CID 18796310 .
- ^ а б Бай, Майкл; Де лос Сантос, Барбур; Wildenbeest, Matthijs (2016). «Поисковая оптимизация: что движет органическим трафиком на сайты розничной торговли?». Журнал экономики и стратегии управления . 25 : 6–31. DOI : 10.1111 / jems.12141 . S2CID 156960693 .
Библиография
Книги
- Кнут, Дональд (1998). Сортировка и поиск . Искусство программирования . 3 (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли Профессионал.
Статьи
- Шмитту, Томас; Шмитту, Фейт Э. (1 августа 2002 г.). «Оптимальные границы для проблемы предшественника и связанных с ней проблем» . Журнал компьютерных и системных наук . 65 (1): 38–72. DOI : 10,1006 / jcss.2002.1822 .
Внешние ссылки
- Неинформированный поисковый проект в Викиверситете .