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

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

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

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

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

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

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

Классы

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

Смотрите также: Решатель

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

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

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

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

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

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

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

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

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

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

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

Также существуют методы поиска, предназначенные для квантовые компьютеры, подобно Алгоритм Гровера, которые теоретически быстрее, чем линейный поиск или перебор, даже без помощи структур данных или эвристики.

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

Категории:

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

Рекомендации

Цитаты

  1. ^ Бим и Фич 2002, п. 39.
  2. ^ Кнут 1998, §6.5 («Получение дополнительных ключей»).
  3. ^ Кнут 1998, §6.1 («Последовательный поиск»).
  4. ^ Кнут 1998, §6.2 («Поиск по сравнению ключей»).
  5. ^ Кнут 1998, §6.3 (Цифровой поиск).
  6. ^ Кнут 1998, §6.4, (Хеширование).

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

Книги

  • Кнут, Дональд (1998). Сортировка и поиск. Искусство программирования. 3 (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли Профессионал.CS1 maint: ref = harv (связь)

Статьи

внешняя ссылка