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

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

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

В данной главе применяются понятия из области анализа алгоритмов. Читатели, незнакомые с понятиями асимптотической сложности (т.е. с системой обозначений О ()) и NP-полноты, должны обратиться к приложению А.