Эвристическая функция в ИИ (искусственном интеллекте): краткий обзор

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

Когда кажется невозможным решить конкретную проблему с помощью пошагового подхода, эвристики используются в ИИ (искусственном интеллекте) и МО (машинном обучении). Эвристические функции в ИИ отдают приоритет скорости над точностью; поэтому они часто сочетаются с методами оптимизации для обеспечения лучших результатов.

Что такое эвристическая функция?

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

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

Ваша карьера в области искусственного интеллекта/машинного обучения уже не за горами!Магистерская программа «Инженер искусственного интеллекта»Изучить программу

Свойства алгоритма эвристического поиска

Алгоритмы эвристического поиска обладают следующими свойствами:

• Допустимое условие: если алгоритм дает оптимальный результат, он считается допустимым.
• Полнота: если алгоритм завершается решением, он считается завершенным.
• Свойство доминирования: если A1 и A2 являются двумя эвристическими алгоритмами и имеют эвристические функции h1 и h2 соответственно, то A1 будет доминировать над A2, если h1 превосходит h2 для всех возможных значений узла n.
• Свойство оптимальности: если алгоритм является полным, допустимым и доминирует над другими алгоритмами, то он будет оптимальным и, несомненно, даст оптимальный результат.

Различные категории методов эвристического поиска в ИИ

Методы эвристического поиска можно разделить на два типа:

Методы прямого эвристического поиска

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

Они используют произвольную последовательность операций и ищут решение по всему пространству состояний. К ним относятся поиск в глубину (DFS) и поиск в ширину (BFS).

BFS — это эвристический метод поиска для диаграмм данных или быстрого сканирования пересечений или древовидных структур. DFS основан на вероятности последнего вошел, первого вышел. Аналогично, структура данных стека LIFO используется для завершения процесса в рекурсии.

Слабые эвристические методы

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

Для исследования и расширения пользователям требуется дополнительная информация для вычисления предпочтений по дочерним узлам. Эвристическая функция подключена к каждому узлу.

Давайте сначала рассмотрим некоторые стратегии, которые мы часто видим, прежде чем подробно останавливаться на конкретных. Вот несколько примеров.

• Поиск
• Поиск по лучшему первому
• Поиск табу
• Двунаправленный поиск
• Постоянные проблемы с удовлетворением
• скалолазание

Ваша карьера в области искусственного интеллекта/машинного обучения уже не за горами!Магистерская программа «Инженер искусственного интеллекта»Изучить программу

Примеры эвристических функций в ИИ

Множество задач можно решить с помощью эвристической функции в ИИ.

Давайте поговорим о некоторых наиболее популярных из них.

Задача коммивояжера

Каков кратчайший путь между каждым городом и его начальной точкой, если задан список городов и расстояния между каждой парой из них?

Эту проблему можно решить методом перебора для небольшого числа городов. Но по мере роста числа городов поиск решения становится все более сложным.

Эта проблема хорошо решается эвристикой ближайшего соседа, которая заставляет компьютер всегда выбирать ближайший неисследованный город в качестве следующей остановки на пути. Хотя NN только иногда предлагает оптимальное решение, оно часто достаточно близко, чтобы вариация была незначительной для ответа на проблему продавца. Этот подход снижает сложность TSP с O(n!) до O (n^2).

Поисковый движок

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

С нетерпением ждем успешной карьеры в области ИИ и машинного обучения. Зарегистрируйтесь в нашей программе профессиональной сертификации в области ИИ и машинного обучения в сотрудничестве с Университетом Пердью уже сейчас.

Заключение

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

Часто задаваемые вопросы

1. Что такое эвристическая функция, приведите пример?

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

2. Где используется эвристическая функция?

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

3. Какие существуют типы эвристических функций?

Типы эвристических функций в ИИ:

Поиск в ширину (BFS) и поиск в глубину (DFS), двунаправленный поиск, поиск A* с имитацией отжига, поиск по холму, поиск по наилучшему первому и поиск по лучу.

4. Какова формула эвристической функции?

f(n)= g(n) + h(n), где

f(n)= предполагаемая стоимость самого дешевого решения

g(n)= стоимость достижения узла n из начального состояния

h(n)= стоимость достижения от узла n до целевого узла

5. Каковы четыре типа эвристик?

Четыре типа эвристик:

• Эвристика доступности
• Эвристика репрезентативности
• Эвристика закрепления и корректировки
• Быстро и просто

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

6. Каковы три типа эвристик?

Наибольшее внимание привлекли три эвристики: репрезентативность, привязка и корректировка, а также доступность.