17 просмотров

Решение проблем в искусственном интеллекте

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

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

Агент по решению проблем

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

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

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

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

Действия, выполняемые агентом по решению проблем

  • Формулировка цели: Это первый и самый простой шаг в решении проблемы. Он организует шаги/последовательность, необходимые для формулирования одной цели из множества целей, а также действия для достижения этой цели. Формулировка цели основана на текущей ситуации и критериях производительности агента (обсуждается ниже).
  • Постановка проблемы: Это самый важный шаг решения проблемы, который решает, какие действия следует предпринять для достижения сформулированной цели. В формулировке проблемы задействованы следующие пять компонентов:
  • Начальное состояние: Это начальное состояние или начальный шаг агента к своей цели.
  • Действия: Это описание возможных действий, доступных агенту.
  • Модель перехода: Он описывает, что делает каждое действие.
  • Целевой тест: Он определяет, является ли данное состояние целевым состоянием.
  • Стоимость пути: Он назначает числовую стоимость каждому пути, который следует за целью. Агент, решающий проблемы, выбирает функцию затрат, которая отражает его показатель эффективности. Запомнить, оптимальное решение имеет наименьшую стоимость пути среди всех решений.
Статья в тему:  Почему искусственный интеллект связан с психологией

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

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

Примеры проблем

По сути, существует два типа проблемных подходов:

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

Некоторые проблемы с игрушками

  • 8 Задача-головоломка: Здесь у нас есть матрица 3×3 с подвижными плитками, пронумерованными от 1 до 8 с пустым пространством. Плитка, примыкающая к пустому пространству, может скользить в это пространство.Цель состоит в том, чтобы достичь определенного целевого состояния, аналогичного целевому состоянию, как показано на рисунке ниже.
  • На рисунке наша задача — преобразовать текущее состояние в целевое, вставив цифры в пустое место.
Статья в тему:  Какой курс искусственного интеллекта

Некоторые проблемы с игрушками

На приведенном выше рисунке наша задача состоит в том, чтобы преобразовать текущее (начальное) состояние в целевое состояние, вставив цифры в пустое место.

Формулировка проблемы следующая:

  • Состояния: Он описывает расположение каждой пронумерованной плитки и пустой плитки.
  • Начальное состояние: Мы можем начать с любого состояния как начального состояния.
  • Действия: Здесь определены действия пустого пространства, т. е. либо влево, вправо, вверх или вниз
  • Модель перехода: Он возвращает результирующее состояние в соответствии с заданным состоянием и действиями.
  • Целевой тест: Он определяет, достигли ли мы правильного целевого состояния.
  • Стоимость пути: Стоимость пути — это количество шагов на пути, где стоимость каждого шага равна 1.

Примечание: Задача с 8 головоломками относится к типу задача со скользящим блоком который используется для тестирования новых алгоритмов поиска в искусственном интеллекте.

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

Из следующего рисунка мы можем понять проблему, а также ее правильное решение.

Задача восьми ферзей в искусственном интеллекте

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

Статья в тему:  Как загрузить искусственный интеллект в виртуальную реальность

Для этой задачи существует два основных вида формулировок:

  • Инкрементальная формулировка: Он начинается с пустого состояния, когда оператор увеличивает ферзя на каждом шаге.

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

  • Состояния: Расположение любых ферзей от 0 до 8 на шахматной доске.
  • Начальное состояние: Пустая шахматная доска
  • Действия: Добавьте королеву в любую пустую коробку.
  • Модель перехода: Возвращает шахматную доску с ферзем, добавленным в поле.
  • Целевой тест: Проверяет, размещены ли на шахматной доске 8-ферзей без какой-либо атаки.
  • Стоимость пути: Нет необходимости в стоимости пути, потому что учитываются только конечные состояния.

В этой формулировке примерно 1,8 х 10 14 возможная последовательность расследования.

  • Формулировка полного состояния: Он начинает со всеми 8-ферзями на шахматной доске и перемещает их, спасая от атак.

Следующие шаги включены в эту формулировку

  • Состояния: Расположение всех 8 ферзей по одному в столбце, при этом ни один ферзь не атакует другого ферзя.
  • Действия: Переместите ферзя в безопасное место от атак.

Эта формулировка лучше, чем инкрементная формулировка, поскольку она уменьшает пространство состояний от 1,8 х 10 14 к 2057, и найти решение несложно.

Некоторые проблемы реального мира

  • Задача коммивояжера (TSP): Это гастрольная проблема где продавец может посетить каждый город только один раз. Цель состоит в том, чтобы найти самый короткий тур и распродать вещи в каждом городе.
  • Проблема компоновки СБИС: В этой задаче миллионы компонентов и соединений размещаются на кристалле, чтобы свести к минимуму площадь, задержки в цепи, паразитные емкости и максимизировать производительность производства.
Статья в тему:  Что такое индуктивное обучение в искусственном интеллекте

Проблема компоновки разделена на две части:

  • Расположение ячеек: Здесь примитивные компоненты схемы сгруппированы в ячейки, каждая из которых выполняет свою определенную функцию. Каждая ячейка имеет фиксированную форму и размер. Задача состоит в том, чтобы разместить клетки на фишке, не перекрывая друг друга.
  • Маршрутизация каналов: Он находит определенный маршрут для каждого провода через промежутки между ячейками.
  • Белковый дизайн: Цель состоит в том, чтобы найти последовательность аминокислот, которая будет складываться в трехмерный белок, обладающий свойством излечивать некоторые болезни.

Поиск решений

Мы видели много проблем. Теперь есть потребность в поиске решений для их решения.

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

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

Измерение эффективности решения проблем

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

Комплектность: Он измеряет, гарантирует ли алгоритм нахождение решения (если какое-либо решение существует).

Оптимальность: Он измеряет, ищет ли стратегия оптимальное решение.

Сложность времени: Время, затрачиваемое алгоритмом на поиск решения.

Космическая сложность: Объем памяти, необходимый для выполнения поиска.

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

Статья в тему:  Как Китай использует искусственный интеллект в классах

Стратегии поиска

Существует два типа стратегий, описывающих решение данной проблемы:

Неинформированный поиск (слепой поиск)

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

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

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

Информированный поиск (эвристический поиск)

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

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

  • Лучший первый поиск (Жадный поиск)
  • Поиск

Похожие сообщения:

  • 10 лучших технологий искусственного интеллекта в 2020 году.
  • Проблемы удовлетворения ограничений в искусственном интеллекте
  • Эвристические функции в искусственном интеллекте
  • Динамические байесовские сети
  • Полезные функции в искусственном интеллекте
  • Вероятностное рассуждение
  • Количественная оценка неопределенности
  • Классическое планирование
  • Скрытые марковские модели
  • Агенты, основанные на знаниях, в ИИ
голоса
Рейтинг статьи
Статья в тему:  Где научиться искусственному интеллекту для игр
Ссылка на основную публикацию
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x