 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
В информатике , А алгоритм поиска является любой алгоритм , который решает задачу поиска , а именно, для получения информации , хранящейся в пределах некоторой структуры данных, или рассчитываются в пространстве поиска в проблемной области, либо с дискретным или непрерывным значениями . Конкретные применения алгоритмов поиска включают:
- Проблемы комбинаторной оптимизации , такие как:
- Проблема маршрута транспорта , форма задачи кратчайшего пути
- Задача о рюкзаке : учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, который нужно включить в коллекцию, чтобы общий вес был меньше или равнялся заданному пределу, а общее значение было таким же большим. насколько возможно.
- Проблема расписания медсестры
- Проблемы с удовлетворением ограничений , такие как:
- Проблема раскраски карты
- Заполнение судоку или кроссворда
- В теории игр и особенно в комбинаторной теории игр выбор лучшего хода для следующего (например, с помощью алгоритма minmax )
- Поиск комбинации или пароля из всего набора возможностей
- Факторинг целого числа (важная проблема в криптографии )
- Оптимизация промышленного процесса, например химической реакции , путем изменения параметров процесса (например, температуры, давления и pH)
- Получение записи из базы данных
- Поиск максимального или минимального значения в списке или массиве
- Проверка, присутствует ли данное значение в наборе значений
Классические задачи поиска, описанные выше, и веб-поиск являются проблемами при поиске информации , но обычно изучаются как отдельные подполя и решаются и оцениваются по-разному. Задачи веб-поиска обычно сосредоточены на фильтрации и поиске документов, наиболее релевантных человеческим запросам. Классические алгоритмы поиска обычно оцениваются по тому, насколько быстро они могут найти решение и гарантированно ли это решение будет оптимальным. Хотя алгоритмы поиска информации должны быть быстрыми, качество ранжирования более важно, а также то, были ли упущены хорошие результаты и включены ли плохие результаты.
Подходящий алгоритм поиска часто зависит от структуры данных, в которой выполняется поиск, и может также включать предварительные знания о данных. Некоторые структуры базы данных, такие как дерево поиска , хэш-карта или индекс базы данных, специально созданы для ускорения или повышения эффективности алгоритмов поиска . [1] [2]
Алгоритмы поиска можно классифицировать на основе их механизма поиска. Алгоритмы линейного поиска проверяют каждую запись на предмет той, которая связана с целевым ключом, линейно. [3] Двоичный поиск или поиск с половинным интервалом многократно нацеливается на центр структуры поиска и делит пространство поиска пополам. Алгоритмы сравнительного поиска улучшают линейный поиск, последовательно удаляя записи на основе сравнений ключей до тех пор, пока целевая запись не будет найдена, и могут применяться к структурам данных в определенном порядке. [4] Алгоритмы цифрового поиска работают на основе свойств цифр в структурах данных, использующих цифровые ключи. [5] Наконец, хеширование напрямую сопоставляет ключи с записями на основехэш-функция . [6] Для поиска вне линейного поиска требуется, чтобы данные были каким-то образом отсортированы.
Алгоритмы часто оцениваются по их вычислительной сложности или максимальному теоретическому времени выполнения. Например, функции двоичного поиска имеют максимальную сложность O (log n ) или логарифмическое время. Это означает, что максимальное количество операций, необходимых для поиска цели поиска, является логарифмической функцией размера области поиска.
Классы [ править ]
Для виртуальных пространств поиска [ править ]
Алгоритмы поиска виртуальных пространств используются в задаче удовлетворения ограничений , где цель состоит в том, чтобы найти набор присвоений значений определенным переменным, которые будут удовлетворять конкретным математическим уравнениям и неравенствам / равенствам. Они также используются, когда цель состоит в том, чтобы найти присвоение переменной, которое максимизирует или минимизирует определенную функцию этих переменных. Алгоритмы для этих проблем включают в себя базовый поиск методом перебора (также называемый «наивным» или «неинформированным» поиском) и различные эвристики, которые пытаются использовать частичные знания о структуре этого пространства, такие как линейная релаксация, создание ограничений, и распространение ограничений.
Важным подклассом являются методы локального поиска , которые рассматривают элементы пространства поиска как вершины графа с ребрами, определяемыми набором эвристик, применимых к данному случаю; и сканировать пространство, перемещаясь от элемента к элементу по краям, например, в соответствии с критерием наискорейшего спуска или наилучшим первым , или при стохастическом поиске . Эта категория включает большое количество общих метаэвристических методов, таких как моделирование отжига , поиск запретов , A-команды и генетическое программирование , которые комбинируют произвольные эвристики определенным образом.
Этот класс также включает в себя различные алгоритмы поиска по дереву , которые рассматривают элементы как вершины дерева и обходят это дерево в определенном порядке. Примеры последних включают в себя исчерпывающие методы , такие как поиска в глубину и поиск в ширину , а также различных эвристической на основе дерева поиска обрезка методов , таких как возвратов и ветвей и границ . В отличие от общей метаэвристики, которая в лучшем случае работает только в вероятностном смысле, многие из этих методов поиска по дереву гарантированно найдут точное или оптимальное решение, если им будет уделено достаточно времени. Это называется « полнота ».
Другой важный подкласс состоит из алгоритмов для исследования дерева игр для многопользовательских игр, таких как шахматы или нарды , узлы которых состоят из всех возможных игровых ситуаций, которые могут возникнуть в текущей ситуации. Цель этих задач - найти ход, обеспечивающий наилучшие шансы на победу с учетом всех возможных ходов соперника (ов). Подобные проблемы возникают, когда люди или машины должны принимать последовательные решения, результаты которых не полностью находятся под их контролем, например, в руководстве роботом или в маркетинговом , финансовом или военном стратегическом планировании. Такого рода задача - комбинаторный поиск- был широко изучен в контексте искусственного интеллекта . Примерами алгоритмов для этого класса являются минимаксный алгоритм , альфа-бета-отсечение , а также алгоритм A * и его варианты.
Для подструктур данной структуры [ править ]
Название «комбинаторный поиск» обычно используется для алгоритмов, которые ищут определенную подструктуру данной дискретной структуры , например граф, строку , конечную группу и т. Д. Термин комбинаторная оптимизация обычно используется, когда цель состоит в том, чтобы найти подструктуру с максимальным (или минимальным) значением некоторого параметра. (Поскольку подструктура обычно представлена в компьютере набором целочисленных переменных с ограничениями, эти проблемы можно рассматривать как частные случаи удовлетворения ограничений или дискретной оптимизации; но они обычно формулируются и решаются в более абстрактной обстановке, где внутреннее представление явно не упоминается.)
Важным и широко изученным подклассом являются алгоритмы графа , в частности алгоритмы обхода графа , для поиска определенных подструктур в данном графе, таких как подграфы , пути , схемы и т. Д. Примеры включают в себя алгоритм Дейкстры , алгоритм Крускала , в ближайший алгоритм соседа , и алгоритм Прима .
Другой важный подкласс этой категории - алгоритмы поиска строк , которые ищут шаблоны в строках. Двумя известными примерами являются алгоритмы Бойера – Мура и Кнута – Морриса – Пратта , а также несколько алгоритмов, основанных на структуре данных суффиксного дерева .
Найдите максимум функции [ править ]
В 1953 году американский статистик Джек Кифер изобрел поиск Фибоначчи, который можно использовать для нахождения максимума унимодальной функции и найти множество других приложений в компьютерных науках.
Для квантовых компьютеров [ править ]
Существуют также методы поиска, разработанные для квантовых компьютеров , такие как алгоритм Гровера , которые теоретически быстрее, чем линейный поиск или поиск методом перебора, даже без помощи структур данных или эвристики.
См. Также [ править ]
- Обратная индукция
- Аппаратное обеспечение памяти с адресацией по содержимому
- Двухфазная эволюция - процесс, который стимулирует самоорганизацию в сложных адаптивных системах.
- Задача линейного поиска
- Никакого бесплатного обеда в поиске и оптимизации - Стоимость решения, усредненная по всем задачам в классе, одинакова для любого метода решения.
- Рекомендательная система - система фильтрации информации для прогнозирования предпочтений пользователей, а также использование статистических методов для ранжирования результатов в очень больших наборах данных.
- Поисковая система (вычисления)
- Поисковая игра - игра для двух человек с нулевой суммой
- Алгоритм выбора
- Решатель
- Алгоритм сортировки - алгоритм, который упорядочивает списки по порядку, необходимый для выполнения определенных алгоритмов поиска.
- Поисковая система в Интернете
Категории:
- Категория: Поисковые алгоритмы
Ссылки [ править ]
Цитаты [ править ]
- ^ Beame & Fich 2002 , стр. 39.
- ^ Knuth 1998 , §6.5 («Поиск вторичных ключей»).
- ^ Knuth 1998 , §6.1 («Последовательный поиск»).
- ^ Knuth 1998 , §6.2 («Поиск путем сравнения ключей»).
- ^ Knuth 1998 , §6.3 (Цифровой поиск).
- ^ Knuth 1998 , §6.4, (Хеширование).
Библиография [ править ]
Книги [ править ]
- Кнут, Дональд (1998). Сортировка и поиск . Искусство программирования . 3 (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли Профессионал.CS1 maint: ref=harv (link)
Статьи [ править ]
- Шмитту, Томас; Шмитту, Фейт Э. (1 августа 2002 г.). «Оптимальные границы для проблемы предшественника и связанных с ней проблем» . Журнал компьютерных и системных наук . 65 (1): 38–72. DOI : 10,1006 / jcss.2002.1822 .
Внешние ссылки [ править ]
- Неинформированный поисковый проект в Викиверситете .
