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

Материал из wikixw
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

Классы[править]

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

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

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

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

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

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

Для субструктур данной структуры[править]

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

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

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

Поиск максимума функции[править]

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

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

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

Смотрите также[править]

Категории:

Источник — https://wikixw.ru/index.php?title=Алгоритм_поиска&oldid=16398