Posted:
Дек 1, 2020
Comments:
0 Comments

Алгоритм поиска это: Глава 15 Алгоритм поиска информации в Интернет

Алгоритмы поиска, которые должен знать каждый специалист по обработке и анализу данных | by not eisenheim | NOP::Nuances of Programming

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

Алгоритм поиска — это не то же, что и поисковая служба

Поиск в рамках искусственного интеллекта — это процесс перемещения из исходного состояния в целевое через промежуточные.

Почти любая задача в рамках искусственного интеллекта может быть сформулирована при помощи этих терминов:

  • Состояние — потенциальные исходы в задаче.
  • Переход — смена одного состояния другим.
  • Исходное состояние — состояние системы на момент начала поиска. С него мы начинаем поиск.
  • Промежуточное состояние — состояние, в которое совершается переход на пути от исходного к целевому.
  • Целевое состояние — состояние, при достижении которого поиск останавливается.
  • Область поиска — множество состояний.

Неинформированный поиск используется в том случае, когда нет информации о стоимости перехода из одного состояния в другое.

Существует три главных классических алгоритма неинформированного поиска:

  • Поиск в глубину — обходит область поиска, используя LIFO-стек для определения следующей вершины.
    Преимущества: хорошо работает в глубоких графах, эффективен по памяти.
    Недостатки: есть вероятность зацикливания.
  • Поиск в глубину с итеративным углублением— обходит область поиска, используя LIFO-стек для определения следующей вершины. Когда алгоритм достигает заранее заданной глубины, он очищает стек, увеличивает счётчик достижения предельной глубины и запускает поиск заново из текущей вершины.
  • Поиск в ширину — обходит область поиска, используя FIFO-очередь для определения следующей вершины.

Информированный поиск используется в том случае, когда мы знаем точную стоимость или же оценку стоимости смены состояний.

  • UCS — обходит область поиска, используя очередь с приоритетом и текущий счёт. Текущий счёт для каждого состояния — стоимость достижения состояния из его родителя, то есть, из предыдущего состояния.
  • A* — обходит область поиска, используя очередь с приоритетом и текущий счёт. Текущий счёт для каждого состояния — стоимость достижения состояния через его родителя в пути и эвристическая оценка стоимости перехода из текущей вершины в целевую.
    Допустимое значение эвристической оценки должно удовлетворять следующим двум условиям: во-первых, эвристическая оценка должна быть меньше минимальной стоимости перехода из текущей вершины в целевую; во-вторых, она должна быть меньше эвристической оценки каждой из родительских вершин и стоимости достижения состояния в текущем пути.
  • IDA* — версия поиска A* с итеративным углублением.

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

  • Поиск восхождением к вершине — жадный итеративный алгоритм, выбирающий следующим состоянием наименее затратное, пока оно не достигнет локального максимума.
  • Алгоритм имитации отжига — имитирует физический процесс, восходя к вершине, пока не достигнет локального максимума. При его достижении используется функция “температуры”, которая определяет: стоит ли окончить поиск или продолжать его в попытке найти лучшее решение.
  • GSAT — алгоритм поиска восхождением к вершине на конъюнктивной нормальной форме. Для каждого возможного параметра подбирается случайное множество булевых значений. Если эти значения удовлетворяют предусловиям целевого состояния, то работа алгоритма завершена. Если же нет, то значения инвертируются таким образом, чтобы выражение соответствовало максимальному числу предусловий. Процесс повторяется заново с новым случайным множеством значений для ранее инвертированных переменных.
  • Генетический алгоритм — генерируется исходная популяция состояний, из которой выбирается часть с наибольшим значением функции приспособленности. Оставшиеся состояния рандомно объединяются, немного мутируют, а затем вновь производится отбор лучших решений в следующее поколение.
  • Лучевой поиск — UCS с сохранением значений правдоподобной вероятности значений текущего и предыдущего шага модели. На каждом шаге алгоритм отбирает N наиболее вероятных состояний для дальнейшего поиска.
  • Метод Монте-Карло — рандомизированный алгоритм поиска, который возвращает лучшее приближение верного результата поиска. Он довольно быстрый, но не точный.
  • Лас-Вегас — как и предыдущий, рандомизированный алгоритм, однако он прекращает свою работу лишь в том случае, если найден верный результат. Таким образом, алгоритм всегда точный, но зачастую медленный.
