Билет №49. В каких случаях применяются эвристики в задачах искусственного интеллекта? Какие алгоритмы поиска называются эвристическими? Назовите и кратко опишите некоторые

В задачах искусственного интеллекта эвристику используют в двух ситуациях:

1. Проблема может не иметь точного решения из-за неопределённости в постановке задачи и/или в исходных данных. Например, в медицинской диагностике определённый набор

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

вызывают различные (часто не связанные друг с другом) предположения относительно протяжённости и ориентации объектов. Оптический обман – хорошая иллюстрация таких

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

2. Проблема может иметь точное решение, но стоимость его поиска может быть слишком высокой. Во многих задачах (например, игра в шахматы) рост пространства возможных состояний носит экспоненциальный характер, другими словами, число возможных состояний растёт экспоненциально с увеличением глубины поиска. В этих случаях методы поиска решения «в лоб» типа поиска в глубину или в ширину могут занять слишком много времени. Эвристика позволяет избежать этой сложности и вести поиск по наиболее «перспективному» пути, исключая из

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

приемлемое решение.

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

Простая форма эвристического поиска – это восхождение на гору (hill climbing). В процессе поиска в программе использует некоторая оценочная функция, с помощью которой можно грубо оценить, насколько «хорошим» (или «плохим») является текущее состояние. Затем можно

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

Основной алгоритм, реализующий идею восхождения на гору, можно сформулировать следующим образом.

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

2. Если одно из новых состояний является решением проблемы, прекратить процесс. В противном случае перейти в то состояние, которое характеризуется наивысшим значением оценочной функции. Вернуться к шагу (1).

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

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

Билет №50. Какими особенностями обладают программы на LISP? Какая структура и как используется в качестве основы этого языка? Для чего необходимо лямбда-исчисление? Приведите пример.

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

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

Основными уникальными особенностями LISP, отличающими его от прочих языков, являются следующие:

• Основной структурой данных является список символов,

• Программы на этом языке также имеют списочную структуру,

• Базовыми операциями являются операции над списками.

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

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

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

В качестве базовой структуры языка лежит выбор списков. Базовым блоком в структуре данных языка LISP является символическое выражение.

Простое символическое выражение использует атомарные символы, или атомы — строки

буквенно-цифровых символов, которые начинаются с буквы, например WOMBAT. (Допустимая

длина строки варьируется в зависимости от версии исполняющей системы.) Во внутренней

структуре данных атом представлен ячейкой памяти. Отдельным атомом является символ Т,

которым представляется константа "True" — истина. Другой специальный атом, NIL,

представляет, с одной стороны, константу "False"—ложь, а с другой — пустой список.

Составные выражения объединяются в древовидной структуре, при этом используется

очевидное соответствие между символическими выражениями и представлением конечных 66

деревьев. Читатели, склонные к математическим формулировкам, найдут более строгое

изложение этого соответствия во врезке 4.2.

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

объединять элементы разных типов и иметь произвольную длину и размерность (вложенность).

Например, в LISP возможен такой список:

("а" (9) () N (? (WOMBAT)) (A . В) NIL 0.9)

Этот список содержит элементы разных типов — строки, числа с фиксированной и

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

Но списки имеют и определенные недостатки, из-за которых в LISP были включены и другие

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

с одного конца списка. Манипулируя только таким списком, невозможно обратиться к элементу

списка по его позиции, как это делается с элементом массива. Поэтому для представления

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

включены другие типы структур. В современных версиях LISP поддерживаются массивы, хэш-

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

пространство памяти и повысить скорость доступа.

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

(defun sqr (x) (* x x))

тогда значением выражения (sqr 5) будет 25. Однако, это не единственный, и не главный способ определения функций. Зачастую необходимо передавать в качестве параметра само определение функции, не определяя ее глобально. Осуществить это можно с помощью лямбда-исчисления (lambda-calculus) – математической моделью обеспечивающей четкое разграничение между объектом и его именем. Синтаксис лямбда-выражения представляет собой список следующей структуры

(lambda (<функциональные параметры>) <тело функции>).

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

(funcall #’(lambda (x) (* x x)) 4).

Функция funcall #’ осуществит вычисление переданного лямбда-выражения для параметра 4. Конечно, через лямбда-выражение можно определить и именованную функцию:

(defun sqr (x) (lambda (x) (* x x))).