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

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

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

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

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

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

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

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

  • Проблемы комбинаторной оптимизации , такие как:
    • Проблема маршрута транспортного средства , форма задачи кратчайшего пути
    • Задача о рюкзаке : учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, которое нужно включить в коллекцию, чтобы общий вес был меньше или равнялся заданному пределу, а общее значение было таким же большим. насколько возможно.
    • Проблема расписания медсестры
  • Проблемы с удовлетворением ограничений , такие как:
    • Проблема раскраски карты
    • Заполнение судоку или кроссворда
  • В теории игр и особенно в комбинаторной теории игр выбор лучшего хода для следующего (например, с помощью алгоритма minmax )
  • Поиск комбинации или пароля из всего набора возможностей
  • Факторинг целого числа (важная проблема в криптографии )
  • Оптимизация промышленного процесса, например химической реакции , путем изменения параметров процесса (например, температуры, давления и pH)
  • Получение записи из базы данных
  • Поиск максимального или минимального значения в списке или массиве
  • Проверка, присутствует ли данное значение в наборе значений

Классы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Обратная индукция
  • Аппаратное обеспечение памяти с адресацией по содержимому
  • Двухфазная эволюция  - процесс, который стимулирует самоорганизацию в сложных адаптивных системах.
  • Задача линейного поиска
  • Никакого бесплатного обеда в поиске и оптимизации  - Стоимость решения, усредненная по всем задачам в классе, одинакова для любого метода решения.
  • Рекомендательная система  - система фильтрации информации для прогнозирования предпочтений пользователей, а также использование статистических методов для ранжирования результатов в очень больших наборах данных.
  • Поисковая система (вычисление)  - Система, помогающая в поиске информации.
  • Поисковая игра  - игра для двух человек с нулевой суммой
  • Алгоритм выбора
  • Решатель
  • Алгоритм сортировки  - алгоритм, который упорядочивает списки по порядку, необходимый для выполнения определенных алгоритмов поиска.
  • Поисковая система в Интернете

Категории:

  • Категория: Алгоритмы поиска

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

Цитаты

  1. ↑ Дэвис, Дэйв (25 мая 2020 г.). «Как работают алгоритмы поисковых систем: все, что вам нужно знать» . Журнал поисковых систем . Проверено 27 марта 2021 года .
  2. ^ Beame & Fich 2002 , стр. 39.
  3. ^ Knuth 1998 , §6.5 («Поиск вторичных ключей»).
  4. ^ Knuth 1998 , §6.1 («Последовательный поиск»).
  5. ^ Knuth 1998 , §6.2 («Поиск путем сравнения ключей»).
  6. ^ Knuth 1998 , §6.3 (Цифровой поиск).
  7. ^ Knuth 1998 , §6.4, (Хеширование).
  8. ^ Хантер, AH; Пиппенгер, Николас (4 июля 2013 г.). «Локальный поиск в сравнении с глобальным поиском в графиках каналов». Сети: международное путешествие . arXiv : 1004,2526 .
  9. ^ Лопес, GV; Горин, Т; Лара, Л. (26 февраля 2008 г.). "Моделирование алгоритма квантового поиска Гровера в квантовом компьютере изинговской ядерной спиновой цепочки с взаимодействиями первого и второго ближайших соседей". Журнал физики B: атомная, молекулярная и оптическая физика . 41 (5): 055504. arXiv : 0710.3196 . Bibcode : 2008JPhB ... 41e5504L . DOI : 10.1088 / 0953-4075 / 41/5/055504 . S2CID 18796310 . 
  10. ^ a b Бай, Майкл; Де лос Сантос, Барбур; 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 .

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

  • Неинформированный поисковый проект в Викиверситете .
Получено с https://en.wikipedia.org/w/index.php?title=Search_algorithm&oldid=1049145670#Informed_search "
Contribute a better translation