// алгоритм Лас-Вегас
repeat:
k = RandInt(n)
if A[k] == 1,
return k;
  • Атлантик Сити — ограниченный вероятностный алгоритм поиска с полиномиальным временем работы. Он объединяет в себе сильные и слабые стороны алгоритмов Монте-Карло и Лас-Вегас.

Перевод статьи Aaron (Ari) Bornstein: AI Search Algorithms Every Data Scientist Should Know

6 алгоритмов, которые должен знать каждый разработчик

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

Что это за 6 значимых алгоритмов?

1. Алгоритмы сортировки

Что такое сортировка? Это алгоритм, который упорядочивает элементы в списке.

Важные алгоритмы сортировки:

  • Пузырьковая сортировка. Пузырьковая сортировка — это самый простой алгоритм сортировки, который работает путем многократной замены соседних элементов, если они не следуют в порядке.
  • Сортировка слиянием. Сортировка слиянием — это метод сортировки, использующий стратегию «разделяй и властвуй».
  • Быстрая сортировка. Быстрая сортировка — это популярный алгоритм сортировки, который в среднем выполняет n log n сравнений при сортировке массива из n элементов. Это более эффективный и быстрый алгоритм сортировки.
  • Сортировка кучей. Сортировка кучей работает путем визуализации элементов массива как особого типа полного двоичного дерева, известного как куча.

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

Что такое поиск? Это алгоритм, который находит элемент в наборе данных.

Важные алгоритмы поиска:

  • Двоичный поиск. Двоичный поиск использует стратегию «разделяй и властвуй», в которой отсортированный список делится на две половины, а элемент сравнивается со средним элементом списка. Если совпадение найдено, возвращается местоположение среднего элемента.
  • Поиск в ширину (Breadth-First Search, BFS). Поиск в ширину — это алгоритм обхода графа, который начинается с корневого узла и исследует все соседние узлы.
  • Поиск в глубину (Depth-First Search, DFS). Алгоритм поиска в глубину начинается с первого узла графа и продолжает идти все глубже и глубже, пока мы не найдем целевой узел или узел без дочерних элементов.

3. Динамическое программирование

Динамическое программирование — это алгоритмический метод решения задачи оптимизации путем разбиения ее на более простые подзадачи и использования того факта, что оптимальное решение общей проблемы зависит от оптимального решения ее подзадач.

4. Алгоритм рекурсии

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

Каждая рекурсивная программа следует одной и той же базовой последовательности шагов:

  • Создайте алгоритм. Для старта рекурсивным программам обычно требуется начальное значение. Это достигается либо с помощью параметра, переданного в функцию, либо путем предоставления нерекурсивной функции шлюза, которая устанавливает начальные значения для рекурсивного вычисления.
  • Проверьте, соответствуют ли текущие обрабатываемые значения нужному варианту. Если это так, обработайте значение и верните его.
  • Перефразируйте решение с точки зрения меньшей или более простой подзадачи или подзадач.
  • Примените алгоритм к подзадаче.
  • Чтобы сформулировать ответ, объедините результаты.
  • Верните результаты.

5. Разделяй и властвуй

Алгоритм «разделяй и властвуй» (Divide and Conquer) рекурсивно делит проблему на две или более подзадачи того же или связанного типа, пока они не станут достаточно простыми для элементарного решения.

Алгоритм «разделяй и властвуй» состоит из вычислений с использованием трех шагов, перечисленных ниже.

  • Divide. Разделите исходную проблему на подзадачи.
  • Conquer. Рекурсивно решайте каждую подзадачу по одной за раз.
  • Объедините. Соедините решения подзадач, чтобы получить решение всей проблемы.

6. Хеширование

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

Вывод

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

Если вы нашли опечатку — выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать [email protected].

Что такое алгоритм поиска?