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

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

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

Эта статья нуждается в дополнительных ссылках для проверки . Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Неисходный материал может быть оспорен и удален.
Поиск источников: «Алгоритм поиска» — новости · газеты · книги · ученый · JSTOR ( апрель 2016 г. ) ( узнайте, как и когда удалить это шаблонное сообщение )

( Узнайте, как и когда удалить это шаблонное сообщение )

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

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

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

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

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

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

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

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

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

Классы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Категории:

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

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

Цитаты

^ Дэвис, Дэйв (25 мая 2020 г.). «Как работают алгоритмы поисковых систем: все, что вам нужно знать» . Журнал поисковой системы . Проверено 27 марта 2021 г.{{cite web}}: CS1 maint: URL-статус ( ссылка )
^ Бим и Фич 2002 , с. 39.
^ Кнут 1998 , §6.5 («Поиск по вторичным ключам»).
^ Кнут 1998 , §6.1 («Последовательный поиск»).
^ Кнут 1998 , §6.2 («Поиск путем сравнения ключей»).
^ Кнут 1998 , §6.3 (Цифровой поиск).
^ Кнут 1998 , §6.4, (Хеширование).
^ Хантер, А.Х.; Пиппенджер, Николас (4 июля 2013 г.). «Локальный и глобальный поиск в графиках каналов». Сети: международное путешествие . архив : 1004.2526 .
^ Лопес, Г.В.; Горин, Т; Лара, Л. (26 февраля 2008 г.). «Моделирование алгоритма квантового поиска Гровера в квантовом компьютере с ядерной спиновой цепью Изинга со связями первого и второго ближайших соседей». Журнал физики B: атомная, молекулярная и оптическая физика . 41 (5): 055504. arXiv : 0710.3196 . Бибкод : 2008JPhB...41e5504L . doi : 10.1088/0953-4075/41/5/055504 . S2CID 18796310 .
^ б Бай , Майкл; Де лос Сантос, Барбур; Гну, Маттейс (2016). «Поисковая оптимизация: что привлекает органический трафик на сайты розничной торговли?». Журнал экономики и стратегии управления . 25 : 6–31. doi : 10.1111/jems.12141 . S2CID 156960693 .

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

Книги

Кнут, Дональд (1998). Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Рединг, Массачусетс: Addison-Wesley Professional.

Статьи

Шмиттоу, Томас; Шмиттоу, Фейт Э. (01.08.2002). «Оптимальные оценки для проблемы предшественника и связанных с ней проблем» . Журнал компьютерных и системных наук . 65 (1): 38–72. doi : 10.1006/jcss.2002.1822 .

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

Неинформированный поисковый проект в Викиверситете .

[1] Дэвис, Дэйв (25 мая 2020 г.). «Как работают алгоритмы поисковых систем: все, что вам нужно знать» . Журнал поисковой системы . Проверено 27 марта 2021 г.{{cite web}}: CS1 maint: URL-статус ( ссылка )

[FOOTNOTEBeameFich200239-2] Бим и Фич 2002 , с. 39.

[FOOTNOTEKnuth1998§6.5_("Retrieval_on_Secondary_Keys")-3] Кнут 1998 , §6.5 («Поиск по вторичным ключам»).

[FOOTNOTEKnuth1998§6.1_("Sequential_Searching")-4] Кнут 1998 , §6.1 («Последовательный поиск»).

[FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_of_Keys")-5] Кнут 1998 , §6.2 («Поиск путем сравнения ключей»).

[FOOTNOTEKnuth1998§6.3_(Digital_Searching)-6] Кнут 1998 , §6.3 (Цифровой поиск).

[FOOTNOTEKnuth1998§6.4,_(Hashing)-7] Кнут 1998 , §6.4, (Хеширование).

[8] Хантер, А.Х.; Пиппенджер, Николас (4 июля 2013 г.). «Локальный и глобальный поиск в графиках каналов». Сети: международное путешествие . архив : 1004.2526 .

[9] Лопес, Г.В.; Горин, Т; Лара, Л. (26 февраля 2008 г.). «Моделирование алгоритма квантового поиска Гровера в квантовом компьютере с ядерной спиновой цепью Изинга со связями первого и второго ближайших соседей». Журнал физики B: атомная, молекулярная и оптическая физика . 41 (5): 055504. arXiv : 0710.3196 . Бибкод : 2008JPhB...41e5504L . doi : 10.1088/0953-4075/41/5/055504 . S2CID 18796310 .

[:0-10] б Бай , Майкл; Де лос Сантос, Барбур; Гну, Маттейс (2016). «Поисковая оптимизация: что привлекает органический трафик на сайты розничной торговли?». Журнал экономики и стратегии управления . 25 : 6–31. doi : 10.1111/jems.12141 . S2CID 156960693 .

[1]