1.Обучение, обучающие выборки
Обучение (в психологии) – усвоение новых знаний. 
Новые умения и навыки приобретаются путем тренировки и упражнения.
Обучение (в работах по ИИ): «любое изменение в системе, приводящее к улучшению решения задачи при ее повторном предъявлении или к решению другой задачи на основе тех же данных» - Н.Саймон.
Принцип полноты базовых знаний. Возможность/невозможность «обучения с нуля».
Проблемы полноты и репрезентативности обучающей выборки (при пополнении базы знаний).
Некоторые важные термины
Генеральная совокупность – вся изучаемая выборочным методом статистическая совокупность объектов и/или явлений, имеющих общие качественные признаки или количественные переменные
Выборка (выборочная совокупность) – часть объектов из генеральной совокупности, отобранных для изучения, с тем чтобы сделать заключение о всей генеральной совокупности. Для того, чтобы заключение, полученное путем изучения выборки, можно было распространить на всю генеральную совокупность выборка должна обладать свойством репрезентативности.
Репрезентативность (представительность) – свойство выборки отражать характеристики изучаемой генеральной совокупности.
Репрезентативная выборка – выборка, имеющая такое же распределение относительных характеристик, что и генеральная совокупность.
Ошибки выборки – отклонение статистической структуры выборки от структуры соответствующей генеральной совокупности.
Произвольная выборка – эмпирическая выборка, не имеющая вероятностного обоснования, складывающаяся на основе случая, причем выбор каждого случая не влияет на любой другой случай.
Источник – www.glossary.ru.

2.Символьное обучение (обучение в ПРОСТРАНСТВЕ ПОНЯТИЙ)
Основные операции в пространстве понятий: обобщение, специализация.
Индуктивное обучение как поиск в пространстве понятий
Пример: Пусть в пространство понятий входит некоторое абстрактное понятие: 
Object (Sizes, Colors, Shapes) 
и известно, что его признаки принимают такие значения:
Sizes = {large, small}; Colors = {red, blue, white, green}; Shapes = {round, polygon}
Индуктивное обучение в этом пространстве – поиск понятия, удовлетворяющего всем примерам обучающей выборки.
Пусть, далее, у нас есть единственный обучающий пример – Object1 (small, red, round).
Результатом обучения может стать пополнение пространства понятий таким новым частным случаем  («маленький красный шар»/«маленький красный мяч» и т.п.). Это – специализация.
Пусть появляется второй обучающий пример –  Object2 (large, red, round).
Результатом обучения может стать пополнение пространства понятий этим новым частным случаем  («большой красный шар»/«большой красный мяч» и т.п.). Это тоже – специализация.
Можно выполнить и некоторые операции обобщения, построив и добавив в общее пространство новые понятия:
Object3 (X, red, round)	– («красный шар»/«красный мяч» и т.п.) 
Object4 (X, Y, round)		– («шар»/«мяч» и т.п.) 
Основные операции обобщения
1.Замена конкретного значения понятия на переменную: 
Colors (X, red) & Shapes (X, cube) → Colors (X, Y) & Shapes (X, cube)
(«красный куб») → («куб <любого цвета>»)
2.Исключение конъюнкта:
Sizes (X, small) & Colors (X, red) & Shapes (X, cube) → Colors (X, red) & Shapes (X, cube)
(«красный куб малого размера») → («красный куб»)
3.Добавление дизъюнкта:
Colors (X, red) & Shapes (X, cube) → Colors (X, red) & ((Shapes (X, cube) V Shapes (X, pyramid)) 
(«красный куб») → («красный куб или красная пирамида»)
4.Замена конкретного объекта или частного понятия общим понятием (на основе иерархии классов):
Colors (X, red) → Colors (X, rainbow-color)	(«красный» → «цвета радуги»)
Shapes (X, polyhedron) → Shapes (X, solid) 	(«многогранник» → «геометрическое тело»)
Роль отрицательных примеров в предотвращении излишнего обобщения.

В последние годы определенную популярность в работах по ИИ получил подход к моделированию процессов обучения/развития на основе так называемых генетических алгоритмов.
3.Понятие о генетических алгоритмах
(Использован материал бывшего доступным в 2002 году сайта:
http://www.ai.tsi.lv/ru/index.htm, Борисов А.Н. Курс: Генетические алгоритмы, 2002)
Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Джоном Генри Холландом в книге «Адаптация в естественных и искусственных системах» (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.
ГА работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах. 
Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.
ГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемой проблемы. Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов для генерации новых решений из предыдущей популяции; 4) Целевая функция для оценки приспособленности (fitness) решений. 
Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможных бинарных строк представляет возможное решение задачи. Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.
 Селекция
Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир. 
•	Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален некоторой величине вычисляемой по формуле.
При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью. 
•	Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2. 
 Скрещивание
Оператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

      0       1       #       #      1

     0       1       #       1       0

     1       0       0       1       0

     1       0       0       #       1

Мутация
Мутация (mutation) - стохастическое изменение части хромосом. Каждый ген строки, которая подвергается мутации, с вероятностью Pmut (обычно очень маленькой) меняется на другой ген. 

      0       1       0       #       1

      0       1       1       #       1

Схема работы ГА
Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.
Схема работы простого ГА выглядит следующим образом:

Начальная
популяция

отбор

скрещивание

мутация

оценка
результата

Повторение цикла с новой популяцией

Задача решена.  Выход

Критерии остановки алгоритма:
•	нахождение глобального, либо субоптимального решения; 
•	исчерпание числа поколений, отпущенных на эволюцию; 
•	исчерпание времени, отпущенного на эволюцию. 
Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска. Примеры реальных областей применения:
•	оптимизация запросов в базах данных;
•	задачи на графах (задача коммивояжера, раскраска);
•	задачи компоновки;
•	составление расписаний.
Замечание: Генетические алгоритмы и «метод проб и ошибок».

Решение задач и искусственный интеллект

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

Представление задач в пространстве состояний

Основные понятия

Типичным представителем класса задач, для которых подходит представление в пространстве состояний, является головоломка, известная как игра в пятнадцать – см. рис. 1(а). В ней используется пятнадцать пронумерованных (от 1 до 15) подвижных фишек, расположенных в клетках квадрата 44. Одна клетка этого квадрата остается всегда пустой, так что одну из соседних с ней фишек можно передвинуть на место этой пустой клетки, изменив тем самым местоположение пустой клетки. Заметим, что более простым вариантом этой головоломки является квадрат 33 и восемь фишек на нем – пример соответствующей задачи показан на рис.1(б).
На рис.1(а) изображены две конфигурации фишек. В головоломке требуется преобразовать первую, или начальную, конфигурацию во вторую, или целевую конфигурацию. Решением этой задачи будет подходящая последовательность сдвигов фишек, например: передвинуть фишку 8 вверх, фишку 6 влево и т.д. 

Важной особенностью класса задач, к которому принадлежит рассмотренная головоломка, относится наличие в задаче точно определенной начальной ситуации и точно определенной цели. Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию в другую. Именно из таких ходов состоит искомое решение задачи, которое можно в принципе получить методом проб и ошибок. Действительно, отправляясь от начальной ситуации, можно построить конфигурации, возникающие в результате выполнения возможных в этой ситуации ходов, затем построить множество конфигураций, получающихся после применения следующего хода, и так далее – пока не будет достигнута целевая конфигурация.
Введем теперь основные понятия, используемые при формализации задачи в пространстве состояний. Центральным из них является понятие состояния, характеризующего некоторый момент решения задачи. Например, для игры в пятнадцать (или в восемь) состояние – это просто некоторая конкретная конфигурация фишек. 
Среди всех состояний задачи выделяются начальное состояние и целевое состояние, в совокупности определяющие задачу, которую надо решить   примеры их приведены на рис.1.
Другим важным понятием является понятие оператора, т.е. допустимого хода в задаче. Оператор преобразует одно состояние в другое, являясь по сути функцией, определенной на множестве состояний и принимающей значения из этого множества. Для игры в пятнадцать или в восемь удобнее выделить четыре оператора, соответствующие перемещениям пустой клетки (можно считать ее фишкой-«пустышкой») влево, вправо, вверх, вниз. В некоторых случаях оператор может оказаться неприменимым к какому-то состоянию: например, операторы сдвига вправо и вниз неприменимы, если пустая клетка расположена в правом нижнем углу. Значит, в общем случае оператор является частично определенной функцией отображения состояний.

В терминах состояний и операторов решение задачи есть определенная последовательность операторов, преобразующая начальное состояние в целевое. Решение задачи ищется в пространстве состояний – множестве всех состояний, достижимых из начального состояния при помощи  заданных  операторов. Например, в игре в пятнадцать или в восемь пространство состояний состоит из всех конфигураций фишек, которые могут быть образованы в результате возможных перемещений фишек.
Пространство состояний можно представить в виде направленного графа, вершины которого соответствуют состояниям, а дуги (ребра) – применяемым операторам. Указанные в виде стрелок направления соответствуют движению от вершины-аргумента применяемого оператора к результирующей вершине. Тогда решением задачи будет путь в этом графе, ведущий от начального состояния к целевому. На рис.2 показана часть пространства состояний для игры в пятнадцать. Каждая вершина соответствует некоторой конфигурации фишек. Все дуги между вершинами являются двунаправленными, поскольку в этой головоломке для любого оператора есть обратный ему (точнее, множество операторов состоит из двух пар взаимно-обратных операторов: влево-вправо, вверх-вниз). 
Пространства состояний могут быть большими и даже бесконечными, но в любом случае предполагается счетность множества состояний.
Таким образом, в подходе к решению задачи с использованием пространства состояний задача рассматривается как тройка ( SI , O , SG ) , где
SI  – начальное состояние;
O – конечное множество операторов, действующих на не более чем счетном множестве состояний;
SG  – целевое состояние.
Дальнейшая формализация решения задачи с использованием пространства состояний предполагает выбор некоторой конкретной формы описания состояний задачи. Для этого могут применяться любые подходящие структуры – строки, массивы, списки, деревья и т.п. Например, для игры в пятнадцать или восемь наиболее естественной  формой описания состояния будет список положений фишек или же двумерный массив. Заметим, что от выбора формы описания состояния зависит в общем случае сложность задания операторов задачи, которые должны быть также определены при формализации задачи в пространстве состояний. 
Если для игры в пятнадцать средством формализации выступает язык программирования Лисп или Паскаль, то операторы задачи могут быть описаны в виде четырех соответствующих функций языка. При использовании же продукционного языка, эти операторы задаются в виде правил продукций вида: «исходное состояние  результирующее состояние».
В рассмотренных выше примерах (игры в пятнадцать и восемь) искомое целевое состояние задавалось явно, т.е. известно было местоположение каждой фишки в целевой конфигурации. В более сложных случаях игры может быть несколько целевых состояний, либо же целевое состояние может быть определено неявно, т.е. охарактеризовано некоторым свойством, например, как состояние, в котором сумма номеров фишек в верхнем ряду не превосходит 10. В подобных случаях свойство, которому должно удовлетворять целевое состояние, должно быть описано исчерпывающим образом, к примеру, путем задания булевской функции, реализующей проверку нужного свойства состояния задачи.
Итак, для представления задачи в пространстве состояний необходимо определить  следующее:
•	форму описания состояний задачи и описание начального состояния;
•	множество операторов и их воздействий на описания состояний;
•	множество целевых состояний или же описание их свойств.
Перечисленные составляющие задают неявно граф-пространство состояний, в котором требуется провести поиск решения задачи. Заметим попутно, что в отличие от такого неявного способа задания графа, при явном способе задания все вершины и дуги графа должны быть перечислены, например, с помощью таблиц.
	Решение задачи в пространстве состояний подразумевает просмотр неявно заданного графа, для чего необходимо преобразование в явную форму достаточно большой его части, включающей искомую целевую вершину. Действительно, просмотр осуществляется как последовательный поиск, или перебор вершин, в пространстве состояний. В исходной точке процесса к начальному состоянию применяется тот или иной оператор и строится новая вершина-состояние, а также связывающие ее с корневой вершиной дуги. На каждом последующем шаге поиска к одной из уже полученных вершин-состояний применяется допустимый оператор и строится еще одна вершина графа и связывающие дуги. Этот процесс поиска продолжается до тех пор, пока не будет построена вершина, соответствующая целевому состоянию.

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

Рассмотрим формализацию в пространстве состояний известной задачи о коммивояжере (представляющей классическую переборную проблему). Коммивояжер, располагая картой дорог, соединяющей 7 городов (рис. 3), должен построить свой маршрут так, чтобы выехав из города А, посетить каждый из других шести городов B, C, D, E, H, G в точности по одному разу и затем вернуться в исходный город. В другом, более сложном варианте задачи требуется также, чтобы маршрут имел минимальную протяженность.

Состояние решаемой задачи можно задать как список городов, которые уже проехал коммивояжер к текущему моменту. Тогда возможным состояниям соответствуют списки из элементов A, B, C, D, E, H, G без повторений, исключение составляет только город A, он может встретиться в списке дважды – в начале списка и его конце. Пример списка-состояния – (A B C H). Начальное же состояние определяется как список (A), а целевое – как любой допустимый список, начинающийся и кончающийся элементом A. Для определенных таким образом состояний задачи операторы задачи могут соответствовать перемещениям между городами – получаем таким образом 13 операторов. 

Рассмотрим теперь широко известную задачу об обезьяне и банане, простейшую формулировку которой мы и рассмотрим. В комнате находятся обезьяна, ящик и связка бананов, которая подвешена к потолку настолько высоко, что обезьяна может до нее дотянуться, только встав на ящик. Нужно найти последовательность действий, которая позволит обезьяне достать бананы. Предполагается, что обезьяна может ходить по комнате, двигать по полу ящик, взбираться на него и хватать бананы.
Ясно, что описание состояния этой задачи должно включать следующие сведения: местоположение обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (т.е. на полу она или на ящике), местоположение ящика  на полу и наличие у обезьяны бананов. Все это можно представить в виде четырехэлементного списка (ПолОб, ВертОб, ПолЯщ, Цель), где
ПолОб – положение обезьяны на полу (это может быть двухэлементный вектор координат);
ПолЯщ –  положение обезьяны и ящика на полу;
ВертОб – это константа П или Я в зависимости от того, где находится обезьяна, на полу или на ящике;
Цель – это константа 0 или 1 в зависимости от того, достала ли обезьяна бананы или нет.
Зафиксируем также как константы три следующие точки в плоскости пола: 
ТО –  точка первоначального местоположения обезьяны;
ТЯ – точка первоначального расположения ящика;
ТБ – точка пола, расположенная непосредственно под связкой бананов.
Тогда начальное состояние задачи описывается списком (ТО, П, ТЯ, 0), а целевое состояние задается как любой список, последний элемент которого – 1.  
Естественно определить операторы в этой задаче в соответствии с возможными действиями обезьяны:
1)	Перейти (W) – переход обезьяны к точке W горизонтальной плоскости пола;
2)	Передвинуть (V) – передвижение обезьяной ящика в точку V пола;
3)	Взобраться – обезьяна взбирается на ящик;
4)	Схватить – обезьяна хватает  связку бананов.
Условия применимости и действие этих операторов легко определить в виде правил продукций вида: аргумент оператора   результат оператора,
причем
 X, Y, Z, W, V обозначают переменные:
1.	Перейти (W) :		(X, П, Y, Z )   (W, П, Y, Z)
2.	Передвинуть (V) :	(X, П, X, Z)   (V, П, V, Z)
3.	Взобраться :		(X, П, X, Z)    (X, Я, X, Z)
4.	Схватить:		(ТБ, Я,ТБ, 0)  (ТБ, Я, ТБ, 1)
Будем считать, что для решения задачи значимы лишь вышеупомянутые точки пола ТО, ТЯ, ТБ , тогда получим пространство состояний задачи, изображенное на рис. 4. Это пространство содержит только 13 состояний, дуги графа-пространства промаркированы порядковым номером применяемого оператора. Пространство содержит четыре цикла хождения обезьяны между тремя значимыми точками (с ящиком или без него). В пространстве есть также две тупиковые ветви – когда обезьяна залезает на ящик, но не под связкой бананов. Жирными дугами (стрелками) показан решающий путь, состоящий из четырех операторов:  Перейти (ТЯ); Передвинуть(ТБ); Взобраться; Схватить.

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

Алгоритмы поиска решения

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

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

Перебор вширь
Базовый алгоритм поиска вширь состоит из следующей последовательности шагов (здесь и далее предполагаем, что начальная вершина не является целевой):
Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.
Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.
Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.
Шаг 4. Раскрыть вершину Current, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.
Шаг 5. Проверить, нет ли среди дочерних вершин целевых. Если есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей назад от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.
Конец алгоритма.
	Основу этого алгоритма составляет цикл последовательного раскрытия (шаги 2-5) концевых вершин (листьев) дерева перебора, хранящихся в списке Open. Алгоритм поиска вширь является полным. Можно также показать, что при переборе вширь непременно будет найден самый короткий путь к целевой вершине, причем быстрее, чем другие решающие пути –  при условии, что этот путь вообще существует. Если же решающего пути нет, то (в случае конечных деревьев-пространств) будет сообщено о неуспехе поиска, в случае же бесконечных пространств  алгоритм  не кончит свою работу.
	На рис. 5 приведено дерево, построенное в результате применения алгоритма поиска вширь к некоторой  начальной конфигурации игры в восемь, причем выполнение алгоритма прервано после построения первых 12  вершин (при этом раскрыто 6 вершин). В вершинах дерева помещены соответствующие описания состояний. Эти вершины занумерованы в том порядке, в котором они были построены в ходе поиска. На следующем шаге цикла алгоритма будет раскрываться одна из вершин с номерами 6, 7 или 8, поскольку они расположены в начале  списка нераскрытых вершин.

Считаем, что порядок построения дочерних вершин соответствует следующему зафиксированному порядку перемещения пустой клетки («пустышки»): влево/вправо/вверх/вниз. Предполагается также, что используемая алгоритмом операция раскрытия вершин организована таким образом, что она не порождает  никакое состояние-вершину,  построенную  ранее и являющуюся родительской для раскрываемой вершины. Тем самым в дереве перебора нет дублирования одного и то же состояния в вершинах, имеющих общего соседа-вершину.
В приведенном примере алгоритм перебора вглубь, сформулированный для деревьев-пространств, применялся к пространству состояний, являющемуся графом (в котором могут быть циклы). В некоторых случаях это допустимо, т.е. алгоритм находит решение, если оно есть, и заканчивает работу. Построенная алгоритмом структура из вершин и указателей всегда образует дерево (дерево перебора), поскольку указатели от дочерних вершин ссылаются только на одну порождающую вершину. Но в случае поиска на произвольном графе (и в этом – отличие от деревьев-пространств) одно и тоже состояние может быть продублировано в разных частях полученного дерева перебора. В примере игры  в восемь по принятому предположению об операции раскрытия исключалось только повторное возникновение состояний, встречавшихся два шага вверх по дереву перебора, другие же, более далекие друг от друга повторы одного и того же состояния остаются возможными. В случае поиска в графе состояний общего вида он как бы разворачивается при поиске в дерево путем дублирования некоторых его частей. Если это дублирование неоднократное (из-за циклов в графе), то оно может привести к зацикливанию базового алгоритма поиска вширь.

Перебор вглубь
Для формулировки алгоритма поиска вглубь необходимо определить понятие глубины вершины в дереве поиска. Это можно сделать следующим образом:
•	глубина корня дерева равна нулю;
•	глубина каждой некорневой вершины на единицу больше глубины ее родительской вершины.
В алгоритме перебора вглубь раскрытию в первую очередь подлежит вершина, имеющая наибольшую глубину. Такой принцип может привести к бесконечному процессу – это происходит, если пространство состояний бесконечно, и поиск вглубь пошел по ветви дерева, не содержащей целевую вершину. Поэтому необходимо то или иное ограничение этого процесса, самый распространенный способ – ограничить глубину просмотра дерева. Это означает, что в ходе перебора можно строить только вершины, глубина которых не превышает некоторую заданную граничную глубину. Тем самым, раскрытию в первую очередь подлежит вершина наибольшей глубины, но расположенная выше фиксированной границы. Соответствующий алгоритм поиска называется ограниченным перебором вглубь.
	Основные шаги базового алгоритма ограниченного перебора вглубь (с граничной глубиной D) таковы:
Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open. Установить ее глубину (0). Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.
Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.
Шаг 3’. Если глубина вершины Current равна граничной глубине D, то перейти к шагу 2, в ином случае перейти к следующему шагу.
Шаг 4. Раскрыть вершину Current, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке; с указанием их глубины) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current (на этом шаге значение счетчика глубины увеличивается на 1).
Шаг 5. Проверить, нет ли среди дочерних вершин целевых. Если есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей назад от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.
Конец алгоритма.
Приведенное только что описание очень похоже на описание алгоритма поиска вглубь, разница заключается только в учете глубины (шаги 1, 3’, 4) и в месте списка Open, куда помещаются  построенные дочерние вершины (шаг 4). Отличия выделены серым фоном.
Поскольку глубина поиска ограничена, то будучи примененным к деревьям-пространствам состояний, описанный базовый алгоритм поиска вглубь всегда заканчивает работу. Но в отличие от алгоритма поиска вширь, он является неполным алгоритмом, поскольку вершины пространства 

состояний, расположенные ниже граничной глубины, среди которых могут быть и целевые, так и останутся нерассмотренными.
На рис. 6 показано дерево перебора, построенное алгоритмом поиска вглубь; граничная глубина установлена равной 4. В качестве начального состояния взята та же самая, что и в примере на рис. 5, конфигурация игры в восемь. Вершины занумерованы в том порядке, в котором они были построены. В ходе поиска раскрыто 7 и построено 12 вершин, но, как нетрудно убедиться, сравнивая последние два рисунка, в целом это не те же самые 12 первых вершин,  построенных алгоритмом поиска вширь.
Видно, что в алгоритме поиска в глубину сначала идет поиск вдоль одного пути, пока не будет достигнута установленная граничная глубина, затем рассматриваются альтернативные пути той же или меньшей глубины, которые отличаются от первого пути лишь последней (концевой) вершиной, после чего рассматриваются пути, отличающиеся последними двумя вершинами, и т.д.

Анализ слепых алгоритмов. Бэктрекинг
	Если продолжить выполнение алгоритмов перебора вширь и вглубь для рассмотренного начального состояния игры в восемь (для задачи, указанной на рис.1(б)), то на глубине 5 будет найдена целевая конфигурация. При этом алгоритмом поиска вширь будет раскрыто 26 и построено 46 вершин, а алгоритмом поиска вглубь – соответственно 18 и 35 вершин.
	Сравнивая в общем алгоритмы поиска вширь и вглубь, можно утверждать, что они примерно сравнимы по эффективности (количеству построенных вершин). Но в ряде случаев второй алгоритм, несмотря на свою неполноту, может оказаться предпочтительнее: если он начат с удачной стороны, то целевая вершина будет обнаружена раньше, чем в алгоритме поиска вширь.
	Подчеркнем, что как и в случае перебора вширь, при переборе вглубь формируется именно дерево, а не граф перебора, даже если пространство состояний представлялось графом с циклами. В последнем случае, однако, дерево перебора может содержать дубликаты состояний. Нельзя, к примеру, исключить ситуацию, когда некие две вершины являются друг для друга дочерними, и тогда они будут многократно дублироваться в списке Open, приводя к зацикливанию алгоритма.
	Чтобы избежать такого дублирования вершин, и предотвратить тем самым возможное зацикливание алгоритма в случае перебора на графах общего вида, необходимо внести некоторые очевидные изменения в описанные базовые  алгоритмы поиска вширь и вглубь..
В алгоритме перебора вширь следует дополнительно проверять, не находится ли   каждая вновь построенная  дочерняя вершина (точнее, соответствующее описание состояния) в списках Open и Closed по той причине, что она уже строилась раньше в результате раскрытия какой-то другой вершины. Если это так, то такую вершину не надо снова помещать в список Open (таким образом разрывается цикл графа-пространства, и обрывается соответствующая ветвь дерева перебора). В алгоритме же ограниченного поиска вглубь кроме рассмотренного изменения может оказаться необходимым пересчет глубины порожденной дочерней вершины, уже имеющейся либо в списке Open, либо в списке  Closed. 

Внесенные изменения дают гарантию, что алгоритм поиска вширь всегда завершит работу в случае существования решения, а алгоритм поиска вглубь закончится в любом случае, независимо от существования решения. 
Немаловажно, что алгоритмы слепого перебора описаны нами в форме, пригодной для их программирования с использованием любого языка, не только языка программирования задач искусственного интеллекта. Алгоритм поиска вглубь демонстрирует также  способ решения поисковых задач, называемый бэктрекингом (backtracking), или режимом возвратов. Этот способ предлагает определенную организацию перебора всех возможных вариантов решения задачи, число которых может быть велико.
Суть бэктрекинга состоит в  том, чтобы в каждой точке процесса решения, где существует несколько равноправных (априори) альтернативных путей дальнейшего продолжения, выбрать один из них и следовать ему, предварительно запомнив другие альтернативные пути – для того, чтобы в случае неуспешности выбранного пути решения вернуться в указанную точку и выбрать для продолжения поиска  следующий  альтернативный вариант-путь. В общем случае в процессе решения возможно возникновение многих подобных точек выбора (называемых развилками) со своими вариантами продолжения решения, и к каждой из точек необходимо совершать возвраты и пробовать другие варианты.
В базовом алгоритме поиска вглубь по существу проводится бэктрекинг: действительно, запоминание всех альтернатив продолжения поиска (нераскрытых вершин) осуществляется в списке Open, на шаге 3 производится выбор варианта-альтернативы, а возврат к этому шагу для выбора следующей альтернативы осуществляется  на шагах 4 и 5. 
Некоторые языки для задач искусственного интеллекта, как, например, Пролог и Плэнер имеют специальный встроенный механизм для реализации бэктрекинга. Это означает, что запоминание развилок – самих альтернатив и связанной с ними информации, а также реализация возвратов к нужным точкам (с восстановлением всей операционной обстановки этой точки) возложены на интерпретатор языка, т.е. делается автоматически. От программиста требуется лишь определение развилок с нужными альтернативами и инициация в необходимый момент процесса возврата (заметим попутно, что язык Плэнер, в отличие от Пролога предлагает более гибкие средства управления  бэктрекингом).
В целом алгоритмы слепого перебора являются неэффективными методами поиска решения, и в случае нетривиальных задач их невозможно использовать из-за большого числа порождаемых вершин. Действительно, если L – длина решающего пути, а B – средне количество ветвей (дочерних вершин) у каждой вершины, то для нахождения решения надо исследовать BL  путей, ведущих из начальной вершины. Величина эта растет экспоненциально с ростом длины решающего пути, что приводит к ситуации, называемой уным взрывом. 
Таким образом, для повышения эффективности поиска необходимо использовать информацию, отражающую специфику решаемой задачи и позволяющую более целенаправленно двигаться к цели. Такая информация обычно называется эвристической, а соответствующие алгоритмы и методы – эвристическими.

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

Алгоритм эвристического перебора
Последовательность шагов формулируемого ниже базового алгоритма эвристического (упорядоченного)  перебора похожа на последовательность шагов алгоритмов слепого перебора, отличие заключается в использовании эвристической оценочной функции. После порождения нового состояния-вершины производится его оценивание (т.е. вычисление значения этой функции), и списки открытых и закрытых вершин должны содержать кроме самих вершин их оценки, которые и используются для упорядочения поиска.
Для раскрытия каждый раз в цикле выбирается наиболее перспективная концевая вершина дерева перебора. Также как и в случае алгоритмов слепого поиска множество порождаемых алгоритмом вершин и указателей образует дерево, в листьях которого находятся нераскрытые вершины.
Предполагаем, что исследуемое алгоритмом пространство состояний представляет собой дерево. Тогда основные шаги алгоритма эвристического перебора (best_first_search) таковы:
Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open и вычислить ее оценку.
Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к шагу 3.
Шаг 3. Выбрать из списка Open вершину с минимальной оценкой (среди вершин с одинаковой минимальной оценкой выбирается любая); перенести эту вершину (назовем ее Current) в список Closed.
Шаг 4. Если Current – целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от нее к начальной вершине, в противном случае перейти к следующему шагу.
Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если таких вершин нет, то перейти к шагу 2, в ином случае – к шагу 6.
Шаг 6. Для каждой дочерней вершины вычислить оценку (значение оценочной функции), поместить все дочерние вершины в список Open, и построить указатели, ведущие от этих вершин к родительской вершине Current. Перейти к шагу 2.
Конец алгоритма.
	Заметим, что поиск вглубь можно рассматривать как частный случай упорядоченного поиска с оценочной функцией Est(V) = d(V) , а поиск вширь – с функцией Est(V) = 1/d(V) , где d(V) – глубина вершины V.
Чтобы модифицировать рассмотренный алгоритм для перебора на произвольных графах-пространствах состояний, необходимо предусмотреть в нем реакцию на случай построения дочерних вершин, которые уже имеются либо в списке раскрытых, либо в списке нераскрытых вершин.
	В принципе эвристическая оценочная функция может зависеть не только от внутренних, собственных свойств самого оцениваемого состояния (т.е., свойств входящих в описание состояния элементов) но и от характеристик всего пространства состояний, например, от глубины местонахождения оцениваемой вершины в дереве перебора или других свойств пути к этой вершине. Поэтому значение оценочной функции для вновь построенной дочерней вершины, входящей в список Open или Closed, может понизиться, и надо скорректировать старую оценку вершины, заменив ее на новую, меньшую. Если вновь построенная вершина с меньшей оценкой входит в список Closed, необходимо вновь поместить ее в список Open, но с меньшей оценкой. Потребуется также изменить направления указателей от всех  вершин списков Open и Closed, оценка которых уменьшилась, направив их к вершине Current.
	Впрочем, если оценочная функция учитывает только внутренние   характеристики вершин-состояний, то для предотвращения зацикливания требуется более простая модификация алгоритма – 
надо просто исключить  дублирование состояний в списках Open и Closed, оставляя в них лишь по одному состоянию.
Проиллюстрируем работу алгоритма эвристического поиска опять же на примере игры в восемь для той же начальной ситуации. Воспользуемся в качестве оценочной следующей простой функцией:
Est1(V) = d(V) + k(V)   , где
d(V) – глубина вершины V, или число ребер дерева на пути от этой вершины к начальной вершине;
k(V) – число фишек позиции-вершины V, стоящих не на «своем» месте (фишка стоит не на «своем» месте, если ее позиция отлична от позиции в целевом состоянии).
На рис.7 показано дерево, построенное алгоритмом эвристического перебора с указанной оценочной функцией. Оценка каждой вершины приведена рядом с ней внутри кружка. Отдельно стоящие цифры, как и раньше, показывают порядок, в котором строились вершины. Двойной рамкой обведена найденная целевая вершина, она построена двенадцатой.
Видно, что поскольку каждый раз выбор вершины с минимальной оценкой производится внутри всего построенного к текущему моменту дерева перебора, то раскрываемые друг за другом  вершины могут располагаться в отдаленных друг от друга частях дерева. Применяемая оценочная функция такова, что при прочих равных преимущество имеет менее глубокая вершина.
Решение задачи длиною в пять ходов найдено в результате раскрытия 6  и построения 13 вершин – это существенно меньше, чем при использовании слепого перебора (соответствующие числа были: 26 и 46, 18 и 35). Таким образом, использование эвристической информации приводит к существенному сокращению перебора. 
Существует несколько критериев оценки качества работы алгоритмов перебора. Один из них называется целенаправленностью и вычисляется как P = L / N , где
L – длина найденного пути до цели (она равна глубине целевой вершины), а
N – общее число вершин, построенных в ходе перебора.
P = 1, если  строятся только вершины решающего пути, в остальных случаях P < 1, вообще, эта величина тем меньше, чем больше строится бесполезных вершин. Таким образом, этот критерий показывает, насколько дерево, построенное при переборе, вытянуто, а не кустисто. К сожалению, величина P зависит от длины решающего пути, что затрудняет порой сравнение алгоритмов. Другой критерий оценки, фактор эффективного ветвления, зависит от длины решающего пути гораздо меньше.
Ясно, что алгоритм эвристического поиска с хорошо подобранной оценочной функцией обнаруживает решение задачи быстрее алгоритмов слепого перебора. Однако подбор удачной эвристической функции, существенно сокращающей поиск, – наиболее трудный момент при формализации задачи, и часто подходящая оценочная функция выявляется в результате многих экспериментов.
Принято сравнивать различные оценочные функции для одной и той же задачи по их эвристической силе, т.е. по тому, насколько они убыстряют поиск, делают его эффективным. Заметим, что  эвристическая сила функции должна учитывать общий объем вычислительных затрат при поиске, поэтому кроме числа раскрытых и построенных вершин важен и такой фактор, как сложность вычисления самой оценочной функции. 
Для игры в восемь можно предложить еще одну эвристическую функцию:
Est2(V) = d(V) + s(V).
Первое слагаемое d(V) этой функции имеет тот же смысл, что и для функции Est1. Второе слагаемое получается, если для каждой из восьми фишек подсчитать сумму  двух  расстояний – по вертикали и горизонтали – между клетками, где находится эта фишка в оцениваемом  и целевом состояниях, а затем подсчитать общую сумму s(V)  таких расстояний для всех восьми фишек (тем самым получим «суммарное расстояние» всех фишек от их целевого положения). 
Например, для начальной конфигурации на рис.7 расстояние текущего положения фишки с номером 8 от ее положения в целевой конфигурации равно 1 и по вертикали, и  по горизонтали, а сумма их равна 2. Общая же сумма таких расстояний для всех фишек равна 5 (фишки 3, 4, 5, 7 стоят уже на «своем» месте, поэтому их вклад в суммарное расстояние равен 0). Интуитивно ясно, и это можно показать на примерах, что новая эвристическая функция имеет большую эвристическую силу, т.е. более эффективно направляет поиск к цели. 

Допустимость алгоритма эвристического перебора
	Важным является вопрос, может ли алгоритм эвристического перебора с оценочной функций общего вида (т.е. выбираемой произвольно) гарантировать нахождение решающего пути за конечное число шагов в тех случаях, когда решение существует (как алгоритм поиска вширь). Понятно, что такой уверенности нет прежде всего для задач с бесконечными пространствами состояний. Вообще же, нередка ситуация, когда эвристика, сильно сокращающая перебор для большинства начальных состояний, в то же время для других начальных конфигураций либо не может уменьшить необходимую переборную работу (и решение задачи может искаться даже дольше, чем с использованием слепого метода), либо вовсе не может обеспечить обнаружение решающего пути.      
	Математическое исследование алгоритма эвристического поиска – условий, гарантирующих нахождение им решения – было проведено для эвристических оценочных функций специального вида и для более сложной задачи, чем до сих пор рассматриваемая задача поиска любого решающего пути до целевой вершины. 
Предположим, что на множестве дуг пространства состояний определена функция стоимости:
с(VA, VB) – стоимость дуги-перехода от вершины VA к  вершине VB . 
Определим также стоимость любого пути в графе-пространстве как сумму стоимостей входящих в путь дуг. Пусть целью поиска будет не просто нахождение решающего пути, а нахождение оптимального решающего пути – решающего пути с минимальной стоимостью.
	Предположим также, что эвристическая оценочная функция Est(V) построена таким образом, чтобы оценивать стоимость оптимального решающего пути, идущего из начальной вершины к одной из целевой вершин, при условии, что этот путь проходит через вершину V. Тогда значение оценочной функции можно представить в виде суммы двух слагаемых:
	Est(V) = g(V) + h(V)		(*)
где  g(V) – оценка оптимального пути от начальной вершины до вершины V,
а      h(V) – оценка оптимального пути от вершины V до целевой вершины.
Если в процессе поиска уже построена вершина V, то путь до нее найден, и его стоимость может быть вычислена. Найденный путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из начальной вершины в V), однако стоимость найденного пути может быть использована в качестве оценки искомого пути минимальной стоимости из начальной вершины до V, т.е. в качестве первого слагаемого g(V)  эвристической функции. Второе же слагаемое h(V) может быть предложено исходя из эвристических соображений, свойственных конкретной решаемой задаче, как некоторая характеристика-оценка текущей вершины V (близости ее к цели). Таким образом, собственно эвристическая информация будет воплощена только во втором слагаемом оценочной функции.  
Разновидность алгоритма эвристического поиска, применяемого для поиска оптимального решающего пути и использующего при этом оценочную функцию указанного выше вида (*), известен в литературе как А-алгоритм. Были доказаны важные свойства этого алгоритма, прежде всего, утверждение о его  допустимости.
Алгоритм перебора называют допустимым (или состоятельным), если для произвольного графа он всегда заканчивает свою работу построением оптимального пути к цели, при условии, что такой путь существует.
Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину. 	Верна следующая теорема о допустимости А-алгоритма:
А-алгоритм, использующий некоторую эвристическую функцию вида (*), где 
g(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, а
h(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,
является допустимым, если 	h(V)  h*(V)    для всех вершин V пространства состояний. 
А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этому условию, получил название А*-алгоритма.
	Практическое значение этой теоремы в том, что для допустимости А-алгоритма достаточно найти какую-либо нижнюю грань функции h*(V) и использовать ее в качестве h(V) – тогда оптимальность найденного алгоритмом решения будет гарантирована.
Если взять тривиальную нижнюю грань, т.е. установить h(V) = 0 для всех вершин пространства состояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствию какой-нибудь эвристической информации о задаче, и оценочная функция Est не имеет никакой эвристической силы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этом аналогично поиску вширь. 
Точнее, при 	Est(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ), мы получаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры). Алгоритм равных цен представляет собой более общий вариант метода перебора в ширину, при котором вершины раскрываются в порядке возрастания стоимости g(V) , т.е. в первую очередь раскрывается вершина из списка нераскрытых вершин, для которой величина g имеет наименьшее значение.
	Если же, кроме того, положить стоимость с(VA, VB) = 0 для всех дуг пространства состояний, то А*-алгоритм просто превращается в неэффективный слепой поиск вширь.
Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяют условию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V при стоимости всех дуг с(VA, VB) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, что значение второй функции  всегда (т.е. для всех состояний), больше значения первой функции:	Est1(V)   Est2(V)  , что равнозначно  k (V)  s (V)  .
Действительно, во второй функции вклад каждой фишки в общую оценку-сумму s(V)  либо равен 0 (фишка стоит уже на «своем» месте), либо не меньше 1 (в противном случае), в первой же функции этот вклад в k(V) соответственно либо равен 0, либо  равен 1. 
Из последнего неравенства следует, что условие допустимости достаточно доказать только для второй функции Est2. Справедливость нужного условия  
s(V)  h*(V) следует из следующего соображения. Если бы фишки не мешали друг другу и могли двигаться до «своего» места по кратчайшему пути, как если бы других фишек на квадрате не было, то сумма длин таких путей для всех фишек была бы в точности равна значению s(V) . На самом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что на ней расположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет не меньше s(V).
	Заметим, что s(V) не учитывает должным образом трудность обмена местами двух соседних фишек, а поэтому ее эвристическая сила в принципе может быть повышена. В ряде случаев эвристическая сила некоторой оценочной функции может быть повышена просто путем умножения на положительную константу, большую единицы, однако часто такое повышение осуществимо только за счет отказа от допустимости алгоритма. Например, если для игры в восемь в качестве второй составляющей эвристической функции взять h(V) = 2s(V), то в ряде случаев такая функция будет убыстрять поиск и позволит решать более трудные задачи, но условие допустимости перестанет выполняться (так как для начального состояния на рис.15:  h*(V)  2s(V) ).
	Вообще в случае, когда верно неравенство h1(V)  h2(V) для всех вершин пространства состояний, не являющихся целевыми, А*-алгоритм, использующий эвристическую составляющую h2(V), называется более информированным, чем А*-алгоритм с функцией h1(V). Показано, что если эти функции статичны (т.е. не изменяются в процессе поиска), то более информированный алгоритм раскрывает всегда меньшее число вершин, прежде чем находит путь минимальной стоимости. Это значит, что более информированный алгоритм осуществляет более направленный, а значит, более эффективный (при прочих равных) поиск целевой вершины. Таким образом, понятие информированности отражает один из аспектов понятия эвристической силы оценочной функции при поиске в пространстве состояний.
	Итак, желательно подобрать такую эвристическую функцию h(V), которая была бы нижней границей h*(V) (чтобы гарантировать допустимость алгоритма) и была бы как можно ближе к h*(V) (чтобы обеспечить эффективность поиска). К сожалению, существуют задачи, для которых нельзя найти оценочную функцию, обеспечивающую во всех случаях как эффективность, так и допустимость эвристического поиска. Поэтому часто приходится останавливаться на эвристических функциях, сокращающих поиск во многих случаях ценой отказа от гарантии найти оптимальный решающий путь.
Заметим, что в идеальном случае, когда известна оценка h*(V), и она используется в качестве h(V), А*-алгоритм находит оптимальный решающий путь сразу, без раскрытия ненужных вершин.

Упрощенные варианты эвристического перебора
Сильным упрощением базового алгоритма эвристического поиска с произвольной оценочной функцией является алгоритм «подъема на холм». Этот алгоритм при каждом раскрытии вершины производит упорядочение (по значению оценочной функции) только порожденных дочерних вершин, и выбирает для последующего раскрытия дочернюю вершину с наименьшей оценкой (а не вершину с наименьшей оценкой среди всех нераскрытых вершин дерева поиска, как в базовом алгоритме). Очевидно, что такой локальный выбор среди только что построенных дочерних вершин реализовать гораздо проще, чем глобальный выбор вершины во всем дереве перебора.
	Идея этого алгоритма аналогична идее известного вне области искусственного интеллекта метода «подъема на гору», применяемого для поиска максимума (или минимума) функции. Для того, чтобы в конечном счете найти максимум функции,  на каждом шаге метода производится движение в направлении наибольшей крутизны функции. Для определенного класса функций (имеющих единственный максимум и некоторые другие свойства роста) такое использование локальной информации, т.е. знания направления наиболее крутого подъема в текущей точке, позволяет найти  глобальное решение, т.е. максимум функции.
	В алгоритме «подъема на холм» в пространстве состояний роль функции метода «подъема на гору» играет эвристическая оценочная функция, взятая с обратным знаком. Поиск продолжается всегда от той дочерней вершины, которая  имеет меньшее значение эвристической функции (при этом случай, когда вершин с одинаковой минимальной оценкой несколько, является нежелательным).
Алгоритм «подъема на холм» дает тот же результат, что и базовый алгоритм эвристического поиска в тех случаях, когда оценочная функция обладает определенными свойствами, в частности, имеет один (глобальный) экстремум. Алгоритм становится несостоятельным, если у эвристической функции имеется несколько локальных экстремумов. Бывают и другие случаи бесперспективности «подъема на холм»: если поверхность-множество значений функции имеет равнинный участок («плато») или же участки узкого и длинного возвышения (в виде горного «хребта»), и процесс поиска вывел как раз на них. Таким образом, этот алгоритм имеет ограниченную применимость, но иногда возникающие проблемы можно разрешить, построив более подходящую эвристическую функцию.

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

   (defun HEURISTIC_SEARCH(StartState)
(prog (Open  Closed  Current 
             Deslist ;список дочерних вершин;
             Reflist ;список указателей;
             Depth ;глубина текущей вершины;)
 ;Шаг 1:;   (setq Open (list (list 'S0  StartState  0
                                 (EST (list StartState 0)))))
 ;Шаг 2:; НS(cond((null Open) (return())))
 ;Шаг 3:;   (setq Current (car Open))
            (setq Open (cdr Open))
            (setq Closed (cons Current Closed))
            (setq Depth (caddr Current))
 ;Шаг 4:;   (cond((IS_GOAL Current)
                  (return (SOLUTION Current Reflist))))
 ;Шаг 5:;   (setq Deslist (OPENING Current))
 ; Исключение повторных вершин-состояний; 
            (setq Deslist (RETAIN_NEW Deslist))
            (cond((null Deslist) (go НS) ))
 ;Шаг 6:;   (setq Open (MERGE (SORT(ADD_DEPTH_EST(add1 Depth) Deslist))
                              Open))
            (setq Reflist(append(CONNECT Deslist Current)
                                 Reflist))
            (go HS) ))

Данная функция использует вспомогательные функции OPENING, SOLUTION, IS_GOAL, CONNECT, EST (которые зависят от конкретной поисковой задачи), а также три вспомогательные функции: RETAIN_NEW, ADD_DEPTH_EST и MERGE.
Вспомогательная функция RETAIN_NEW оставляет в списке дочерних состояний Dlist только те, которые не порождались ранее – тем самым исключается зацикливание при поиске в произвольном графе. Вспомогательная функция SORT упорядочивает (по неубыванию эвристической оценки) список дочерних вершин, к элементам которого добавлена информация о глубине в дереве поиска и об оценке. Определения этих двух функций мы не рассматриваем.
   	Функция ADD_DEPTH_EST устанавливает глубину дочерних вершин и вычисляет их эвристическую оценку:
   (defun ADD_DEPTH_EST (Dn Slist)
      (cond((null Slist) ())
          (t (cons(list (caar Slist) (cadar Slist) Dn
                     (EST(list (cadar Slist) Dn)) )
                  (ADD_DEPTH_EST Dn (cdr Slist)) ) )) )
Функция MERGE выполняет слияние двух упорядоченных (по неубыванию эвристической оценки) списков состояний в результирующий упорядоченный список:
   (defun MERGE (L1 L2)
      (cond((null L1) L2)
           ((null L2) L1)
           ((gt (car (cdddar L1)) (car (cdddar L2)))
                (cons(car L2) (MERGE L1 (cdr L2))))
           (t   (cons(car L1) (MERGE (cdr L1) L2))) ))
Игра в восемь (Лисп)

Граф-пространство состояний для головоломки-игры в восемь достаточно велик (в игре в пятнадцать фишек он на порядок больше), поэтому хотя в принципе применимы алгоритмы слепого поиска, предпочтителен все же эвристический поиск. Опишем нужные для HEURISTIC_SEARCH вспомогательные лисп-функции:  IS_GOAL, EST, OPENING, SOLUTION, CONNECT - для игры в восемь. Состояние задачи (конфигурация игры) представляется списком из следующих элементов: 
•	идентификатор состояния (используются атомы S1, S2, S3, … , генерируемые встроенной лисп-функцией gensym); 
•	собственно описание состояния – список из номеров фишек, записанных последовательно по рядам квадрата;
•	число-глубина состояния-вершины в дереве перебора;
•	числовая эвристическая  оценка состояния.
В описание состояния включается также – в качестве первого элемента списка – обозначение того оператора движения пустой клетки, который привел к данному состоянию. Этот элемент нужен, чтобы  исключить тривиальные повторы состояний при раскрытии вершин. Операторы будут обозначаться соответственно именами-атомами right, left, up, down; а "пустышка" (пустая клетка) – символом  #. Отметим, что эвристическая оценка используется только в алгоритме эвристического перебора, а глубина вершины –  в алгоритмах эвристического перебора и ограниченного перебора вглубь. 
Для примера, приведенного на рис. 1 в основной части текста  День 10, лекции № 19, № 20, начальное состояние S0 имеет такой вид: (? 2 8 3 1 6 4 7 # 5). Символ «?» означает, что оператора, который привел к данному состоянию, нет. При обращении к функции HEURISTIC_SEARCH с таким параметром на Шаге 1 в описание состояния S0 будут добавлены: этот идентификатор, информация о глубине (0) и эвристической оценке (4), затем будет сформирован список Open:
((S0 (? 2 8 3 1 6 4 7 5 #) 0 4))
Дочерние вершины S0:
(S1 ('right 2 8 3 1 6 4 7 5 #))
(S2 ('left  2 8 3 1 6 4 # 7 5))
(S3 ('up    2 8 3 1 # 4 7 6 5))
будут построены (именно в таком порядке) на Шаге 5 функцией OPENING. Список этих вершин станет значением переменной Deslist.
На шаге 6 в эти описания будет добавлена информация о глубине вершин (1) и их эвристических оценках (6, 6, 4) – в функции ADD_DEPTH_EST.
Описанные ниже лисп-функции для игры в восемь пригодны и для игры в пятнадцать, так как размер стороны игрового квадрата, равный 3, используется в них как глобальная переменная (переменная Size). Другая глобальная переменная (Goalstate), хранит описание целевого состояния (без идентификатора, глубины и  эвристической оценки). Значение оценочной функции EST –  сумма числа фишек, стоящих не на «своих» местах,  и длины пути  (глубины) оцениваемого состояния в дереве поиска.
   
     (defun IS_GOAL(State)
            (equal (cdadr State) Goalstate ))

     (defun EST (S)
        (prog(Len G  N  E1 E2)
            (setq Len (cadr S)) (setq N 0)
            (setq S (cdar S)) (setq G Goalstate)
     ;одновременный просмотр списков-описаний;
     ;     заданного и целевого состояний;
         ES (cond((null S) (return (+ (- N 1) Len)) ))
            (setq E1 (car S)) (setq S (cdr S))
            (setq E2 (car G)) (setq G (cdr G))
            (cond((neq E1 E2) (setq N (add1 N))
                 ((eq  E1 '#) (setq N (add1 N)))
            (go ES) ))

   (defun OPENING (State)
      (prog(Op St  Dlist K  I J El)
    ; выделение составных элементов описания состояния;
          (setq St (cadr State))
          (setq Op (car St))  (setq St (cdr St))
          (setq State St) (setq K 0)
    ; поиск порядкового номера К "пустышки" в списке;
       OP (setq El (car St))
          (setq K (add1 K))
          (cond ((neq El '#) (setq St(cdr St)) (go OP) ))
    ; вычисление номера ряда и номера столбца "пустышки";
          (setq I(add1(mod K Size))) (setq J (rem K Size))
    ; поочередно проверка возможности движения «пустышки»;
    ; вправо/влево/вверх/вниз; за счет анализа оператора Op;
    ; исключаем в дереве поиска тривиальные циклы, т.е. возврат;
    ; после применения двух операторов в исходное состояние;
          (cond((and (neq Op 'left) (< J Size))
                    (ADD_STATE 'right K (add1 K)) ))
          (cond((and (neq Op 'right) (> J 1))
                    (ADD_STATE 'left K (sub1 K)) ))
          (cond((and (neq Op 'down) (> I 1))
                    (ADD_STATE 'up K (- K Size)) ))
          (cond((and (neq Op 'up) (< I Size))
                    (ADD_STATE 'down K (+ K Size)) ))
          (return Dlist) ))

При раскрытии используется вспомогательная функция ADD_STATE, добавляющая в список дочерних вершин список-описание новой вершины из 2 элементов: идентификатора этой вершины (его генерирует функция gensym) и списка номеров фишек. В ADD_STATE применяется  встроенная лисп- функция NTH, выбирающая из заданного списка элемент с указанным порядковым номером.
   (defun  ADD_STATE (Op K1 K2)
    (push(list(gensym)
          (cons Op
           (cond((< K1 K2)
                 (EXCHANGE State 1 '# K1 (NTH K2 State)K2))
            (t (EXCHANGE State 1(NTH K2 State)K2 '# K1))) ))
          Dlist))

Рекурсивная функция EXCHANGE, используемая в ADD_STATE, формирует новое состояние игры путем перестановки заданных элементов исходного состояния-списка List (переменная K служит для просмотра  этого списка, при обращении к функции ее значение равно 1).
   (defun EXCHANGE (List K Elem1 K1 Elem2 K2)
     (cond((eql K K1) (cons Elem2
            (EXCHANGE(cdr List)(add1 K)Elem1 K1 Elem2 K2) ))
          ((eql K K2)(cons Elem1 (cdr List)) )) )

Функция CONNECT формирует список указателей от текущей вершины-состояния Curr  к заданным (в списке Dlist) дочерним вершинам-состояниям. Каждый указатель есть трехэлементный список из идентификатора родительской вершины, идентификатора дочерней вершины и названия связывающего их оператора.
   (defun CONNECT (Dlist Curr)
      (prog (D Di Ci Rlist)
        C (setq D (car Dlist)) (setq Dlist (cdr Dlist))
          (setq Di (car D))  (setq Ci (car Curr))
          (setq Rlist(cons (list Ci Di (caadr D))Rlist))
          (cond ((null Dlist) (return Rlist) ))
          (go C) ))
Функция SOLUTION, выделяя решающий путь, строит  последовательность (названий) операторов, преобразующих начальное состояние в целевое (ее аргумент Reflist – список всех указателей-связей между состояниями). Для поиска указателя к очередной вершине решающего пути функция использует  вспомогательную функцию LOOK_FOR . 
   (defun SOLUTION (Goal Reflist)
     (prog (Sollist ;список, в котором строится решение;
 Gi Edge)
         (setq Gi (car Goal))
       S (cond((eq Gi 'S0) (return Sollist) ))
         (setq Edge (LOOK_FOR Gi Reflist))
         (setq Sollist (cons(caddr Edge) Sollist))
         (setq Gi (car Edge))
         (go S) ))

   (defun LOOK_FOR (Id List)
         (cond((null List) (quote error))
              ((eq ID (cadar List)) (car List))
              (t(LOOK_FOR Id (cdr List)) )) )

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

   (prog(Goalstate Initstate Size)
         (setq *gensym-prefix* 'S)
         (setq *gensym-count* 1)
         (setq Size 3)
         (setq Goalstate '(1 2 3 8 # 4 7 6 5))
         (setq Initstate '(? 2 8 3 1 6 4 7 # 5))
         (HEURISTIC_SEARCH Initstate))

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

Поиск вглубь на Лиспе
Лисп-функция LIMITED_DEPTH_SEARCH поиска вглубь имеет два аргумента: кроме начального состояния StartState в число ее аргументов включена граничная глубина LimDepth. Предполагается, что в каждом списке-описании состояния, кроме идентификатора состояния и собственно описания состояния задачи, содержится также третий элемент – глубина этого состояния-вершины в дереве поиска. Проверка на окончание алгоритма (шаг 5 базового алгоритма), для упрощения программы производится в середине цикла. 

 (defun LIMITED_DEPTH_SEARCH (StartState LimDepth)
  (prog (Open Closed Current
         Deslist ;список дочерних вершин;
         Reflist ;список указателей;
         Depth   ;глубина текущей вершины; )
 ;Шаг 1: занесение начальной вершины (ее глубина равна 0):;
 ;в список нераскрытых вершин:;
          (setq Open (list (list 'S0 StartState 0)))
 ;Шаг 2:;
       LS (cond ((null Open) (return ())))
 ;Шаг 3:; (setq Current (car Open))
          (setq Open (cdr Open))
          (setq Closed (cons Current Closed))
 ;Определение глубины текущей вершины:;
          (setq Depth (caddr Current))
          (cond ((IS_GOAL Current) ;/Шаг 5/;
                 (return (SOLUTION Current Reflist))))
 ;Шаг 3’:;(cond ((eql Depth LimDepth) (go LS)))
 ;Шаг 4:Раскрытие вершины, исключение повторных вершин и;
 ; модификация списков указателей и нераскрытых вершин:;
          (setq Deslist (OPENING Current))
          (setq Deslist (RETAIN_NEW Deslist))
          (cond ((null Deslist) (go LS)))
          (setq Open (append (ADD_DEPTH (add1 Depth) Deslist) Open))
          (setq Reflist (append (CONNECT Deslist Current) Reflist))
          (go LS) ))

Эта функция, как и функция эвристического поиска HEURISTIC_SEARCH, использует вспомогательные функции OPENING, SOLUTION, IS_GOAL, CONNECT (которые зависят от конкретной поисковой задачи), а также вспомогательные функции: RETAIN_NEW и ADD_DEPTH (упрощенный вариант функции ADD_DEPTH_EST).

Поиск вглубь на Плэнере
Плэнер-функция DEРTH_FIRST_SEARCH выполняет поиск вглубь от заданного состояния St, но без ограничения глубины (чтобы ограничить глубину, необходимо добавить в эту функцию дополнительный аргумент – граничную глубину, и несколько простых действий). Функция использует встроенный бэктрекинг языка Плэнер.
Значением этой функции является список всех состояний-вершин, лежащих на решающем пути от St до целевой вершины. Как и в случае реализации программ поиска на Лиспе, вспомогательные функции OPENING и IS_GOAL зависят от конкретной решаемой задачи: первая реализует раскрытие заданной вершины-аргумента и выдает как свое значение список дочерних вершин; вторая является предикатом, проверяющим, является ли  исследуемая вершина-аргумент целевой.

[define DEРTH_FIRST_SEARCH (lambda (St)
   [prog (Dst  очередная раскрываемая вершина;
          Reslist список, в котором строится решающий путь;)
     [set Dst .St] [set Reslist (.St)]
  DS [set Dst [among [OPENING .Dst]]]
     [cond ([memb .Dst .Reslist] [fail])]
     [set Reslist (!.Reslist .Dst)]
     [cond ([IS_GOAL .Dst] [return .Reslist])
           (t [go DS])] ])]

Из программных средств управления бэктрекингом (напомним, что в языке Плэнер он называется режимом возвратов) в приведенном тексте используется только функция among, организующая точку выбора альтернатив (развилку). В соответствующей строке программы с меткой DS, являющейся началом внутреннего цикла, раскрывается очередная вершина, из получившихся дочерних вершин образуется развилка (точка бэктрекинга) и выбирается одна из вершин развилки. Затем проверяется,  содержится ли выбранная вершина-состояние в списке Reslist, и если это не так, то она добавляется в этот список, где последовательно формируется решающий путь. Далее проверяется, не является ли выбранная вершина целевой, и в зависимости от результата этой проверки либо поиск успешно заканчивается, либо производится переход на начало цикла – для того, чтобы, раскрывая текущую вершину, идти вглубь дерева поиска (каждый шаг цикла соответствует шагу вниз в дереве поиска). 
В принципе алгоритм поиска вглубь можно было запрограммировать без цикла, с использованием рекурсии. В этом случае развилка бы ставилась при каждом обращении к рекурсивной функции поиска, и каждое рекурсивное обращение соответствовало бы шагу вниз по дереву перебора.
Отметим, что плэнерская функция fail, инициирующая автоматический процесс возврата, в рассмотренной функции DEРTH_FIRST_SEARCH применяется только для предотвращения зацикливания, когда порожденная дочерняя вершина уже содержится в списке Reslist. В этом случае происходит возврат к текущей развилке для выбора следующей дочерней вершины. Возврат же к предыдущей по времени возникновения развилке (т.е. точке бэктрекинга, организованной на предыдущем шаге цикла и лежащей на один шаг вверх в дереве перебора) инициируется самой функцией among в двух следующих случаях. Во-первых, когда список порожденных дочерних вершин оказался пуст, а во-вторых, когда уже перепробованы все установленные в развилке варианты (дочерние вершины) и все они оказались неуспешными.
Поскольку глубина перебора в функции DEРTH_FIRST_SEARCH никак не ограничена, то окончание работы алгоритма гарантировано только в случае поиска в ограниченных пространствах состояний. Если просматриваемое пространство не содержит целевого состояния, результатом этой функции будет неуспех, и процесс возврата вернет управление к последней по времени развилке, возникшей перед входом в функцию DEРTH_FIRST_SEARCH.
Если сравнивать эту плэнер-функцию с основной лисп-функцией для эвристического поиска, то нетрудно заметить, что встроенный механизм бэктрекинга позволяет обойтись без многих вспомогательных структур – списков открытых и закрытых вершин, списка указателей между вершинами и др., а также без операций по их модификации. Не используются также вспомогательные функции SOLUTION, CONNECT.
Кроме достоинств, заключающихся в упрощении программирования слепого перебора вглубь, встроенный бэктрекинг имеет и недостатки, главные из которых – «жесткость» и неэффективность. 
Встроенный механизм возвратов языка Плэнер не облегчает программирование других разновидностей поиска – перебора вширь и эвристического поиска, и оно выполняется обычно без использования этого механизма, т.е. почти так же, как и в языках программирования без встроенного бэктрекинга. Что же касается языка Пролог, в котором по существу нельзя отказаться от встроенного бэктрекинга, то по этой причине запрограммировать на нем алгоритм поиска вширь, как и алгоритм эвристического поиска, даже сложнее, чем в обычных языках без встроенного бэктрекинга.

Поиск на игровых деревьях

Деревья игры. Поиск выигрышной стратегии
Будем рассматривать класс игр двух лиц с полной информацией. В таких играх участвуют два игрока, которые поочередно делают свои ходы. В любой момент игры каждому игроку известно все, что произошло в игре к этому моменту и что может быть сделано в настоящий момент. Игра заканчивается либо выигрышем одного игрока (и проигрышем другого), либо ничьей. 
Таким образом, в рассматриваемый класс не попадают игры, исход которых зависит хотя бы частично от случая  большинство карточных игр, игральные кости, «морской бой» и проч. Тем не менее класс достаточно широк: в него входят такие игры, как шахматы, шашки, реверси, калах, крестики-нолики и другие игры. 
Для формализации и изучения игровых стратегий в классе игр с полной информацией может быть использован подход, основанный на редукции задач. При этом подходе должны быть определены следующие составляющие: форма описания задач и подзадач; операторы, сводящие задачи к подзадачам; элементарные задачи; а также задано описание исходной задачи.
Наиболее интересна задача поиска выигрышной стратегии для одного из игроков, отправляясь от некоторой конкретной конфигурации (позиции) игры (не обязательно начальной). При использовании подхода, основанного на редукции задач, выигрышная стратегия ищется  в процессе доказательства того, что игра может быть выиграна. Аналогично, поиск ничейной стратегии, исходя из некоторой конкретной позиции, ведется в процессе доказательства  того, что игра может быть сведена к ничьей.
Ясно, что описание решаемой задачи должно содержать описание конфигурации игры, для которой ищется нужная стратегия. Например, в шашках игровая позиция включает задание  положений на доске всех шашек, в том числе дамок. Обычно описание конфигурации содержит также указание, кому принадлежит следующий ход.
Пусть именами игроков будут ПЛЮС и МИНУС. Будем использовать следующие обозначения:
XS или YS  некоторая конфигурация игры, причем индекс S принимает значения  + или , указывая тем самым, кому принадлежит следующий ход (т.е. в конфигурации X+ следующий ход должен делать игрок ПЛЮС, а в X – игрок МИНУС);
W(XS)  задача доказательства того, что игрок ПЛЮС может выиграть, исходя из позиции XS;
V(XS)  задача доказательства того, что игрок МИНУС может выиграть, отправляясь от позиции XS.
Рассмотрим сначала игровую задачу W(XS). Операторы сведения  (редукции) этой задачи к подзадачам определяются исходя из ходов, допустимых в проводимой игре:
*	 Если в некоторой конфигурации X+ очередной ход делает игрок ПЛЮС, и имеется N допустимых ходов, приводящих соответственно к конфигурациям X1, X2, . . . XN , то для решения задачи W(X+) необходимо решить по крайней мере одну из подзадач W(Xi). Действительно, так как ход выбирает игрок ПЛЮС, то он выиграет игру, если хотя бы один из ходов ведет к выигрышу  см. рис. 1(а).
*	 Если же в некоторой конфигурации Y ход должен сделать игрок МИНУС, и имеется K допустимых ходов, приводящих к конфигурациям Y1+ , Y2+ , . . . YK+, то для решения задачи W(Y) требуется решить каждую из возникающих подзадач W(Yi+). Действительно, поскольку ход выбирает МИНУС, то ПЛЮС выиграет игру, если выигрыш гарантирован ему после любого хода противника  см. рис. 1(б).

Последовательное применение данной схемы редукции к исходной конфигурации игры порождает И/ИЛИ-дерево (И/ИЛИ-граф), которое называют деревом (графом) игры. Дуги игрового дерева соответствуют ходам игроков, вершины  конфигурациям игры, причем листья дерева  это позиции, в которых игра завершается выигрышем, проигрышем или ничьей. Часть листьев являются заключительными вершинами, соответствующими элементарным задачам  позициям, выигрышным для игрока ПЛЮС. Заметим, что для конфигураций, где ход принадлежит ПЛЮСу, в игровом дереве получается ИЛИ-вершина, а для позиций, в которых ходит МИНУС, получается И-вершина.
Цель построения игрового дерева или графа  получение решающего поддерева для задачи W(XS), показывающего, как игрок ПЛЮС может выиграть игру из позиции XS независимо от ответов противника. Для этого могут быть применены разные алгоритмы поиска на И/ИЛИ-графах. Решающее дерево заканчивается на позициях, выигрышных для ПЛЮСа, и содержит полную стратегию достижения им выигрыша: для каждого возможного продолжения игры, выбранного противником, в дереве есть ответный ход, приводящий к победе.
Для задачи V(XS) схема сведения игровых задач к подзадачам аналогична: ходам игрока ПЛЮС будут соответствовать И-вершины, а ходам МИНУСа  ИЛИ-вершины, заключительные же вершины будут соответствовать позициям, выигрышным для игрока МИНУС.
Конечно, подобная редукция задач применима и в случае, когда нужно доказать существование ничейной стратегии в игре. При этом определение  элементарной задачи должно быть соответствующим образом изменено.
Рассмотрим в качестве иллюстрации простую игру, называемую «последний проигрывает». Два игрока поочередно берут по одной или две монеты из кучки, первоначально содержащей семь монет. Игрок, забирающий последнюю монету, проигрывает. 
На рис.2 показан полный граф игры для задачи V(7+), жирными дугами на нем выделен решающий И/ИЛИ-граф, который доказывает, что второй игрок (т.е. игрок МИНУС, начинающий вторым), всегда может выиграть. Конфигурация игры описана как число оставшихся в текущий момент монет, также указание, кому принадлежит следующий ход. Заключительные вершины, соответствующие элементарной задаче V(1+), т.е. выигрышу игрока МИНУС, в графе подчеркнуты. 
Представленная в решающем графе выигрышная стратегия может быть сформулирована словесно так: если в очередном ходе игрок ПЛЮС берет одну монету, то в следующем ходе МИНУС должен взять две, а если ПЛЮС берет две монеты, то МИНУС должен забрать одну. Отметим, что для аналогичной задачи W(7+) решающий граф построить не удастся (начальная вершина неразрешима); таким образом, у игрока ПЛЮС нет выигрышной стратегии в этой игре.

В большинстве игр, представляющих интерес, таких как шашки и шахматы, построить полные решающие деревья и найти полные игровые стратегии не представляется возможным. Например, для шашек число вершин в полном игровом дереве оценивается величиной порядка 1040, и просмотреть такое дерево практически нереально. Алгоритмы же упорядоченного перебора с применением эвристик не настолько уменьшают просматриваемую часть дерева игры, чтобы дать существенное, на несколько порядков, сокращение времени поиска.
Тем не менее для неполных игр в шашки и шахматы (например, для эндшпилей), так же как и для всех несложных игр, таких как  «крестики-нолики» на фиксированном квадрате небольшого размера, можно успешно применять алгоритмы поиска на И/ИЛИ-графах, позволяющие обнаруживать выигрышные и ничейные игровые стратегии.
Рассмотрим, к примеру, игру «крестики-нолики» на квадрате 33. Игрок ПЛЮС ходит первым и ставит крестики, а МИНУС  нолики. Игра заканчивается, когда составлена либо строка, либо столбец, либо диагональ из крестиков (в этом случае выигрывает ПЛЮС) или ноликов (выигрывает МИНУС). Оценим размер полного дерева игры: начальная вершина имеет 9 дочерних вершин, каждая из которых в свою очередь  8 дочерних; каждая вершина глубины 2 имеет 7 дочерних и т.д. Таким образом, число концевых вершин в дереве игры равно 9!=362880, но многие пути в этом дереве обрываются раньше на заключительных вершинах. Значит, в этой игре возможен полный просмотр дерева и нахождение выигрышной стратегии. Однако ситуация изменится при существенном увеличении размеров квадрата или же в случае неограниченного поля игры.
В таких случаях, как и во всех сложных играх вместо нереальной задачи поиска полной игровой стратегии решается, как правило, более простая задача  поиск для заданной позиции игры достаточно хорошего первого хода. 

Минимаксная процедура
С целью поиска достаточно хорошего первого хода просматривается обычно часть игрового дерева, построенного от заданной конфигурации. Для этого применяется один из переборных алгоритмов (в глубину, в ширину или эвристический) и некоторое искусственное окончание перебора вершин в игровом дереве: например, ограничивается время перебора или же глубина поиска.
В построенном таким образом частичном дереве игры оцениваются вершины, и по полученным оценкам определяется наилучший ход от заданной игровой конфигурации. При этом для оценивания концевых вершин (листьев) полученного дерева используется так называемая статическая оценочная функция, а для оценивания остальных вершин – корневой (начальной) и промежуточных между корневой и концевыми вершинами – используется так называемый минимаксный принцип.
Статическая оценочная функция, будучи применена к некоторой вершине-конфигурации игры, дает числовое значение, оценивающее различные достоинства этой игровой позиции. Например, для шашек могут учитываться такие (статические) элементы конфигурации игры, как продвинутость и подвижность шашек, количество дамок, контроль ими центра и проч. По сути, статическая функция вычисляет эвристическую оценку шансов на выигрыш одного из игроков. Для определенности будем рассматривать задачу выигрыша игрока ПЛЮС и соответственно поиска достаточно хорошего его первого хода от заданной конфигурации.
Будем придерживаться общепринятого соглашения, по которому значение статической оценочной функции тем больше, чем больше преимуществ имеет игрок ПЛЮС (над игроком МИНУС) в оцениваемой позиции. Очень часто оценочная функция выбирается следующим образом:
•	статическая оценочная функция положительна в позициях, где  игрок ПЛЮС имеет преимущества;
•	статическая оценочная функция отрицательна в конфигурациях, где МИНУС имеет преимущества;
•	статическая оценочная функция близка к нулю в позициях, не дающих преимущества ни одному из игроков.
Например, для шашек в качестве простейшей статической функции может быть взят перевес в количестве шашек (и дамок) у игрока ПЛЮС. Для игры «крестики-нолики» на фиксированном квадрате возможна такая статическая оценочная функция:
   +		если P есть позиция выигрыша игрока ПЛЮС
E(P) =  	   		если P есть позиция выигрыша МИНУСа
  (NL+ +NC+ +ND+ )(NL +NC +ND) 	в остальных случаях
где 	+  очень большое положительное число;
  очень маленькое отрицательное число;
NL+, NC+, ND+   соответственно число строк, столбцов и диагоналей, «открытых» для игрока ПЛЮС (т.е. где он еще может поставить три выигрышных крестика подряд),
а   NL, NC, ND  аналогичные числа для игрока МИНУС. 
На рис.3 приведены две игровые позиции (на квадрате 44) и соответствующие значения статической оценочной функции.

Подчеркнем, что с помощью статической оценочной функции оцениваются только концевые вершины дерева игры, для оценок же промежуточных вершин, как и начальной вершины, используется минимаксный принцип, основанный на следующей простой идее. Если бы игроку ПЛЮС пришлось бы выбирать один из нескольких возможных ходов, то он выбрал бы наиболее сильный ход, т.е. ход, приводящий к позиции с наибольшей оценкой. Аналогично, если бы игроку МИНУС пришлось бы выбирать ход, то он выбрал бы ход, приводящий к позиции с наименьшей оценкой. 
Сформулируем теперь сам минимаксный принцип:
▪ ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;
▪ И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.
Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определения наилучшего (более точно, достаточно хорошего) хода игрока исходя из заданной конфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, что игрок ПЛЮС ходит первым (т.е. начальная вершина есть ИЛИ-вершина). Основные этапы этой процедуры таковы:
1.	Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило, алгоритмом поиска вглубь) от исходной позиции S до глубины N;
2.	Все концевые вершины полученного дерева, т.е. вершины, находящиеся на глубине N, оцениваются с помощью статической оценочной функции;
3.	В соответствии с минимаксным принципом вычисляются оценки всех остальных вершин: сначала вычисляются оценки вершин, родительских для концевых, затем родительских для этих родительских вершин и так далее; таким образом оценивание вершин происходит при движении снизу вверх по дереву поиска  до тех пор, пока не будут оценены вершины, дочерние для начальной вершины, т.е. для исходной конфигурации S;
4.	Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который к ней ведет, и есть искомый наилучший ход в игровой конфигурации S.

На рис.4 показано применение минимаксной процедуры для дерева игры, построенного до глубины N=3. Концевые вершины не имеют имен, они обозначены своими оценками  значениями статической оценочной функции. Числовые индексы имен остальных вершин показывают порядок, в котором эти вершины строились алгоритмом перебора вглубь. Рядом с этими вершинами находятся их минимаксные оценки, полученные при движении в обратном (по отношению к построению дерева) направлении. Таким образом, наилучший ход – первый из двух возможных.
На рассматриваемом игровом дереве выделена ветвь (последовательность ходов игроков), представляющая так называемую минимаксно-оптимальную игру, при которой каждый из игроков всегда выбирает наилучший для себя ход. Заметим, что оценки всех вершин этой ветви дерева совпадают, и оценка начальной вершины равна оценке концевой вершины этой ветви.
В принципе статическую оценочную функцию можно было бы применить и к промежуточным вершинам, и на основе этих оценок осуществить выбор наилучшего первого хода, например, сразу выбрать ход, максимизирующий значение статической оценочной функции среди вершин, дочерних к исходной. Однако считается, что оценки, полученные с помощью минимаксной процедуры, есть более надежные меры относительного достоинства промежуточных вершин, чем оценки, полученные прямым применением статической оценочной функции. Действительно, минимаксные оценки основаны на просмотре игры вперед и учитывают разные особенности, которые могут возникнуть в последующем, в то время как простое применение оценочной функции учитывает лишь свойства позиции как таковой. Это отличие статических и минимаксных оценок существенно для «активных», динамичных позиций игры (например, в шашках и шахматах к ним относятся конфигурации, в которых возникает угроза взятия одной или нескольких фигур). В случае же так называемых «пассивных», спокойных позиций статическая оценка может мало отличаться от оценки по минимаксному принципу.

Альфа-бета процедура
Минимаксная процедура организована таким образом, что процесс построения частичного дерева игры отделен от процесса оценивания вершин. Такое разделение приводит к тому, что в целом минимаксная процедура  неэффективная стратегия поиска хорошего первого хода. Чтобы сделать процедуру более экономной, необходимо вычислять статические оценки концевых вершин и минимаксные оценки промежуточных вершин одновременно с построением игрового дерева. Этот путь приводит к так называемой альфа-бета процедуре поиска наилучшего первого хода от заданной позиции, при этом можно добиться существенного сокращения вычислительных затрат, прежде всего, времени вычисления статических оценок. В основе сокращения поиска лежит достаточно очевидное соображение: если есть два варианта хода одного игрока, то худший в ряде случаев можно сразу отбросить, не выясняя, насколько в точности он хуже.
Рассмотрим сначала идею работы альфа-бета процедуры на примере игрового дерева, приведенного на рис.19. Дерево игры строится до глубины N=3 алгоритмом перебора вглубь. Причем сразу, как это становится возможным, вычисляются не только статические оценки концевых вершин, но и предварительные минимаксные оценки промежуточных вершин. Предварительная оценка определяется соответственно как минимум или максимум уже известных к настоящему моменту оценок дочерних вершин. В общем случае, эта оценка может быть получена при наличии оценки хотя бы одной дочерней вершины. В ходе дальнейшего построения дерева игры и получения новых оценок вершин предварительные оценки постепенно уточняются, опять же по минимаксному принципу.
Пусть таким образом построены вершины W1,  W2+ и первые три конечные вершины (листья)  см. рис.5. Эти листья оценены статической функцией, и вершина W2+ получила точную минимаксную оценку 3, а вершина W1  предварительную оценку 3. Далее при построении и раскрытии вершины W3+ статическая оценка первой ее дочерней вершины дает величину 4, которая становится предварительной оценкой самой вершины W3+. Эта предварительная оценка будет потом, после построения второй ее дочерней вершины, пересчитана. Причем согласно минимаксному принципу оценка может только увеличиться (поскольку подсчитывается как максимум оценок дочерних вершин), но даже если она увеличится, это не повлияет на оценку вершины W1, поскольку последняя при уточнении по минимаксному принципу может только уменьшаться (так как равна минимуму оценок дочерних вершин). Следовательно, можно пренебречь второй дочерней вершиной для W3+, не строить и не оценивать ее, поскольку уточнение оценки вершины W3+ не повлияет на оценку вершины W1. Такое сокращение поиска в игровом дереве называется отсечением ветвей.

Продолжим для нашего примера процесс поиска в глубину с одновременным вычислением предварительных (и точных, где это возможно) оценок вершин вплоть до момента, когда построены уже вершины W4 , W5+ и две дочерних последней, которые оцениваются статической функцией. Исходя из оценки первой дочерней вершины начальная вершина W0+, соответствующая исходной позиции игры, к этому моменту уже предварительно оценена величиной 3. Вершина W5+ получила точную минимаксную оценку 3, а ее родительская W4 получила пока только предварительную оценку 3. Эта предварительная оценка вершины W4может быть уточнена в дальнейшем, и в соответствии с минимаксным принципом возможно только ее уменьшение, но это уменьшение не повлияет на оценку вершины W0+, поскольку последняя, опять же согласно минимаксному принципу, может только увеличиваться. Таким образом, построение дерева можно прервать ниже вершины W4, отсекая целиком выходящие из нее вторую и третью ветви (и оставляя ее оценку предварительной).

На этом построение игрового дерева заканчивается, полученный результат  лучший первый ход  тот же самый, что и при минимаксной процедуре. У некоторых вершин дерева осталась неуточненная, предварительная оценка, однако этих приближенных оценок оказалось достаточно для того, чтобы определить точную минимаксную оценку начальной вершины и наилучший первый ход. В то же время произошло существенное сокращение поиска: вместо 17 вершин построено только 11, и вместо 10 обращений к статической оценочной функции понадобилось всего 6.
Обобщим рассмотренную идею сокращения перебора. Сформулируем сначала правила вычисления оценок вершин дерева игры, в том числе предварительных оценок промежуточных вершин, которые для удобства будем называть альфа- и бета-величинами:
•	концевая вершина игрового дерева оценивается статической оценочной функцией сразу, как только она построена;
•	промежуточная вершина предварительно оценивается по минимаксному принципу, как только стала известна оценка хотя бы одной из ее дочерних вершин; каждая предварительная оценка пересчитывается (уточняется) всякий раз, когда получена оценка еще одной дочерней вершины;
•	предварительная оценка ИЛИ-вершины (альфа-величина) полагается равной наибольшей из вычисленных к текущему моменту оценок ее дочерних вершин;
•	предварительная оценка И-вершины (бета-величина) полагается равной наименьшей из вычисленных к текущему моменту оценок ее дочерних вершин.
	Укажем очевидное следствие этих правил вычисления: альфа-величины не могут уменьшаться, а бета-величины не могут увеличиваться.
	Сформулируем теперь правила прерывания перебора, или отсечения ветвей игрового дерева:.
A)	  Перебор можно прервать ниже любой И-вершины, бета-величина которой не больше, чем альфа-величина одной из предшествующих ей ИЛИ-вершин (включая корневую вершину дерева);
B)	 Перебор можно прервать ниже любой ИЛИ-вершины, альфа-величина которой не меньше, чем бета-величина одной из предшествующих ей И-вершин.
При этом в случае А говорят, что имеет место альфа-отсечение, поскольку отсекаются ветви дерева, начиная с ИЛИ-вершин, которым приписана альфа-величина, а в случае В  бета-отсечение, поскольку отсекаются ветви, начинающиеся с бета-величин). 
	Важно, что рассмотренные правила работают в ходе построения игрового дерева вглубь; это означает, что предварительные оценки промежуточных вершин появляются лишь по мере продвижения от концевых вершин дерева вверх к корню и реально отсечения могут начаться только после того, как получена хотя бы одна точная минимаксная оценка промежуточной вершины.
	В рассмотренном примере на рис. 20 первое прерывание перебора было бета-отсечением, а второе  альфа-отсечением. Причем в обоих случаях отсечение было неглубоким, поскольку необходимая для соблюдения соответствующего правила отсечения альфа- или бета-величина находилась в непосредственно предшествующей к точке отсечения вершине. В общем же случае она может находиться существенно выше отсекаемой ветви – где-то на пути от вершины, ниже которой производится отсечение, к начальной вершине дерева, включая последнюю.
	После прерывания перебора предварительные оценки вершин в точках отсечения остаются неуточненными, но, как уже отмечалось, это не препятствует правильному нахождению предварительных оценок всех предшествующих вершин, как и точной оценки корневой вершины и ее дочерних вершин, а значит, и искомого наилучшего первого хода.
На приведенных выше правилах вычисления оценок вершин и выполнения отсечений (всюду, где это возможно) основана альфа-бета процедура, являющаяся более эффективной реализацией минимаксного принципа. Справедливо следующее
Утверждение:
Альфа-бета процедура всегда приводит к тому же результату (наилучшему первому ходу), что и простая минимаксная процедура той же глубины.
	Важным является вопрос, насколько в среднем альфа-бета процедура эффективнее обычной минимаксной процедуры. Нетрудно заметить, что количество отсечений в альфа-бета процедуре зависит от степени, в которой предварительные оценки (альфа- и бета-величины), полученные первыми, аппроксимируют окончательные минимаксные оценки: чем ближе эти оценки, тем больше отсечений и меньше перебор.
Таким образом, эффективность альфа-бета процедуры зависит от порядка построения и раскрытия вершин в дереве игры. Возможен и неудачный порядок просмотра, при котором придется пройти без отсечений через все вершины дерева, и в этом, худшем случае, альфа-бета процедура не будет иметь никаких преимуществ против минимаксной процедуры.
Наилучший случай, т.е. наибольшее число отсечений, достигается, когда при переборе в глубину первой обнаруживается конечная вершина, статическая оценка которой станет в последствии минимаксной оценкой начальной вершины. При максимальном числе отсечений строится и оценивается минимальное число концевых вершин. Показано, что в случае, когда самые сильные ходы всегда рассматриваются первыми, количество концевых вершин глубины N, которые будут построены и оценены альфа-бета процедурой, примерно равно числу концевых вершин, которые были бы построены и оценены на глубине  N/2 обычной минимаксной процедурой. Таким образом, при фиксированном времени и памяти альфа-бета процедура сможет пройти при поиске вдвое глубже по сравнению с обычной минимаксной процедурой.
	В заключение отметим, что статическая оценочная функция и альфа-бета процедура  две непременные составляющие почти всех компьютерных игровых программ (в том числе коммерческих). Часто используются также дополнительные эвристические приемы в самой альфа-бета процедуре:
•	направленное (эвристическое) отсечение неперспективных ветвей: например, построение дерева игры обрывается на «пассивных» позициях, к которым применяется оценочная функция, для «активных» же позиций поиск продолжается дальше, до нужной глубины или даже глубже, поскольку на это можно использовать время, сэкономленное вследствие отсечения ветвей;
•	последовательное углубление, при котором альфа-бета процедура применяется неоднократно: сначала до некоторой небольшой глубины (например, 2), а затем глубина увеличивается с каждой итерацией, причем после каждой итерации выполняется переупорядочение всех дочерних вершин – с тем, чтобы увеличить число отсечений в последующих итерациях;
•	фиксированное упорядочение вершин при спуске-построении дерева вглубь, при котором в первую очередь строится и раскрывается дочерняя вершина, оцениваемая как более перспективная (эта оценка может быть проведена как с помощью статической оценочной функции, так и более простой, хотя и менее надежной эвристической функции);
•	динамическое упорядочение вершин, при котором каждый раз после уточнения минимаксных оценок и проведения отсечений производится переупорядочивание вершин во всем построенном к текущему моменту дереве (с помощью некоторой эвристической функции) и для дальнейшего раскрытия выбирается наиболее перспективная вершина (заметим, что по существу это означает переход от классического перебора вглубь к алгоритму упорядоченного перебора на И/ИЛИ-графах).
Для усиления игры могут быть также использованы библиотеки типовых игровых ситуаций.

Редукция задач
Кроме уже рассмотренного подхода – представления задач в пространстве состояний – для решения ряда задач возможен и другой, более сложный подход. При этом подходе производится анализ исходной задачи с целью выделения такого набора подзадач, решение которых означает решение исходной задачи. Каждая из выделенных подзадач в общем случае является более простой, чем исходная, и может быть решена каким-либо методом, в том числе – с использованием пространства состояний. Но можно продолжить процесс, выделяя последовательно из возникающих задач подзадачи – до тех пор, пока не получим элементарные задачи, решение которых уже известно. Такой путь называется подходом, основанным на сведении задач к подзадачам, или на редукции задач.
Для иллюстрации этого подхода рассмотрим один из вариантов известной головоломки – задачи о пирамидке, или ханойской башне. В ней используются 3 колышка (обозначим их буквами A, B, C) и 3 диска разного диаметра, которые можно нанизывать на колышки через отверстия в центре. В начале все диски расположены на колышке А, причем диски меньшего диаметра лежат на дисках большего диаметра – см. рис. 6 (диски занумерованы в порядке возрастания диаметра). Требуется переместить все диски на колышек С, двигая их по очереди и соблюдая следующие правила. Перемещать можно только самый верхний диск, и нельзя никакой диск класть на диск меньшего размера. На рис.6 показаны начальное и целевое состояния задачи о пирамидке.
Эта задача легко может быть формализована в пространстве состояний: состояние задачи задается списком из трех элементов, каждый из которых указывает местоположение соответствующего диска (первый элемент – первого диска, второй – второго, третий – третьего). Начальное состояние описывается списком (ААА), а целевое – (ССС). При этом предполагается, что если на одном колышке находится более одного диска, то любой больший диск расположен ниже любого меньшего.

Полное пространство состояний задачи о пирамидке включает 27 вершин.
Посмотрим, как можно решить эту задачу методом редукции задач. Ключевая идея состоит в том, что для перемещения всей пирамидки необходимо переложить самый нижний диск 3, а это возможно, только если располагающаяся над ним пирамидка из двух меньших дисков 1 и 2 перенесена на колышек В – см. рис. 7(а). Таким образом, исходную задачу можно свести к следующим подзадачам:
1) 	переместить диски 1 и 2 с колышка А на колышек В ( 1, 2 : А  В);
2) 	переместить диск 3 с колышка А на колышек С ( 3 : А  С);
3) 	переместить диски 1 и 2 с колышка В на колышек С ( 1, 2 : В  С).
На рис. 7(б) показано исходное состояние для третьей задачи.

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

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

И/ИЛИ графы. Решающий граф
Для изображения процесса редукции задач и получающихся при этом альтернативных множеств подзадач используются обычно графоподобные структуры, вершины которых представляют описания задач/подзадач, а дуги связывают любую пару вершин, соответствующих редуцируемой задаче и одной из результирующих подзадач, причем стрелки на дугах указывают направление редукции. Пример такой структуры приведен на рис. 10 (а): задача G может быть решена путем решения либо задач D1 и D2, либо E1, E2 и E3  либо задачи F. При этом ребра, относящиеся к одному и тому же множеству подзадач, связываются специальной дугой. Чтобы сделать такую структуру более наглядной, вводятся дополнительные промежуточные вершины, и каждое множество результирующих задач группируется под своей родительской вершиной. При этом структура на рис.10(а) преобразуется в структуру, изображенную на рис.10(б): для двух из трех альтернативных множеств подзадач добавлены соответственно вершины D и E.

Если считать, что вершины D и E соответствуют описаниям альтернативных путей решения исходной задачи, то вершину G можно назвать ИЛИ-вершиной, так как задача G разрешима или способом D, или способом E, или способом F. Аналогично вершины D и E можно назвать И-вершинами, поскольку каждый из соответствующих им способов требует решения всех подчиненных задач, что и обозначается специальной дугой. По этой причине структуры, подобные структурам, изображенным на рис.9(б) и рис.10, называются И/ИЛИ-графами. 
Если некоторая вершина такого графа имеет непосредственно следующие за ней (дочерние) вершины, то либо все они являются И-вершинами, либо все они – ИЛИ-вершины. Заметим, что если у некоторой вершины И/ИЛИ-графа имеется ровно одна дочерняя вершина, то ее можно считать как И-вершиной, так и ИЛИ-вершиной   как, например, вершину F на рис.9(б) .
На языке И/ИЛИ-графов применение некоторого оператора редукции задачи  будет означать, что сначала будет построена промежуточная И-вершина, а затем непосредственно следующие за ней ИЛИ-вершины подзадач. Исключение составляет случай, когда множество задач состоит только из одного элемента, в этом случае будет образована ровно одна вершина, будем для определенности считать ее ИЛИ-вершиной. 
Вершину И/ИЛИ-графа, соответствующую описанию исходной задачи, будем называть начальной вершиной. Вершины же, которые соответствуют описаниям элементарных задач, будем называть заключительными вершинами. В графе, показанном на рис.10, начальной является вершина P0, а заключительными – вершины P1, P4, P5, P7  и P8 (они изображены жирными кружками).
Поиск, осуществляемый путем перебора вершин графа, применим и в подходе, основанном на редукции задач. Цель поиска на И/ИЛИ-графе – показать, что разрешима исходная задача, т.е. начальная вершина. Разрешимость этой вершины зависит от разрешимости других вершин графа. 

Сформулируем общее рекурсивное определение разрешимости вершины в И/ИЛИ-графе:
•	заключительные вершины разрешимы, так как они соответствуют элементарным задачам;
•	вершина, не являющаяся заключительной и имеющая дочерние И-вершины,  разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин;
•	вершина, не являющаяся заключительной и имеющая дочерние ИЛИ-вершины, разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин.
Если в процессе поиска удалось показать, что начальная вершина разрешима, то это значит, что обнаружено решение исходной задачи, которое заключено в так называемом решающем графе. Решающий граф – это подграф И/ИЛИ-графа, состоящий только из разрешимых вершин и доказывающий разрешимость начальной вершины.

Для И/ИЛИ-графа, изображенного  на рис.10, разрешимыми являются (кроме заключительных) вершины M1, M2, P2, P3. Этот граф содержит два решающих графа: первый состоит из вершин P0, M1, P1, P2 и P5 ; а второй  – из вершин P0, M2, P3, P4  и P5. Заметим, что вершины M3 и P6  не являются разрешимыми (M3 неразрешима в силу неразрешимости вершины P6).

Пример: задача символьного интегрирования
В качестве примера применения метода редукции рассмотрим решение задачи символьного интегрирования, т.е. нахождения неопределенного интеграла F(x)dx. Обычно эта задача решается путем последовательного преобразования интеграла к выражению, содержащему известные табличные интегралы. Для этого используется несколько правил интегрирования, в том числе: правило интегрирования суммы функций, правило интегрирования по частям, правило вынесения постоянного множителя за знак интегрирования, а также применение алгебраических и тригонометрических подстановок и использование различных алгебраических и тригонометрических тождеств. 
Для формализации этой задачи в рамках подхода, основанного на редукции задач, необходимо определить форму описания задач/подзадач, операторы редукции и элементарные задачи. В качестве возможной формы описания задач может быть взята символьная строка, содержащая запись подынтегральной функции и переменной интегрирования (если последняя не фиксирована заранее). Операторы редукции будут основаны, очевидно, на упомянутых правилах интегрирования. Например, правило интегрирования по частям udv = udv  - vdu сводит исходную задачу (неопределенный интеграл в левой части равенства) к двум подзадачам интегрирования (два соответствующих интеграла в правой части равенства).
Заметим, что часть получаемых таким образом операторов редукции (как, например, операторы, соответствующие правилу интегрирования по частям и правилу интегрирования суммы функций), действительно редуцируют исходную задачу и порождают И-вершину в И/ИЛИ-графе, в то время как алгебраические и тригонометрические подстановки и тождества (как, например, деление числителя на знаменатель или дополнение до полного  квадрата) лишь заменяют одно подынтегральное выражение на  другое, порождая, таким образом, ИЛИ-вершины.
Элементарные задачи интегрирования соответствуют табличным интегралам, к примеру,  sin(x)dx =  - cos(x) + C. Отметим, что поскольку каждая из таких табличных формул содержит переменные, на самом деле она является схемой, задающей бесконечное множество элементарных задач.

Особенностью задачи интегрирования является то, что, например, при интегрировании по частям может оказаться несколько способов разбиения исходного подынтегрального выражения на части и соответственно несколько способов применения этого правила интегрирования. Это означает, что в общем случае для одного правила возможно  несколько вариантов редукции задачи, т.е. несколько способов применения одного и того же оператора редукции.
Другая особенность рассматриваемой  задачи  состоит в том, что на каждом шаге процесса редукции применимо обычно большое количество операторов (включая несколько применений одного и того же оператора), и получающийся И/ИЛИ-граф задачи слишком велик даже для несложных задач интегрирования. Поэтому, чтобы сделать поиск на таком графе достаточно эффективным, необходимо как-то ограничивать и/или упорядочивать множество порождаемых при поиске вершин. К примеру, можно упорядочить операторы редукции по степени их полезности, и приписать больший приоритет операторам, соответствующим правилам интегрирования суммы и интегрирования по частям.
На рис.11 показан решающий граф для одной задачи интегрирования. В вершинах графа указаны соответствующие задачи/подзадачи, заключительные вершины заключены в двойные рамки. Решение задачи может быть собрано из содержащейся в графе информации. Оно состоит из следующих шагов:
1.	применения подстановки z=tg(x); 
2.	эквивалентного преобразования подынтегрального выражения;
3.	применения правила интегрирования суммы функций.
При этом одна из трех результирующих подзадач оказывается элементарной, а две остальные решаются за один шаг (первая –  путем вынесения постоянного множителя за знак интеграла, вторая –  применением подстановки z=tg(w) ).
Подход, основанный на редукции задач, применим и имеет преимущества по сравнению с подходом, использующем представление в пространстве состояний, когда получающиеся при редукции подзадачи можно решать независимо друг от друга, как в примере с интегрированием. Впрочем, это условие взаимной независимости результирующих задач можно несколько ослабить. Метод редукции применим также, если решения получающих подзадач зависят друг от друга, но при этом существует такой порядок их редукции, при котором найденные решения одних, более ранних  подзадач не разрушаются при решении других, более поздних – как в головоломке о ханойской башне, в которой важен лишь порядок решения выделяемых подзадач.

Плэнер-алгоритм, реализующий минимаксную процедуру
Рассмотрим сначала написанную на Плэнере функцию MIN_MAX, реализующую минимаксную процедуру. Аргументы этой функции: Instate  исходная позиция игры, для которой ищется наилучший ход; N    глубина поиска, т.е. количество ходов вперед. Вырабатываемое функцией значение  это дочерняя для Instate позиция, соответствующая искомому наилучшему ходу.
[define MIN_MAX (lambda (Instate N)
   [SELECT_MAX [MM_EVALP .Instate  0 T ]] )]
Функция  MIN_MAX использует две вспомогательные функции: SELECT_MAX и MM_EVALP. Первая функция, SELECT_MAX выбирает из своего единственного аргумента-списка, состоящего из позиций и их оценок, позицию с наибольшей оценкой:
[define SELECT_MAX (lambda (List)
  [prog (Elem Max_elem )
      [fin Max_elem .List]
   SM [cond([fin Elem List] [return [2 .Max_elem]])
           ([gt [1 .Elem] [1 .Max_elem]]
              [set Max_elem .Elem]) ]
     [go SM]  ] )]
Функция MM_EVALP с тремя аргументами является главной рекурсивной функцией, оценивающей вершины дерева игры по минимаксному принципу. На каждом шаге рекурсии она оценивает вершину-позицию Position, находящуюся на глубине Depth и имеющую тип Deptype: "ИЛИ" при  Deptype=Т  и  "И" при Deptype=(). Исходная позиция (корневая вершина дерева) имеет тип Т и находится на глубине 0. Значением функции MM_EVALP является либо вычисленная оценка вершины Position (при Depth>0) либо список дочерних для Position позиций с их числовыми оценками (при Depth=0). 
При работе MM_EVALP используются вспомогательные функции, определение которых зависит от конкретной игры: OPENING, вычисляющая для заданной позиции игры список дочерних вершин-позиций, и STAT_EST  статическая оценочная функция. 
[define MM_EVALP (lambda (Position Depth Deptype)
   [prog (D             %дочерняя позиция;
          (Movelist()) %список ходов-позиций);
          Pvalue Dvalue) %оценки текущей и дочерней 
                            позиций;
% 1:установка развилки, включающей все дочерние вершины текущей позиции(список () добавлен в развилку, чтобы "поймать" момент ее закрытия);
    [set D [among (<OPENING .Position> ())]]
% 2: если развилка закрыта - возврат функцией подсчитанной оценки;
    [cond ([empty .D]
            [return [cond ([eq .Depth 0] .Movelist)
                          (t .Pvalue) ]] )]
% 3: вычисление оценки очередной дочерней позиции: либо применение статической функции, либо рекурсивный спуск;
   [cond ([eq .Depth [- .N 1]] 
            [set Dvalue [STAT_EST .D]])
         (t [set Dvalue [MM_EVALP .D
                                [+ 1 .Depth]
                                [not .Deptype]]] )]
% 4:пересчет оценки текущей позиции по минимаксному принципу;
    [cond ([hasval Pvalue] [pset Pvalue
               [cond(.Deptype [max .Pvalue .Dvalue])
                    (t [min .Pvalue .Dvalue]) ]])
          (t [pset Pvalue .Dvalue]) ]
% 5: при необходимости пересчет для исходной позиции списка ходов(дочерних позиций) с их оценками;
  [cond([eq .Depth 0]
         [pset Movelist(!.Movelist (.Dvalue .D)) ])]
% 6: возврат к другой альтернативе развилки;
    [fail]  ])]

Различия и ключевые операторы
В заключение целесообразно обсудить ряд общих идей, на которых может быть основана редукция задач. К их числу  прежде всего относится идея выделения так называемых ключевых операторов и различий состояний. Будем далее предполагать, что задачи и подзадачи описываются в пространстве состояний как тройки вида ( SI , O, SG ), где SI   и SG  – соответственно начальное и целевое состояния, или же  как двойки (SI , SG ), если предполагать неизменным при поиске множество O операторов преобразования состояний. 
	Часто при поиске в пространстве состояний нетрудно обнаружить один оператор, который обязательно должен входить в решение задачи (по сути, применение этого оператора есть необходимый шаг решения этой задачи). Такой оператор и называется ключевым оператором в пространстве состояний. К примеру, в задаче о пирамидке ключевым оператором был оператор переноса на нужный колышек самого большого диска 3.
Ключевой оператор может быть использован для следующего способа сведения исходной задачи к подзадачам. Пусть 
Op –  найденный в пространстве состояний задачи ключевой оператор (OpO) ;
SOp  – множество состояний, к которым применим ключевой оператор Op;
Op(s) – состояние, полученное в результате применения  ключевого оператора Op к состоянию s (s  SOp).
Тогда исходную задачу можно свести к трем подзадачам:
•	первая задача (SI , SOp)  состоит в поиске пути от начального состояния исходной задачи к одному из состояний, к которому применим ключевой оператор Op;
•	вторая задача является элементарной, она заключается в применении этого ключевого оператора;
•	третья задача (Op(s) , SG)  состоит в поиске пути от состояния, полученного применением ключевого оператора,  к целевому состоянию исходной задачи.
Порядок решения перечисленных задач существен (третья задача не может быть решена раньше первой и второй, также как вторая – раньше первой). Для решения первой и третьей задач может быть применен опять метод редукции с помощью ключевого оператора, или же их решение может быть найдено непосредственным поиском в пространстве состояний.
	Для большинства задач не удается всегда однозначно выделить ключевой оператор, гораздо чаще удается найти множество операторов-кандидатов в ключевые (т.е. операторов, с большой вероятностью могущих стать ключевыми). Таким образом, в общем случае необходим процесс перебора операторов-кандидатов, каждый из которых образует свое множество результирующих задач (этот перебор и означает поиск на И/ИЛИ-графе задачи).
Самый важный вопрос при таком способе редукции задач состоит в том, как найти кандидаты в ключевые операторы. Один из способов, предложенных и опробованных впервые в одной из наиболее известных систем искусственного интеллекта “General Problem Solver” - GPS (А.Ньюэлл, Г.Саймон, Дж.Шоу – 1957 г.), заключается в выявлении различий для начального и целевого состояний задачи.	Различие легче всего формализовать как несоответствие различных элементов описаний начального и целевого состояний. 
	К примеру, в задаче об обезьяне и банане различием можно считать неравенство соответствующих элементов списков, описывающих два состояния. Тогда при сравнении состояний (ТО,П,ТЯ,0)  и (ТЯ,П, ТО,1)  выявляются  три различия – соответственно в первых, третьих и четвертых элементах списков.
	С каждым различием в системе GPS был связан один или несколько операторов, призванных  устранять или уменьшать это различие. Эти операторы и являлись по сути кандидатами в ключевые. На каждом этапе работы система определяла различие между текущим состоянием (объектом) задачи и целевым состоянием (объектом), а затем выбирала и пыталась применить оператор для уменьшения найденного различия. В общем случае операторы включали в себя предусловия (условия применимости), выполнение которых было необходимо для их применения, в этом случае GPS сводила исходную задачу к задаче достижения нужного условия.
В задаче об обезьяне и банане естественно связать различия и операторы-кандидаты в ключевые следующим образом:
•	Различие в первом элементе списка-описания состояния (положение обезьяны в плоскости пола) – операторы  Перейти и Передвинуть.
•	Различие во втором элементе (положение обезьяны по вертикали) – оператор  Взобраться.
•	Различие в третьем элементе (положение ящика) – оператор Передвинуть.
•	Различие в четвертом элементе (содержимое руки обезьяны) – оператор Схватить.

Ясно, что для реализации рассмотренных идей в виде алгоритма или программы должна быть, во-первых, специальная процедура сравнения описаний состояний и вычисления различий. Во-вторых, необходима процедура, связывающая ключевые операторы с возможными различиями (в GPS использовалась таблица связей различие-оператор). Последняя процедура должна также устанавливать порядок устранения различий в случаях, когда выявлено несколько различий и возможно применение нескольких ключевых операторов. Различия должны быть упорядочены по степени их существенности, значимости для конечного решения исходной задачи. Система GPS начинала с попытки обработки более серьезных и трудно устранимых различий, переходя затем к более легким.
В задаче об обезьяне и банане приоритет (существенность) различий можно установить, например, следующим образом: различие в четвертом, затем во втором, затем в третьем и первом элементе описания состояния задачи. Такой же приоритет может быть и у  операторов, уменьшающих эти различия.
Важно, что воплощаемая в указанных процедурах информация является специфической, зависящей от конкретной задачи, т.е.  эвристической проблемно-ориентированной информацией. Одной из слабостей применяемого в системе GPS подхода было то, что процедуры определения различий и уменьшающих их операторов должны были быть отдельно реализованы для каждой конкретной задачи (или для очень узкой предметной области, включающей несколько видов задач), в противном случае снижалась эффективность решения задач. 
	Подчеркнем, что основной механизм системы GPS не был проблемно-ориентированным: он представлял собой реализацию универсального эвристического метода решения задач, часто применяемого человеком, и известного как анализ целей и средств (means-ends analysis). Ключевая идея этой эвристики такова:
•	поиск различий между тем, что дано в поставленной задаче, и тем, что надо получить;
•	последовательное устранение найденных различий с помощью подходящих средств–операций.
Работая в соответствии с этой эвристикой, GPS применяла несколько схем редукции задач (Методов), и на основе выявления различий между объектами задачи и применения уменьшающих эти различия операторов рекурсивно формировала систему (дерево) задач-целей (подзадач).

Краткое описание схемы работы системы GPS
Проблемная среда в системе GPS описывается с использованием таких понятий/терминов:
	Объекты (элементы проблемной среды)
	Различия (между Объектами)
	Операторы (способы преобразования Объектов)
	Цель
При планировании решения задачи в системе GPS используются:
Три основных Метода (не зависящих от конкретной предметной области):
1. Преобразовать один Объект в другой: A  →  B
а)	Сравнить A с B, найти D  =  (A  -  B)
	если D  =  0, то FIN (успех)
б)	ПОДЦЕЛЬ: Уменьшить Различие D
	если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с B)  
в)	ПОДЦЕЛЬ: Преобразовать A’  →  B
	если это не удается, то FIN (неудача), иначе FIN (успех)  
2. Уменьшить Различие между двумя Объектами: D  =  (A  -  B)
а)	Найти оператор Q, подходящий для уменьшения Различия D
если это не удается, то FIN (неудача)
б)	Предварительная проверка применимости Оператора 
	если Оператор эту проверку не прошел, то FIN (неудача)
в)	ПОДЦЕЛЬ: Применить Оператор Q  (A), результат A’, FIN (успех)
3. Применить Оператор к Объекту: Q  (A)
а)	Найти D  =  (prec (Q)  -  A)
	если D  =  0, то результат A’’, FIN (успех)
б)	ПОДЦЕЛЬ: Уменьшить Различие D
	если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с prec(Q))  
в)	ПОДЦЕЛЬ: Применить Оператор Q  (A’), результат A’’,
	если это не удается, то FIN (неудача), иначе FIN (успех)  

Для использования системы GPS в конкретной предметной области необходимо описать Объекты этой ПО и множество учитываемых Различий между Операторами, а также установить связи между Различиями и Операторами (для каждого Оператора указать, какие Различия он может устранить). 
Эти связи можно задать с помощью таблицы (демонстрационный пример):

                   Операторы

Различия
	Op1	Op2	Op3	Op4	. . .	OpN	
D1	+						
D2	+		+				
D3		+					
D4		+					
. . . 							
DM			+			+	
Символ «+» в позиции <i, j>, что Opj  может устранить различие Di.

Предметная область (в которой реально проводились эксперименты с системой GPS) – «Преобразование логических выражений»:

Примеры Различий:
D1 – в формуле не хватает символов (добавить символ)
D2 – в формуле есть лишние символы (вычеркнуть символ)
D3 – в формуле другая связка (изменить связку)
D4 – в формуле другой знак выражения (изменить знак)

Примеры Операторов:
Op1 :  A  &  A  →   A;     A  V  A  ↔  A
Op2 :  A  V  B  ↔  (~A  &  ~B)
Op3 :  A  &  B  →   A;     A  &  B  ↔  B [относится только к основному выражению]

Правила предварительной проверки применимости оператора:
•	Одинакова ли главная связка?
•	Не слишком ли «велик» Оператор? { (A  V  B)  &  (A  V  C)  →  A  V  (B  &  C) }
•	Не слишком ли «прост»/неспецифичен Оператор? { A  →  A  &  A }
•	Удовлетворены ли побочные условия? { [относится только к основному выражению] }

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

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

Пример: ПЛАНИРОВАНИЕ ДЕЙСТВИЙ РОБОТА В «МИРЕ КУБИКОВ»

A

B

 C

B

C

A

							Начальное состояние:
CL (C),  CL (B),  ON (C,  A),  ONT (A),  ONT (B),
							HEMP,  HOLD (x)
							Целевое состояние:
							ON (C,  B)  &  ON (A,  C)  [  &  ONT (B)  ]

Сложность достижения «целей»:
HEMP		1
CL (x)		2
ONT (x)	2
HOLD (x)	2
ON (x,  y)	3

Операторы:
Pickup (x)
	prec:	ONT (x),  CL (x),  HEMP
	res–:	ONT (x),  CL (x),  HEMP
	res+:	HOLD (x)

Putdown (x)
	prec:	HOLD (x)
	res–:	HOLD (x)
	res+:	ONT (x),  CL (x),  HEMP

Stack (x, y)
	prec:	HOLD (x),  CL (y)
	res–:	HOLD (x),  CL (y)
	res+:	ON (x, y),  CL (x),  HEMP

Unstack (x, y)
	prec:	ON (x, y),  CL (x),  HEMP	
	res–:	ON (x, y),  CL (x),  HEMP
	res+:	HOLD (x),  CL (y)

Планирование способов достижения целевого состояния: ON (C,  B)  &  ON (A,  C)
Иерархическое планирование:
1.Планированине на высшем (3) уровне сложности:
{ Stack (C,  B),  Stack (A,  C) } – предусловия пока не рассматриваем
2.Учет предусловий (планирование на других уровнях сложности):
HOLD (C),  CL (A) –  res+ оператора Unstack (C, A), CL (B) – выполняется [начальное состояние]
Stack (C,  B)
HOLD (A)	        –  res+ оператора Pickup (A), CL (C) – выполняется [res+ оператора Stack (C,  B)]
Stack (A,  C)
3. Окончательный план: { Unstack (C, A), Stack (C,  B), Pickup (A), Stack (A,  C) }  

ИНТЕЛЛЕКТУАЛЬНЫЕ РОБОТЫ  и  ПРОМЫШЛЕННЫЕ РОБОТЫ
История. «Телетанки» – 30-е гг. ХХ века (предложил  маршал Тухачевский);
Германия (во второй мировой войне) – около 7000 шт. Управление по радио. Проблемы.
Чернобыльская авария. Высокий уровень радиации выдерживали только отечественные роботы.
Наше время. Луноход (часто можно управлять с Земли), Марсоход (более актуально).
Подводные роботы (Балтийское море: разминирование, поиск химического оружия).
Война в Ираке (воздушная разведка – несколько сотен беспилотных ЛА).
Основные военные приложения: разминирование, разведка, санитарная служба (поиск раненых, экстренная медицинская помощь, эвакуация с поля боя).
Прогноз. Через 20 лет роботы – основной вид вооружений.

	В последние годы понятие интеллектуальный робот в какой-то степени вытесняется близким понятием интеллектуальный агент.

Интеллектуальные Агенты
Термин Интеллектуальный Агент, ставший популярным около 10 лет назад, трактуется различными исследователями по-разному. 
Обычно предполагается, что Интеллектуальный Агент:
- действует автономно или совместно с другими компьютерными/интеллектуальными системами;
- выполняет шаблонные предписанные действия и/или действия, требующие активности и учета состояния окружающей среды;
- в той или иной степени способен к обучению, корпоративным действиям; мобилен.

В работах, посвященных Интеллектуальным Агентам, указываются, в частности, следующие сферы их применения (и соответствующие технологии):
агенты, поддерживающие интеллектуальный пользовательский интерфейс;
мульти-агентные системы (и технологии «распределенного искусственного интеллекта»);
мобильные агенты (в том числе реализованные программно), которые могут общаться между собой и перемещаться в своем специфическом окружении (в частности, в компьютерных сетях).

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

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

Реально: неопределенность, мера/степень доверия, мера доверия и выводы меняются в процессе работы.
Немонотонные рассуждения:
Заключения/выводы могут пересматриваться. 
Допускается признание истинности некоторого факта на основе «здравого смысла» (как устроен мир обычно).
Допускается использование неточных и противоречивых данных.

Подходы:
1.Расширение логических формализмов.
Логическая абдукция.
Абдуктивный вывод: P → Q, если имеет место Q, то можно сделать вывод, что имеет место P (Q  P).

Пример:
если двигатель не вращается и фары не горят (Q), то проблема в аккумуляторе или проводке (P)
[это неверно; возможно (но маловероятно), что поврежден стартер и перегорели все электролампы]
< P → Q, Q  P >
Обратное верно:
если проблема в аккумуляторе или проводке (P), то двигатель не вращается и фары не горят (Q)
< P → Q, P  Q >

2.Неточный вывод на основе фактора уверенности / нечеткие рассуждения / теория Демпстера-Шефера

3.Стохастические подходы (основанные на теореме Байеса).
Расчет вероятности верности гипотезы в условиях неполной и/или непредставительной выборки (на основе наблюдений известна лишь часть информации о событиях).

Краткое описание схемы работы системы GPS

Проблемная среда в системе GPS описывается с использованием таких понятий/терминов:
	Объекты (элементы проблемной среды)
	Различия (между Объектами)
	Операторы (способы преобразования Объектов)
	Цель

При планировании решения задачи в системе GPS используются:
Три основных Метода (не зависящих от конкретной предметной области):
1. Преобразовать один Объект в другой: A  →  B
а)	Сравнить A с B, найти D  =  (A  -  B)
	если D  =  0, то FIN (успех)
б)	ПОДЦЕЛЬ: Уменьшить Различие D
	если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с B)  
в)	ПОДЦЕЛЬ: Преобразовать A’  →  B
	если это не удается, то FIN (неудача), иначе FIN (успех)  
2. Уменьшить Различие между двумя Объектами: D  =  (A  -  B)
а)	Найти оператор Q, подходящий для уменьшения Различия D
если это не удается, то FIN (неудача)
б)	Предварительная проверка применимости Оператора 
	если Оператор эту проверку не прошел, то FIN (неудача)
в)	ПОДЦЕЛЬ: Применить Оператор Q  (A), результат A’, FIN (успех)
3. Применить Оператор к Объекту: Q  (A)
а)	Найти D  =  (prec (Q)  -  A)
	если D  =  0, то результат A’’, FIN (успех)
б)	ПОДЦЕЛЬ: Уменьшить Различие D
	если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с prec(Q))  
в)	ПОДЦЕЛЬ: Применить Оператор Q  (A’), результат A’’,
	если это не удается, то FIN (неудача), иначе FIN (успех)  
Для использования системы GPS в конкретной предметной области необходимо описать Объекты этой ПО и множество учитываемых Различий между Операторами, а также установить связи между Различиями и Операторами (для каждого Оператора указать, какие Различия он может устранить). 
Эти связи можно задать с помощью таблицы (демонстрационный пример):

                   Операторы

Различия
	Op1	Op2	Op3	Op4	. . .	OpN	
D1	+						
D2	+		+				
D3		+					
D4		+					
. . . 							
DM			+			+	
Символ «+» в позиции <i, j>, что Opj  может устранить различие Di.
Предметная область (в которой реально проводились эксперименты с системой GPS) – «Преобразование логических выражений»:
Примеры Различий:
D1 – в формуле не хватает символов (добавить символ)
D2 – в формуле есть лишние символы (вычеркнуть символ)
D3 – в формуле другая связка (изменить связку)
D4 – в формуле другой знак выражения (изменить знак)
Примеры Операторов:
Op1 :  A  &  A  →   A;     A  V  A  ↔  A
Op2 :  A  V  B  ↔  (~A  &  ~B)
Op3 :  A  &  B  →   A;     A  &  B  ↔  B [относится только к основному выражению]

Правила предварительной проверки применимости оператора:
•	Одинакова ли главная связка?
•	Не слишком ли «велик» Оператор? { (A  V  B)  &  (A  V  C)  →  A  V  (B  &  C) }
•	Не слишком ли «прост»/неспецифичен Оператор? { A  →  A  &  A }
•	Удовлетворены ли побочные условия? { [относится только к основному выражению] }

Пример: ПЛАНИРОВАНИЕ ДЕЙСТВИЙ РОБОТА В «МИРЕ КУБИКОВ»

A

B

 C

B

C

A

							Начальное состояние:
CL (C),  CL (B),  ON (C,  A),  ONT (A),  ONT (B),
							HEMP,  HOLD (x)
							Целевое состояние:
							ON (C,  B)  &  ON (A,  C)  [  &  ONT (B)  ]

Сложность достижения «целей»:
HEMP		1
CL (x)		2
ONT (x)	2
HOLD (x)	2
ON (x,  y)	3

Операторы:
Pickup (x)
	prec:	ONT (x),  CL (x),  HEMP
	res–:	ONT (x),  CL (x),  HEMP
	res+:	HOLD (x)

Putdown (x)
	prec:	HOLD (x)
	res–:	HOLD (x)
	res+:	ONT (x),  CL (x),  HEMP

Stack (x, y)
	prec:	HOLD (x),  CL (y)
	res–:	HOLD (x),  CL (y)
	res+:	ON (x, y),  CL (x),  HEMP

Unstack (x, y)
	prec:	ON (x, y),  CL (x),  HEMP	
	res–:	ON (x, y),  CL (x),  HEMP
	res+:	HOLD (x),  CL (y)

Планирование способов достижения целевого состояния: ON (C,  B)  &  ON (A,  C)
Иерархическое планирование:
1.Планированине на высшем (3) уровне сложности:
{ Stack (C,  B),  Stack (A,  C) } – предусловия пока не рассматриваем
2.Учет предусловий (планирование на других уровнях сложности):
HOLD (C),  CL (A) –  res+ оператора Unstack (C, A), CL (B) – выполняется [начальное состояние]
Stack (C,  B)
HOLD (A)	        –  res+ оператора Pickup (A), CL (C) – выполняется [res+ оператора Stack (C,  B)]
Stack (A,  C)
3.Окончательный план: { Unstack (C, A), Stack (C,  B), Pickup (A), Stack (A,  C) }  

Экспертные системы

Работы по созданию Экспертных систем (ЭС) - первая попытка практического применения результатов в области Искусственного интеллекта (ИИ).

История: «романтический период» ИИ → серьезные научные исследования → практические задачи.

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

Основные особенности ЭС:
•	ориентированы на решение практических задач в трудноформализуемых узких предметных областях,
•	результаты работы сравнимы с результатами человека-эксперта,
•	«прозрачность» решения,
•	открытая совокупность знаний.

Одна из первых задач - задача Диагностики (выявление причин неправильного функционирования системы). 
Одна из первых ЭС для задачи медицинской диагностики: MYCIN (диагностика бактериальных инфекций).
Одна из первых ЭС в Геологии: PROSPECTOR  - оценка потенциальной рудоносности района
Что может делать СИСТЕМА PROSPECTOR:
•	Беседует с пользователем (экспертом-геологом), употребляя знакомые ему термины.
•	Позволяет пользователю вводить любую информацию о районе в любой момент диалога; учитывает при этом степень уверенности пользователя в достоверности сообщаемых им фактов.
•	Выбирает гипотезу о рудных залежах в районе и затем задает пользователю вопросы с целью либо доказать, либо опровергнуть ее.
•	Перефразирует вопросы, когда пользователь указывает, что они ему непонятны.
•	Может сообщить пользователю, почему ей нужен ответ на конкретный вопрос.
•	Отбрасывает свои гипотезы и выбирает новые на основании ответов пользователя на свои вопросы.
•	Ищет противоречия в ответах пользователя, указывает их и позволяет пользователю изменять и старые, и новые ответы с целью добиться непротиворечивости.
•	Предлагает свои заключения вместе со сводкой соображений, на основании которых она пришла к этим заключениям.

ФРАГМЕНТ ПРОТОКОЛА ДИАЛОГА ПОЛЬЗОВАТЕЛЯ С СИСТЕМОЙ PROSPECTOR.
01.П:  присутствуют дайки (запоминает ЭС: дайки, достоверность = 5)
02.П:  присутствуют меловые диориты (запоминает ЭС: меловые диориты, достоверность = 5)
03.П:  возможно, есть сиенодиорит (запоминает ЭС: сиенодиорит/монцонит, достоверность = 3)
04.П: может быть некоторое количество кварцевого монцонита (запоминает ЭС: кварцевый монцонит, достоверность = 3)
. . .
77:ЭС: на шкале от -5 до +5 уверенность, что имеется месторождение медно-порфировых руд типа А (МПРА), равна 1.683.
Основные заключения в пользу гипотезы:
- Соответствующее геологическое строение региона (достоверность = 3.576).
- Соответствующее петро-тектоническое окружение (достоверность = 3.333).
- Соответствующая интрузивная структура для МПРА (достоверность = 1.683).
Основные наблюдения, поддерживающие гипотезу:
- В исследуемом регионе есть система гранитных интрузий (достоверность = 5.0).
- Наблюдаются измененные породы (достоверность = 5.0)
. . .
Существует еще много других наблюдений в пользу гипотезы. Хотите рассмотреть еще какие-нибудь?
П: нет 

Типичные задачи, решаемые с помощью ЭС:

Интерпретация - описание ситуации по информации, поступающей от датчиков.
	SPE - определение концентрации гамма-глобулина в крови.
Прогноз - определение вероятных последствий заданных ситуаций.
	PLANT/cd - определения потерь урожая от черной совки.
Планирование - определение последовательности действий.
	TATR - планирование авиаударов по аэродромам противника.
Диагностика - выявление причин неправильного функционирования системы.
	MYCIN - диагностика бактериальных инфекций.
Отладка - составление рецептов исправления неправильного функционирования системы.
	ONCOCIN - планирования химиотерапевтического лечения.
Ремонт - выполнение последовательности предписанных исправлений.
	TQMSTUNE - настройка масс-спектрометра.
Проектирование - построение конфигурации объектов при заданных ограничениях.
	XCON (R1) - выбор оптимальной конфигурации аппаратных средств (VAX).
Наблюдение - сравнение результатов наблюдения с ожидаемыми результатами.
	VM - наблюдение за состоянием больного в палате интенсивной терапии.
Обучение - диагностика, отладка и ремонт поведения обучаемого.
	GUIDON - обучение студентов-медиков (антибактериальная терапия).
Управление - управление поведением системы как целого.
	VM

Сферы применения ЭС:

ХИМИЯ:	DENDRAL (интерпр.) - определение структурной формулы хим.в-ва		
МЕДИЦИНА:	VM, MYCIN (см.выше)
ВОЕННОЕ ДЕЛО: TATR (см.выше), I&W (прогнозир.) - прогнозирование вооруженных конфликтов
ЭЛЕКТРОНИКА: EURISKO (проектир.) - проектирование СБИС
КОМПЬЮТЕРНЫЕ СИСТЕМЫ: XCON (см.выше), PTRANS (планир.&прогнозир.) - маркетинг в DEC
ТЕХНИКА: REACTOR (наблюден.) - в составе системы управления ядерным реактором  
ГЕОЛОГИЯ: PROSPECTOR (интерпр.) - оценка потенциальной рудоносности района

Основные компоненты ЭС (архитектура ЭС):

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

Решатель ЭС:

Вызов процедур (модулей / правил) по образцу  гибкая схема взаимодействия (управления)
Продукция – правило вида:  p:  (где: p – предусловие,  - антецедент,  - консеквент).

Основной цикл работы решателя:
•	выборка (правил-кандидатов)
•	сопоставление / означивание
•	разрешение конфликтов
•	выполнение / действия
•	переход на НАЧАЛО

Экспертные системы Реального времени

Способность «быстро работать» - лишь одно из требований к ЭС РВ.

Основные свойства ЭС РВ:
1.Немонотонность. В процессе функционирования происходит обновление данных. Необходимы специальные механизмы поддержания истинности (удаление старых данных вместе со сделанными на их основе выводами, учет новых данных).
2.Рассуждения с учетом времени (способность рассуждать о прошлых, текущих и будущих событиях, планировать поведение с учетом времени).
3.Реактивность по отношению к асинхронным событиям (происходящим в среде).
4.Концентрация внимания. Учет того, что события имеют разную значимость для ЭС РВ, умение выделять наиболее важные цели и отбирать необходимые для их достижения ресурсы.
5.Внешний интерфейс. ЭС РВ должна уметь собирать информацию, поступающую от различных сенсоров, по различным каналам связи, а также передавать данные по каналам связи (в том числе и для различных исполнительных механизмов).
6.Ненадежность и неполнота данных. Наличие ненадежных и неполных данных типично для областей применения ЭС РВ, необходимы механизмы для работы в таких условиях.
7.Интеграция с традиционным программным обеспечением (сжатие данных, обработка сигналов, специальный ввод-вывод и др.).
8.Высокая скорость работы. Для многих приложений важна высокая скорость реакции на события, важно также, чтобы ЭС РВ имела гарантированное время ответа (т.е., было известно, что обработка любого события потребует времени в определенных фиксированных границах). 

Основной цикл работы решателя:
•	ввод в базу фактов всех сообщений, полученных к данному моменту из внешних источников, посылка необходимых сообщений внешним адресатам (фаза коммуникации)
•	ввод в базу фактов «отложенных» фактов, время наступления которых уже «пришло»
•	выборка (правил-кандидатов)
•	сопоставление / означивание
•	разрешение конфликтов (если правил с удовлетворенными условиями нет, СТОП), переход в специальный режим «ожидание», нарушить который может некоторое событие (внешнее сообщение, сообщение от таймера)
•	выполнение / действия
•	переход на НАЧАЛО

Метазнания в ЭС

1. ВЫБОР ПРАВИЛ:
П1: утечка серной кислоты  использовать анион-обменник 
(стоимость: дорого, источник информации: доктор Грин, степень опасности: невелика)

П2: утечка серной кислоты  использовать уксусную кислоту
(стоимость: дешево, источник информации: практикант Грун, степень опасности: велика)

П3: прежде всего использовать правило, требующее минимальных затрат

П4: прежде всего использовать правило, внесенное в БЗ специалистом

П5: прежде всего использовать правило с минимальной степенью опасности

	2. ОПРАВДАНИЕ ПРАВИЛ:
П6: утечка серной кислоты  использовать известь
(оправдание: нейтрализация, образование нерастворимого и химически неактивного вещества)

П7: утечка уксусной кислоты  использовать известь
(оправдание: нейтрализация)

П8: утечка соляной кислоты  использовать известь
(оправдание: нейтрализация)

	3. ОБНАРУЖЕНИЕ ОШИБОК В ПРАВИЛАХ:
ПР01: использовать известь	- нет антецедента

ПР02: утечка:	соляная кислота  использовать известь	 

ПР03: 		соляная кислота  использовать известь - проверить: не совпадает ли предусловие
								с предусловием предыдущего правила

П9: если некоторое правило никогда не срабатывает, проверить его предусловие

	 4. СТРАТЕГИЧЕСКИЕ ПРАВИЛА:
П10: пространство поиска относительно мало  оправдан полный перебор

П11: один из конъюнктов часто ложен  перенести его в начало

П12: фрагмент часто выполняется  оптимизировать его

П13: фрагмент часто выполняется & редко меняется  скомпилировать его

П14: утечка вещества, которое не описано в БЗ  база знаний по утечкам неадекватна

Пример вывода в ЭС, основанной на правилах продукций

Правила:	R1: разлита горючая жидкость  звонить по телефону 01
R2: разлита уксусная кислота  использовать известь
		R3: pH жидкости < 6  кислота
R4: кислота & имеет запах уксуса  уксусная кислота

Факты:		F1: разлита жидкость
		F2: pH жидкости < 6
		F3: жидкость имеет запах уксуса

Цепочка вывода:
F1 & F2  F4 (разлита кислота) & F3  F5 (разлита уксусная кислота)  F6 (нейтрализация)  
              R3                                              R4                                                     R2
Цепочка вывода с учетом достоверности / вероятности:
F1      &      F2            F4     &    F3              F5           F6
80%            60%   R3     70%         100%    R4    85%     R2

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

Объяснение в ЭС
Цель - обосновать, аргументировать ответ в максимально естественной форме.

Что объяснять?
•	как получено решение
•	как использована некоторая информация (факты, правила)
•	почему не использована некоторая информация (факты, правила)
•	что использовано в целом при решении задачи (факты, правила)

Для кого нужны объяснения?
-	эксперты
-	инженеры знаний
-	пользователи
-	изучающие (новички)

Этапы построения ЭС:
•	идентификация ПО (цели и характеристики ЭС, ресурсы, участники разработки)
•	концептуализация  (основные понятия и связи между ними, основные задачи)
•	формализация (запись на выбранном языке представления знаний, формирование БЗ)
•	реализация
•	проверка правил, тестирование

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

Создавать ли ЭС?
ДА - ЕСЛИ: Разработка возможна & Разработка оправдана & Разработка разумна

Разработка возможна:
задача не слишком трудна
задача вполне понятна

&

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

Разработка оправдана:
полученное решение высокорентабельно
человеческий опыт утрачивается
V	экспертов мало
опыт нужен во многих местах
опыт нужен в неблагоприятной среде (автономная ЭС)
Разработка разумна:
задача требует оперирования символами
задача требует эвристических решений
&	задача не слишком проста
задача имеет практический интерес
задача решаема (ЭС реализуема)

Трудности, Ловушки, Советы
ВЫБОР ЗАДАЧИ: задача слишком трудна, построенная ЭС не решает нужные задачи.
РЕСУРСЫ: количество разработчиков, ЭС - не обычная программа.
ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА: неэффективны, не начинать с языков низкого уровня.
ЭКСПЕРТЫ: выбор Э, у Э нет времени, Э далек от компьютеров, Э незнаком с терминологией ЭС, правила слишком коротки и просты, правила слишком громоздки, Э теряет интерес к работе, слишком много Э (они не единодушны во мнениях).
РЕАЛИЗАЦИЯ: разделять знания Э и знания для решения задач, в готовой ЭС нет многих понятий, очень много специфических частных правил, нет хороших объяснений, нет удобств для пользователя, разочарование на этапе тестирования, трудно вносить изменения (большая система).

Извлечение экспертных знаний и формирование БЗ:
Эмпирические правила:
"Чем более компетентен эксперт, тем менее способен он описать те знания, которые использует при решении задач".
"Не будьте своим собственным экспертом".
"Не принимайте на веру все, что говорят эксперты".
Методы извлечения экспертных знаний:
Наблюдение на рабочем месте
	Э решает реальные задачи, ИЗ - пассивно наблюдает
	цель: ИЗ получает представление о характерных задачах.  
Обсуждение задач
ИЗ обсуждает с Э отобранные им (ИЗ) характерные задачи
цель: ИЗ узнает, как организованы знания Э (понятия, гипотезы), как Э работает с неполной, неточной, противоречивой информацией, какие процедуры необходимы для решения задач.
Описание задач
	ИЗ просит Э описать типичные задачи для каждого класса задач
	цель: ИЗ узнает, как связаны между собой задачи одного класса, классы задач.
Анализ задач
	ИЗ предлагает Э задачи и расспрашивает о ходе решения
	цель: ИЗ пытается найти и сформулировать стратегии решения задач.
Доводка системы
Э предлагает ИЗ/прототипу_ЭС характерные задачи
	цель: ИЗ проверяет сформированную совокупность знаний (БЗ).
Оценивание системы
Э анализирует и оценивает правила, стратегии, систему понятий ПО
цель: Э оценивает точность работы ИЗ и правильность сформированной БЗ.
Проверка системы
	ИЗ предлагает независимым экспертам протоколы решения задач Э и прототипом_ЭС
	цель: объективная оценка результатов работы ИЗ и Э (и сформированной БЗ).

Пример: Оценка размера страховых выплат
Ситуация. Беседа Инженера_знаний с Экспертом.
Некоторые правила:
Если	повреждение истца действительно требует, чтобы он носил очки
  и	и истец до повреждения не носил очков
увеличить фактор неудобства на 2500$
Если	истец действительно имеет вероятность заболеть глаукомой
  и	эта вероятность была вызвана повреждением
  и	величина этой вероятности равна 10%
увеличить фактор осложнений в будущем на 30000$

Реализация модельной экспертной системы на языке Плэнер

Модельная экспертная система решает задачу распознавания вида животного (тигр) на основе группы взаимосвязанных признаков:

млекопитающее

хищник

рыжевато-кор

темные-полосы

питается-мясом

острокон-зубы

когти

глаза-спереди

ТИГР

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

(<имя> = <вид>) → ОБСН: <обоснование>  ​  ( )
(<имя> - <класс>) → ОБСН: <обоснование>  ​  ( )
(<имя> имеет <свойство>) → ОТВ: ДА  ​  НЕТ
(<имя> питается <пища>)

Для определения вида животного используется аппарат теорем. Часть информации, необходимой для решения задачи представлена в виде утвереждений базы данных, часть запрашивается у пользователя. В списках свойств утверждений представлены ответы пользователя и обоснование решения системы.
[define  main  (lambda  ( )
	[prog (ОТВ  ИМЯ  КЛАСС  ОБ)
     [while  T
		[print  ‘Работает эксперт по распознаванию животных‘]
		[print  ‘У Вас есть задача на распознавание?‘]
		[pset  ОТВ [yes-no]]
		[cond ([eq  .ОТВ  НЕТ]  [exit  main  main])]
		[print  ‘Введите имя распознаваемого объекта‘]
		[pset  ИМЯ  [read]]
		[if  ([perm  [goal  (.ИМЯ  =  *КЛАСС)]]
		      [pset  ОБ  [geta  (.ИМЯ   =  *КЛАСС)  ОБСН]]
		      [output  .ИМЯ  .КЛАСС  .ОБ] )
		     (T [mprint  Кем является .ИМЯ я не знаю ])]
		[cleardb]  ] ])]

[define  Тигр?  (conseq  (ИМЯ  ОБ  ОБ1  ОБ2)
		(*ИМЯ  =  ТИГР)
[goal (.ИМЯ  - млекопитающее)]
[goal (.ИМЯ  - хищник)]
[goal (.ИМЯ  имеет рыжевато-кор) (test  ОТВ  ДА)]
[goal (.ИМЯ  имеет темные-полосы) (test  ОТВ  ДА)]
	[pset  ОБ1 [geta  (.ИМЯ  - млекопитающее) ОБСН]]
	[pset  ОБ2 [geta  (.ИМЯ  - хищник) ОБСН]]
	[pset  ОБ ( ( (.ИМЯ  = ТИГР) так как (.ИМЯ – млекопитающее)
    (.ИМЯ – хищник)								    	       (.ИМЯ имеет рыжевато-коричневую окраску)
				    	       (.ИМЯ имеет темные полосы)) !.ОБ1  !.ОБ2)]
	[passert  (.ИМЯ  = ТИГР)  (with  ОБСН  .ОБ)]   )]

[define  Окраска?  (conseq  (ИМЯ  ОТВ)
	(*ИМЯ имеет рыжевато-кор)
[if  ([search1 (.ИМЯ имеет рыжевато-кор)  (test  ОТВ  *ОТВ)])
     (T  [mprint  .ИМЯ имеет рыжевато-коричневую окраску?]
           [pset  ОТВ  [yes-no]]
           [passert  (.ИМЯ имеет рыжевато-кор)  (with  ОТВ  .ОТВ)])]
[cond ([eq  .ОТВ  НЕТ]  [fail])] )]

[define  Полосы?  (conseq  (ИМЯ  ОТВ)
	(*ИМЯ имеет темные-полосы)
[if  ([search1 (.ИМЯ имеет темные-полосы)  (test  ОТВ  *ОТВ)])
     (T  [mprint  .ИМЯ имеет темные полосы?]
           [pset    [yes-no]]
           [passert  (.ИМЯ имеет темные-полосы )  (with  ОТВ  .ОТВ)])]
[cond ([eq  .ОТВ  НЕТ]  [fail])] )]

[define  Хищник1?  (conseq  (ИМЯ  ОБ)
		(*ИМЯ  -  хищник)
[goal (.ИМЯ  питается  мясом)]
	[pset  ОБ  ( ( (.ИМЯ - хищник) так как (питается мясом)))]
	[passert  (.ИМЯ - хищник)  (with  ОБСН  .ОБ)]   )]

[define  Хищник2?  (conseq  (ИМЯ  ОБ)
	(*ИМЯ  -  хищник)
[goal (.ИМЯ  имеет  острокон-зубы)]
[goal (.ИМЯ  имеет  когти)]
[goal (.ИМЯ  имеет  глаза-спереди)]
	[pset  ОБ  ( ( (.ИМЯ - хищник) так как   (.ИМЯ имеет  остроконечные зубы)								            (.ИМЯ имеет когти)
			            (.ИМЯ имеет глаза спереди)))]
	[passert  (.ИМЯ - хищник)  (with  ОБСН  .ОБ)]   )]
[define  yes-no  (lambda  ( ) [read])]
[define  output  (lambda  (x y z ) [prog ( ) [print .x] [print.y] [print .z]])]

[assert (Муся  питается  мясом)]
[assert (Муся - млекопитающее)]
[assert (Муся  имеет темные-полосы) (with ОТВ ДА)]
[assert (Муся  имеет рыжевато-кор) (with ОТВ ДА)]

Реализация модельной экспертной системы на языке Плэнер

Модельная экспертная система решает задачу распознавания вида животного (тигр) на основе группы взаимосвязанных признаков:

млекопитающее

хищник

рыжевато-кор

темные-полосы

питается-мясом

острокон-зубы

когти

глаза-спереди

ТИГР

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

(<имя> = <вид>) → ОБСН: <обоснование>  ​  ( )
(<имя> - <класс>) → ОБСН: <обоснование>  ​  ( )
(<имя> имеет <свойство>) → ОТВ: ДА  ​  НЕТ
(<имя> питается <пища>)

Для определения вида животного используется аппарат теорем. Часть информации, необходимой для решения задачи представлена в виде утверждений базы данных, часть запрашивается у пользователя. В списках свойств утверждений представлены ответы пользователя и обоснование решения системы.
[define  main  (lambda  ( )
	[prog (ОТВ  ИМЯ  КЛАСС  ОБ)
     [while  T
		[print  ‘Работает эксперт по распознаванию животных‘]
		[print  ‘У Вас есть задача на распознавание?‘]
		[pset  ОТВ [yes-no]]
		[cond ([eq  .ОТВ  НЕТ]  [exit  main  main])]
		[print  ‘Введите имя распознаваемого объекта‘]
		[pset  ИМЯ  [read]]
		[if  ([perm  [goal  (.ИМЯ  =  *КЛАСС)]]
		      [pset  ОБ  [geta  (.ИМЯ   =  *КЛАСС)  ОБСН]]
		      [output  .ИМЯ  .КЛАСС  .ОБ] )
		     (T [mprint  Кем является .ИМЯ я не знаю ])]
		[cleardb]  ] ])]

[define  Тигр?  (conseq  (ИМЯ  ОБ  ОБ1  ОБ2)
		(*ИМЯ  =  ТИГР)
[goal (.ИМЯ  - млекопитающее)]
[goal (.ИМЯ  - хищник)]
[goal (.ИМЯ  имеет рыжевато-кор) (test  ОТВ  ДА)]
[goal (.ИМЯ  имеет темные-полосы) (test  ОТВ  ДА)]
	[pset  ОБ1 [geta  (.ИМЯ  - млекопитающее) ОБСН]]
	[pset  ОБ2 [geta  (.ИМЯ  - хищник) ОБСН]]
	[pset  ОБ ( ( (.ИМЯ  = ТИГР) так как (.ИМЯ – млекопитающее)
    (.ИМЯ – хищник)								    	       (.ИМЯ имеет рыжевато-коричневую окраску)
				    	       (.ИМЯ имеет темные полосы)) !.ОБ1  !.ОБ2)]
	[passert  (.ИМЯ  = ТИГР)  (with  ОБСН  .ОБ)]   )]

[define  Окраска?  (conseq  (ИМЯ  ОТВ)
	(*ИМЯ имеет рыжевато-кор)
[if  ([search1 (.ИМЯ имеет рыжевато-кор)  (test  ОТВ  *ОТВ)])
     (T  [mprint  .ИМЯ имеет рыжевато-коричневую окраску?]
           [pset  ОТВ  [yes-no]]
           [passert  (.ИМЯ имеет рыжевато-кор)  (with  ОТВ  .ОТВ)])]
[cond ([eq  .ОТВ  НЕТ]  [fail])] )]

[define  Полосы?  (conseq  (ИМЯ  ОТВ)
	(*ИМЯ имеет темные-полосы)
[if  ([search1 (.ИМЯ имеет темные-полосы)  (test  ОТВ  *ОТВ)])
     (T  [mprint  .ИМЯ имеет темные полосы?]
           [pset    [yes-no]]
           [passert  (.ИМЯ имеет темные-полосы )  (with  ОТВ  .ОТВ)])]
[cond ([eq  .ОТВ  НЕТ]  [fail])] )]

[define  Хищник1?  (conseq  (ИМЯ  ОБ)
		(*ИМЯ  -  хищник)
[goal (.ИМЯ  питается  мясом)]
	[pset  ОБ  ( ( (.ИМЯ - хищник) так как (питается мясом)))]
	[passert  (.ИМЯ - хищник)  (with  ОБСН  .ОБ)]   )]

[define  Хищник2?  (conseq  (ИМЯ  ОБ)
	(*ИМЯ  -  хищник)
[goal (.ИМЯ  имеет  острокон-зубы)]
[goal (.ИМЯ  имеет  когти)]
[goal (.ИМЯ  имеет  глаза-спереди)]
	[pset  ОБ  ( ( (.ИМЯ - хищник) так как   (.ИМЯ имеет  остроконечные зубы)								            (.ИМЯ имеет когти)
			            (.ИМЯ имеет глаза спереди)))]
	[passert  (.ИМЯ - хищник)  (with  ОБСН  .ОБ)]   )]
[define  yes-no  (lambda  ( ) [read])]
[define  output  (lambda  (x y z ) [prog ( ) [print .x] [print.y] [print .z]])]

[assert (Муся  питается  мясом)]
[assert (Муся - млекопитающее)]
[assert (Муся  имеет темные-полосы) (with ОТВ ДА)]
[assert (Муся  имеет рыжевато-кор) (with ОТВ ДА)]

ОБЩЕНИЕ  ЧЕЛОВЕКА  С  СИСТЕМОЙ  ИИ
(Искусственный интеллект и естественный язык)

Естественный язык в работах по искусственному интеллекту. Первые шаги.  
В 60-е – 70-е гг. ХХ века специалистов в области искусственного интеллекта интересовала прежде всего проблема моделирования понимания сообщений/текстов. Были реализованы системы, способные «поддерживать диалог» с человеком на естественном языке, интерпретировать словесные команды роботу (действующему в «Мире кубиков»), решать задачи в словесной формулировке.
Система ELIZA (DOCTOR) – Дж. Вейзенбаум (1966)
Система относится к классу Conversation Machines, разработчики которых надеялись на то, что их творения смогут пройти Тест Тьюринга. 
Версия DOCTOR моделирует диалог врача-психоаналитика (система) с пациентом (человек).
Фрагмент диалога с системой ELIZA:
USER:  MY  MOTHER  TAKES  CARE  OF  ME
ELIZA:  WHO  ELSE  IN  YOUR  FAMILY  TAKES  CARE  OF  YOU
USER:  MY  FATHER
ELIZA:  YOUR  FATHER
USER:  YOU  ARE  LIKE  MY  FATHER  IN  SOME  WAYS
ELIZA:  WHAT  RESEMBLANCE  DO  YOU  SEE
USER:  YOU  ARE  NOT  VERY  AGGRESSIVE
ELIZA:  WHAT  MAKES  YOU  THINK  I  AM  NOT  VERY  AGGRESSIVE
Для формирования ответов система использует простейшие шаблоны и связанные с ними правила, например:
(<any-1> you <any-3> me) → (what makes you think I <any-3> you)
USER: IT SEEMS THAT YOU HATE ME
ELIZA: WHAT MAKES YOU THINK I HATE YOU
(<any-1> you are <any-3>) -> (what makes you think I am <any-3>)
USER: YOU ARE NOT VERY AGGRESSIVE
ELIZA: WHAT MAKES YOU THINK I AM NOT VERY AGGRESSIVE
Система APRIL – М.Г.Мальковский (1969)
	Система APRIL решает арифметические задачи в словесной формулировке. Результатом ее работы является ответ (формула или число), иногда сопровождаемый некоторыми комментариями, или сообщение (также сопровождаемое комментариями) о том, что задачу решить не удалось.
	Система решает довольно узкий круг задач из школьного курса математики (1-2-й классы) –  так называемые задачи «на владение». Каждая задача решается независимо от других.
	На входной язык системы наложены достаточно жесткие ограничения, которые, впрочем, абсолютно естественны для рассматриваемого класса задач. Так, условие задачи должно быть сформулировано в виде трех простых предложений, а все слова, встречающиеся в тексте условия, должны быть знакомы системе (записаны в ее словарь).
	Наиболее серьезное внимание было уделено разработке методов, позволяющих учитывать возможность варьирования словесных формулировок условий задач и употребления в тексте неполных (эллиптичных) конструкций. Так, внешне непохожие задачи № 1, № 2 и № 3 система сводит к одному типу задач, а решая задачи, которые человек воспринимает как имеющие решение и притом единственное, несмотря на отсутствие подразумеваемых уточняющих слов, она делает примерно те же предположения, что и человек.
Задача N 1: У Саши 5 яблок. У Пети 10 груш. Сколько фруктов у ребят?
ОТВЕТ: 15
Задача N 2: У человека 10 книг. У второго человека в 2 раза меньше. Сколько книг у них вместе?
ОТВЕТ: 15
Задача N 3: На стол положили 6 книг. Затем еще 4 книги. Сколько книг на столе?
ЕСЛИ ВО ВСЕХ ФРАЗАХ ИМЕЕТСЯ В ВИДУ "СТОЛ", ТО 
ЕСЛИ В НАЧАЛЬНЫЙ МОМЕНТ КОЛИЧЕСТВО ОБЪЕКТОВ "КНИГА" В МЕСТЕ "СТОЛ" = 0, ТО 
ПРЕДПОЛОЖИТЕЛЬНЫЙ ОТВЕТ: 10
Первые эксперименты показали и принципиальную возможность моделирования процессов владения языком, и чрезвычайную сложность естественного языка как объекта исследования.

Естественный язык в деятельности человека
Как мы знаем, интеллектуальная деятельность предполагает создание и использование абстрактных объектов (понятий), освобожденных от второстепенных, привходящих характеристик и отражающих наиболее существенные стороны действительности. Она реализует высшую форму регуляции деятельности человека в предметной среде.
В свою очередь существенность, значимость отражаемого определяется деятельным контекстом: в процессе управляемой мышлением деятельности и в соотнесении с ее целями и средствами. Очевидно, что деятельность человека нельзя рассматривать в отрыве от его общественных отношений. В социальной среде, в условиях общественного разделения труда структура человеческой деятельности усложняется. Человек может выполнять лишь отдельные этапы решения задачи, а цель деятельности может быть связана с его непосредственными потребностями косвенным путем. При этом функции регуляции совместной и дифференцированной деятельности выполняет коммуникативная деятельность (общение), заключающаяся в обмене информацией о деятельности индивидуальной.
В качестве средства такого обмена (средства общения) используется знаковая система социального уровня – язык. Связи языковых знаков (элементов языка) с психическими явлениями и объектами психического взаимодействия объективированы в социальной группе носителей данного языка и относительно константны для нее. Каждый член группы воспринимает эти связи как данные извне, как существующие объективно, а процесс усвоения этих связей (и знаков языка) – одна из необходимых предпосылок формирования личности, включения человека в систему общественных отношений. Овладевая языком, человек приобретает детально разработанную систему объективации и реализации собственной психической деятельности, активно используемую им в ходе социальных взаимодействий.
Основными элементами языка как знаковой системы являются языковые знаки, образующие субстанцию языка. Они связаны внутрисистемными отношениями, определяющими как структуру языка в целом, так и структуру конкретных знаковых конструкций, и участвуют в отношениях с внеязыковыми объектами.
Языковой знак – материальный объект, поставленный в соответствие некоторому другому объекту и заменяющий последний в ходе деятельности (свойство знаковости). Другими словами, если некоторый объект является знаком, то он поставлен в соответствие некоторому другому объекту и способен его заменять. Отметим также, что знаки следует отличать от единиц языка: фонем, морфем и слов (в естественном языке). Фонемы свойством знаковости не обладают и служат лишь исходным материалом для построения знаков языка, а морфемы и слова являются знаками.
Второй атрибут языкового знака – его конвенциальность, или немотивированность. Это свойство означает, что устанавливается указанное соответствие соглашением людей, использующих язык (всюду в данном разделе, если специально не оговаривается иное, речь идет о языке человека). Знак может не иметь никакого сходства с объектом, в соответствие которому он поставлен, и не быть связанным с ним причинно-следственными отношениями.
Однако выбор материального объекта на роль знака не может быть произволен абсолютно. Объект должен обладать так называемыми системообразующими свойствами – необходимыми для включения его в систему языка.
К числу системообразующих свойств языка относятся дискретность («членораздельность») и неоднородность («различаемость») его элементов. Неоднородность языка проявляется и в его иерар- хичности – в языке может быть выделено несколько иерархических неоднородных уровней, единицы каждого из которых относительно однородны (морфемы – как единицы морфологического уровня, например). С особенностями речевого аппарата человека связан принцип линейности в языке – в конструкциях, построенных по правилам языка, знаки могут располагаться лишь в линейной последовательности, то есть цепочкой.
Как элементы системы (языка) знаки обладают еще рядом свойств. Связь знака с внеязыковыми объектами задается отношениями: сигматическими – связь знака с реальными объектами и явлениями действительности или отдельными аспектами их; семантическими – связь с психическими  моделями соответствующих сторон реальности или с моделями реально не существующих объектов; прагматическими – связь с людьми, использующими знаки языка в своей деятельности. Синтаксические отношения (при описании естественных языков обычно рассматриваются два уровня синтаксических отношений: морфологический и синтаксический в узком смысле) характеризуют связи между знаками как элементами языка: иерархические – отношения вхождения знака в сложный знак; синтагматические – отношения взаимодействия знаков или их классов; парадигматические – отношения между элементами одного класса, например, формами одного слова.

Естественный язык в человеческой деятельности (продолжение)
Характеристика языка как знаковой системы, элементы которой связаны отношениями с различными сторонами действительности, полезна и при рассмотрении процессов его использования. Язык является знаковой системой социального уровня. Выбор знаков, правил их комбинирования и соотнесения с явлениями объективного и субъективного планов закреплен «общественным соглашением», которое разделяют все владеющие данным языком. Тем самым язык задает нормы интерпретации и употребления знаков. А в реальных процессах использования языка на основе этих общих норм строятся и анализируются конкретные знаковые конструкции, описывающие конкретные ситуации.
Таким образом, процесс использования языка – речевая деятельность (РД) – может быть охарактеризован как актуализация и конкретизация существующих в языке в потенциальной форме синтаксических отношений и отношений знаков с внеязыковыми объектами: выбор нужной формы слова при синтезе, установление актуального сигматического отношения с реальным объектом – денотатом и т.п. Результатом РД при синтезе является сообщение, несущее определенную информацию и о самом языке (по правилам которого оно построено), и о ситуации, в которой оно было синтезировано, и об авторе.
В структурном плане сообщение представляет собой наделенную структурой линейную последовательность знаков. Каждый знак характеризуется его позицией в цепочке и актуальными синтаксическими отношениями с другими знаками. «Нечленимые» в языке знаки – материальные оболочки «элементарных» языковых единиц (морфем, неизменяемых слов, фразеологизмов) – «воспроизводятся» в речевом произведении в готовом виде. Структурно сложные знаки строятся из составляющих по правилам языка.
Общение, или коммуникативная деятельность, предполагает наличие не менее двух носителей языка – автора сообщения и субъекта, которому это сообщение адресовано, – реципиента (в случае диалога они естественным образом поочередно «меняются местами»), а также наличие некоторой совместной деятельности, которую общение должно регулировать.
Определенное сходство в структурном и функциональном плане с естественными языками имеют и представители класса искусственных языков.
Хотя проблема соотношения естественных и искусственных языков представляется на первый взгляд (и является на самом деле) тривиальной, при ее рассмотрении часто допускаются ошибки. Одна из наиболее распространенных – абсолютизация временных и несущественных различий (существенные при этом как правило упускаются из виду), учет особенностей искусственных языков, существующих в данный момент, и неоправданный перенос выявляемых при этом различий на весь класс искусственных языков вообще. Очевидно, что в этом случае и сама проблема подменяется другой.
Единственное непреходящее отличие естественного языка от всех прочих – которые и следует называть искусственными – связано с историей его возникновения. Естественный язык – продукт, естественно-исторически возникший из объективных общественных потребностей (в первую очередь из потребности в общении, регулирующем совместную и дифференцированную деятельность) на ранних этапах общественного развития, когда человеческое познание было практически нерефлексивным и никакое активное сознательное регулирование процесса создания языка было невозможно.
Объективность существования ЕЯ объясняет, почему многие языковые реликты, исключения и нерегулярности «живут» в языке до сих пор, а попытки избавиться от них, модернизировать, улучшить язык часто заканчиваются неудачей. Для того, чтобы некоторые новшества попали в язык, «закрепились» в нем, их должно усвоить большинство носителей языка (и при спонтанном развитии языка новшества, возникшие в речи, попадают в язык лишь в этом случае). Это и есть объективация
Примечательно, что хотя существенные отклонения от общих языковых правил и норм недопустимы, индивидуальные модели ЕЯ (индивидуальные языковые модели – ИЯМ), усвоенные его носителями и определяющие особенности речи последних, могут иметь некоторое своеобразие. Они описывают своего рода «подмножество-расширение» эталонного языка, не содержащее неизвестных конкретному носителю языка знаков и правил и включающее ряд конструкций и форм, не входящих в общелитературный язык (заведомо неграмматичных) или используемых в рамках узких социальных групп (формы просторечные и разговорные, жаргонизмы, профессионализмы). Несмотря на формальную недопустимость или ограничения на употребление подобных форм, они (эти формы) не только встречаются в повседневной речи (соответствующие запреты либо вообще не входят в ИЯМ носителя языка, либо случайно или намеренно им игнорируются), но и понимаются людьми.
Понятие ИЯМ подчеркивает факт субъективного преломления естественного языка как знаковой системы социального уровня в ходе его усвоения и использования. Формирование ИЯМ – сложный и длительный процесс, включенный в процесс развития человеческой психики и детерминируемый как внешними (социальная среда), так и внутренними (индивидуальные психофизиологические особенности) факторами. Примечательно, что с уменьшением социальной группы (производственный коллектив, семья) своеобразие используемого в ней подмножества-расширения ЕЯ возрастает. И это естественно: усвоить отклонения от языка-эталона должно в этом случае небольшое число лиц.
Характерной, но не обязательно отличительной чертой любого естественного языка является его универсальность. Возникнув как средство регуляции самых разнообразных видов человеческой деятельности (протекающей в различных контекстах, предполагающей использование различных средств, направленной на различные объекты), ЕЯ может быть использован для выражения качественно различных видов содержания, для описания реальной действительности и процессов психической деятельности с разной степенью строгости, полноты, эксплицитности.
Автор сообщения, например, может описать некоторую ситуацию в весьма общих чертах и, не потеряв при этом объективно существенные (но не сочтенные им таковыми) детали, возложить задачу выявления этих деталей и дальнейшей конкретизации совместной деятельности на реципиента.
И хотя в ходе последующих языковых взаимодействий могут потребоваться новые языковые средства (необходимые для выражения новых видов информации), соответствующее расширение ЕЯ, представляющего собой открытую систему, всегда возможно. При этом способность ЕЯ служить метаязыком для себя позволяет описать такое расширение средствами самого языка.
Поскольку ЕЯ является средством объективации психической деятельности человека (построения моделей отражаемого) и средством передачи информации об отражаемом, сигматические, семантические и прагматические аспекты знаков чрезвычайно существенны в процессах использования языка. Важную роль играют и синтаксические отношения, существующие в потенциальной форме в языке или в ИЯМ и актуализируемые в РД. Возможность передачи информации с необходимостью предполагает структурированность языковых выражений, репрезентующих эту информацию, а многие тонкие оттенки содержания передаются исключительно синтаксическими средствами (например, порядком слов).
Синтаксическое значение существует в языке как система ассоциированных с данным сообщением эталонных парадигматических, синтагматических и иерархических связей с другими знаками языка – аналог «значимости» в смысле одного из лингвистов-классиков  Ф. де Соссюра. Являясь соотносительной характеристикой знаков языка, оно определяет выбор некоторого знака как средства выражения других видов значения. Сигматическое значение – класс реальных объектов («денотатов», или «обозначаемых»), в соответствие которым может быть поставлено сообщение, в то время как  семантическое значение отсылает к классу эталонных психических моделей денотатов (к «десигнатам», «означаемым», или «концептам»). Прагматическое значение представляет собой класс нормативно соотнесенных с сообщением действий потенциальных реципиентов или же класс действий и целей потенциального автора сообщения, побуждающих его к речевой деятельности.
Полное  значение сообщения является комплексом четырех указанных видов  значения.   Возможны и «вырожденные» случаи. Так, например, сигматическое значение некоторых знаков может быть пустым (всегда – кентавр, в определенном временном интервале – Великий инквизитор); пустая морфа не изображается никаким знаком (хотя, например, в словоформе слов отсутствие флексии передает грамматическое значение родительный падеж, множественное число); служебные морфемы обладают лишь грамматическим и крайне абстрактным семантическим (грамматический род, число) значением.
Отметим, что для ЕЯ характерно отсутствие взаимнооднозначного соответствия между знаками и связанными с ними обозначемыми, означаемыми и действиями. Знак или сообщение называется омонимичным, если связанные с ним в языке или в речевом произведении классы обозначаемых, означаемых или деятельных актов содержат более одного элемента. Частным случаем омонимии является полисемия – наличие у слова нескольких обозначаемых (означаемых): оросительный канал ↔ канал ствола орудия ↔ канал  связи  с ЭВМ ↔ дипломатические каналы. Возможна и грамматическая омонимия: второй параграф ↔ о  второй  главе ↔  для  второй  главы,  цинковые белила ↔ белила  потолок,  прием  посла  =  посол  принял <кого-то>   ↔ <кто-то>  принял посла.
В письменной речи (если не проставлены ударения) неразличимы формы: профессора ↔ профессора, колет ↔ колет, это все твои вещи? ↔ это все твои вещи?, а в устной (омофония) – конструкции и скота ↔ из кота. Определенный интерес представляют сходные по строению, но имеющие несовпадающие значения слова (паронимы): языковый ↔ языковой, представить ↔ предоставить (языковая колбаса ↔ языковой знак, представить справку ↔ предоставить возможность).
Если же различные знаки имеют «общее значение» и могут, в частности, заменять друг друга в сообщении (общее в синтаксическом значении, «значимости»), то их обычно называют синонимами. «Абсолютная» синонимия в ЕЯ встречается редко: языкознание = лингвистика = языыковедение; флексии -ее и -ей с грамматическим значением сравнительная степень прилагательного, находящиеся в отношении свободного чередования: весел-ее = весел-ей.
Как правило, возможность замены знака другим, то есть употребления синонима, ограничена нетождественностью «общего значения», контекстными условиями. Так, например, морфологические синонимы – флексии с «общим значением» мужской род, множественное число, именительный падеж: -ы, -и, -е, -а, -я – употребляются с существительными различных типов склонения (лингвист-ы, филолог-и, южан-е, профессор-а, кра-я). К контекстным условиям относятся также лексическая сочетаемость и стилистическая окраска. Например, замена хочу на желаю во фразе Я не хочу его видеть допустима, а во фразе Кроме нас хотят  переселиться  в  колхоз  еще  несколько  семей – нет. 
Описывая одну и ту же ситуацию, одно обозначаемое с помощью различных синонимичных конструкций (синонимичными, естественно, могут быть и предложения, тексты), носитель языка имеет возможность переструктурировать не только сообщение, но и репрезентуемую им модель ситуации, выделять то одни, то другие компоненты и аспекты.
Согласно данному выше определению значение сообщения является комплексом эталонных для некоторого ЕЯ внутриязыковых связей знаков и ассоциированных со знаками внеязыковых объектов. А поскольку при усвоении естественного языка конкретным человеком, при формировании ИЯМ язык претерпевает субъективное преломление, отклонения от эталона имеют место и в сфере значений – субъективное сужение или расширение значения. Возможно, что отдельные виды значения при этом не меняются или меняются в разной степени. Своеобразием может отличаться и значение, ассоциированное со знаком в той или иной социальной группе (научные термины, профессионализмы, диалекты языка, жаргонизмы).
Учет субъективной и социальной соотнесенности значения (как следствие преломления языка в ИЯМ или в модели языка, общей для членов социальной группы) – необходимая предпосылка эффективного использования ЕЯ для общения между людьми, между людьми и искусственными информационными системами.
В конкретных процессах РД происходит дальнейшая модификация значения – с сообщением связываются лишь отдельные компоненты преломленного в ИЯМ значения. Подобная актуализация предполагает выбор уместных в текущем контексте аспектов семантического и прагматического (учет конкретной цели автора сообщения, особенностей собеседника) значений; установление, если это возможно, связи с обозначаемым; выбор (раскрытие) синтаксических средств выражения значения.
Соотнесенная с сообщением в реальном процессе речевой деятельности подсистема значения (виртуально ассоциированного с данным сообщением в ИЯМ носителя языка) может быть названа смыслом сообщения.

Понимание выражений естественного языка
С привлечением понятий значения и смысла сообщения можно конкретизировать описание информационного аспекта общения, регулирующего совместную и дифференцированную деятельность. Автор очередного сообщения строит его таким образом и с использованием таких (представленных в его ИЯМ) языковых средств, чтобы смысл сообщения максимально точно отображал важнейшие в текущей контекстной ситуации аспекты деятельности, преследуемые им цели. Задача же реципиента – выявить этот смысл, то есть установить те стороны значения (допустимого с позиций его ИЯМ), которые наиболее существенны в текущей ситуации с его точки зрения и которые, как он предполагает, имел в виду автор сообщения.
Подобный процесс раскрытия смысла и назван пониманием сообщения.
Понимание сообщения можно трактовать как вид интеллектуальной деятельности, обладающий всеми атрибутами ее и, естественно, всеми атрибутами психического отражения: информационностью (выявляется информация об актуальных связях знаков) и субъективностью (учитывается информация, существенная с позиций реципиента). Процесс понимания может быть прерывистым: выдвижение подцелей, возврат на предыдущие этапы и коррекция. Кроме того, он может сопровождаться адаптацией как к языку в целом, так и к особенностям ИЯМ собеседника.
В силу того, что понимание языковых выражений – один из наиболее привычных для человека видов интеллектуальной деятельности, многие этапы понимания реализуются с помощью неосознаваемых человеком средств – вторичных автоматизмов, сформированных в ходе усвоения языка.
Однако хотя построение интерпретации сообщения часто осуществляется «автоматически», и не вызывает осознаваемых субъективных трудностей, смысл, соотнесенный с сообщением реципиентом – Ср, может отличаться от смысла, ассоциированного с тем же сообщением его автором – Са. Главные причины этого: несовпадение ИЯМ, используемых конкретными носителями языка; неадекватное отражение в них языка как социального феномена; многоплановость сущности, репрезентуемой языковым выражением (негомогенность значения, потенциальная неисчерпаемость этого значения).
После того как Са объективирован в построенном автором сообщении и сообщение передано реципиенту, последний рассматривает как единственно доступные реальности только это сообщение (линейную последовательность знаков языка) и текущий деятельный контекст. Он может воспринимать этот контекст иначе, чем автор сообщения (из-за иных представлений о членении ситуации и существенности отдельных компонентов ее) и сопоставить сообщению иную интерпретацию, отображающую те аспекты, которые восприняты им. Даже и в том случае, когда основные компоненты ситуации отображены реципиентом верно (относительно Са), многогранность свойств и характеристик реальных объектов может привести к расхождению смыслов, ассоциируемых с соответствующим сообщением.
Кроме того «ключевыми» в текущем коммуникативном акте могут быть различные виды значения сообщения. Одно и то же сообщение может быть синтезировано с разными целями: установить актуальные семантические и сигматические связи и выполнить действия над соответствующими объектами, запомнить смысл сообщения и др.
Замечательный пример, иллюстрирующий возможность неправильного относительно Са выделения ключевого вида значения описан Дж. Литлвудом. В печатном тексте одной из своих работ Литлвуд не обнаружил последней фразы – Таким образом, σ следует сделать сколь возможно малым. Однако вместо нее на пустом месте в конце статьи стояла миниатюрнейшая σ. Наборщик вместо того, чтобы воспроизвести данную фразу (что он и должен был сделать по роду своей профессии), выполнил потенциально предусматриваемые ее значением действия.
Примечательно, что своеобразие восприятия смысла часто определяется устойчивыми факторами, в первую очередь социальной ролью реципиента (поэтому ошибку наборщика следует признать экстраординарной). Так, лингвиста могут заинтересовать несущественные для прочих носителей языка проявления в речи языковых закономерностей.
В силу действия подобных осложняющих факторов понимание должно предполагать ориентацию на ИЯМ автора полученного сообщения, учет целей его обращения к реципиенту, а также адаптацию и обучение, направленные на сближение используемых собеседниками ИЯМ и повышение точности отражения в них языка. Основная предпосылка близости ИЯМ – активные коммуникативные взаимодействия, протекающие в общем деятельном контексте (так, в небольшой социальной группе ИЯМ достаточно близки, хотя они, как отмечалось, могут отражать язык с искажениями). А для сближения смыслов можно использовать перефразирование сообщений, упоминавшееся в связи с синонимией, и уточняющий диалог.
Разумеется, такой диалог будет возможен и плодотворен лишь в том случае, когда реципиент осознает, что он понял сообщение «как-то не так», что в сообщении не указаны важные с его точки зрения детали: Этого просто не вынести!   А что вам нужно вынести? – спросила Алиса (Л. Кэрролл, «Алиса в Стране Чудес»), что в его распоряжении вообще нет средств приписать сообщению какую-либо интерпретацию.
В тех же случаях, когда реципиент считает, что смысл сообщения раскрыт им правильно, возможно объективное несовпадение этого смысла с Са и/или с наиболее вероятной в языке интерпретацией сообщения – нормативно выделенной подсистемой значения ЯВ, которую можно назвать смыслом относительно языка (Ся). 
В языке критерии выделения Ся должны быть объективными, например синтаксическими. Так, наиболее вероятная (нормативная) в русском языке трактовка фразы Мать любит дочь определяется порядком слов: мать – субъект, дочь – объект. Можно считать, что значение данного выражения включает и другую, менее вероятную интерпретацию (которую следовало бы выразить фразой Дочь любит мать) и предположить, что эта интерпретация соответствует Са. Ср может в данном случае совпасть либо с Ся, либо с Са.
Таким образом, Са – «то, что хотел сказать автор сообщения», Ся – «то, что сказано», и Ср – «то, что понял реципиент», вообще говоря могут не совпадать. Если Ср совпадает с Са, реципиент понял сообщение правильно относительно автора, если же Ср совпадает с Ся – объективно правильно.  Субъективно правильное понимание имеет место в том случае, когда Ср релевантен текущей деятельности реципиента, когда реципиент сумел извлечь из полученного сообщения ценную для себя информацию.
Введенные критерии правильности независимы – понимание правильное в одном аспекте, может быть правильным и в других, а может и не быть таковым. Причем правильность трактуется как соотносительная характеристика процесса понимания. Понимание может быть правильным (или неправильным) лишь по отношению к некоторому «судие»: автору сообщения, языку, деятельности реципиента. В то же время при совпадении (близости) Са, Ся и Ср можно говорить и об абсолютно правильном понимании. Здесь, правда, возникает уже упоминавшаяся в связи с синонимией проблема описания «пространства смыслов» – причем, общего для собеседников (!) – и задания его «метрики». В пространстве смыслов, наряду с правильностью понимания, характеризующей корреляцию наиболее существенных аспектов значения, можно было бы рассматривать и полноту понимания – меру близости объемов смыслов.
Для того, чтобы добиться правильного понимания адресуемых ему сообщений, каждый из участников процесса общения должен располагать информацией об определяющей предмет общения проблемной среде, о языке (эта информация представлена в его ИЯМ), о собеседнике, в том числе и об используемой им ИЯМ, и о себе. Эта информация соответствует глобальному контексту общения.
Естественно, что при обработке очередного сообщения (отдельной фразы, абзаца и т.п.) важную роль играет и информация, почерпнутая из предшествующих сообщений (из локального контекста). Именно учет глобального и локального контекстов: предмета обсуждения, собственных целей и целей собеседника, языковых и внеязыковых связей между отдельными сообщениями – и помогает реципиенту приписать очередному сообщению наиболее уместную интерпретацию, то есть правильно понять его.
Установив, о чем идет речь в сообщении, как должна быть использована содержащаяся в нем информация, реципиент может относительно легко разрешать проблемы, возникающие при анализе чисто знаковых (синтаксических) отношений, определяющих структуру сообщения.
Иллюстрирует эти возможности способность человека:
1) выбирать «наиболее разумную» интерпретацию сообщения, отсеивая интерпретации неестественные (но формально допустимые): За безбилетный проезд и провоз одного  места багажа взимается штраф 1 рубль,  Сведения о войсках противника,  которые помогали нашим партизанам,  В  черных костюмах выступают наши фигуристы, которые отделаны красными и зелеными цветами;
2) понимать неграмматичные  (ошибочные)  конструкции:  Ошбика вслове  лектор,  В аудиторию вошли лектора [следует: лекторы], Предоставить [следует:  представить]  справку в бухгалтерию – и грамматически  неоформленные  квазифразы  типа:  ребен-  спа- комнат-  шир-  распах-  окн-;
3) определять по контексту достаточные с точки зрения текущего этапа общения аспекты значений и функциональные роли в тексте незнакомых слов и конструкций. Читатель «Алисы в Зазеркалье», например,  достаточно  ясно  представляет себе, что произошло с головой Бармаглота  (... Взы-взы – стрижает меч,  Ува!  Ува!  И голова  Барабардает  с  плеч!), хотя и не знает семантическое и сигматическое значения незнакомого глагола  барабардать.
Примечательно, что ориентация на «высшие» аспекты значения (сигматический, семантический и прагматический), то есть на внеязыковые связи знака характерна и для более частных видов речевой деятельности. Так, согласно данным психолингвистики  и при выборе слов из долговременной памяти человек ориентируется в первую очередь на их семантические значения и связи. Использование других критериев, звукового сходства, например, свидетельствует либо о невозможности обращения к семантическому уровню (незнание семантического значения слова), либо о нарушении психической деятельности (шизофрения).
В этой связи можно вспомнить знаменитую фразу Л.В.Щербы Глокая куздра штеко будланула бокра и кудрячит бокренка. Невозможность установить сигматические и семантические отношения квазислов этой фразы заставляет человека при ее анализе обратиться к чисто знаковым (синтаксическим) отношениям. Предполагая грамматическую корректность фразы, можно исследовать ее синтаксические свойства: порядок слов, словоизменение, словообразование (бокр ↔ бокр-енок). Определенные ассоциации могут возникнуть и при анализе знаковой (звуковой) структуры корневых морфем. Так, глокость может показаться кому-то очень нехорошим качеством, а глагол кудрячить может ассоциироваться либо с существительным кудри, либо с глаголами корчить или корячить, либо с названием встроенной функции CDR (рекомендуется произносить «кудр») языка Лисп.
Несомненно, «высшие» аспекты значения передаются с помощью знаковых (синтаксических) средств, а проникнуть на эти «высшие» уровни не удается, не начав анализа структуры сообщения. Однако можно предположить, что по мере раскрытия внеязыковых связей знаков – даже до завершения анализа синтаксической структуры сообщения в целом – происходит переход на уровень информационной модели описываемой ситуации. Причем выявляемая информация (семантическая, сигматическая, прагматическая) не только пополняет эту модель, но и управляет дальнейшим анализом текста.

Проблема речевых ошибок
		Использование естественного языка в качестве средства общения (речевая деятельность  человека) неизбежно сопровождается теми или иными нарушениями языковых правил. Такие  нарушения – вне зависимости от того, обусловлены они неполнотой знаний человека о языке или же явлениями подсознания или случайными сенсомоторными «сбоями» (описки, опечатки, оговорки) – мы будем называть речевыми ошибками.
		Обнаружить речевую ошибку не всегда просто. Действительно, для получателя сообщения (реципиента) внешним признаком речевой ошибки служит появление в тексте какой-либо незнакомой ему речевой единицы. Однако такая «подозреваемая» речевая единица может оказаться и правильной конструкцией или формой (например, термином), не знакомой реципиенту.
		С другой стороны, абсолютно правильная на первый взгляд единица может быть ошибкой, обнаружить которую удается лишь на «высших» этапах анализа. Так, в предложении: Пуск ракеты осуществляется нажатием краской кнопки – все слова известны, синтаксические связи правильны; опечатка обнаруживается только на семантическом/смысловом уровне.
		Если одним из участников общения является компьютерная система (система автоматической обработки текста – АОТ-система), положение становится еще более сложным. И лингвистические знания, и интеллектуальные способности (в том числе – в плане работы с языком) такого «собеседника» пока весьма скромны.
		Отметим еще одно обстоятельство. Как бы ни разнились характер использования и назначение АОТ-систем (системы машинного перевода, работающие в пакетном режиме; системы обеспечения диалога с машиной на естественном языке), оснащение их средствами обнаружения и исправления речевых ошибок повышает устойчивость и эффективность функционирования таких систем, облегчает (в случае диалоговых систем) процесс общения человека с ЭВМ.

Классификация речевых ошибок
		Первый критерий классификации речевых ошибок (в соответствии с которым ошибки подразделяются на мотивированные и случайные), связан с упоминавшимся понятием индивидуальной языковой модели. Субъективное преломление языка (как знаковой системы социального уровня) в процессе его усвоения приводит к тому, что в ИЯМ не попадают (или попадают в искаженном варианте) некоторые языковые единицы и правила языка.
		Поэтому в речи конкретных носителей языка начинают проявляться некоторые индивидуальные особенности, либо вступающие в противоречие с языковыми нормами, либо нет.
		В первом случае мы имеем дело с мотивированными речевыми ошибками – точнее, с ошибками, мотивированными особенностями ИЯМ конкретного носителя языка (автора текста). К ошибкам такого рода относятся, например, ошибки в словоизменении (контейнерá – в форме именительного падежа множественного числа), орфографические ошибки в основах (еденица), некоторые пунктуационные ошибки, смешение слов-паронимов (представить – предоставить), нарушение лексической сочетаемости (делать горе), искажение фразеологизмов (не так страшен черт, как его малютки).
		Ошибки, обусловленные внешними по отношению к ИЯМ факторами: сбой речевого аппарата человека, несвоевременное переключение регистра клавиатуры, нажатие соседней клавиши, сбой на линии связи с ЭВМ – мы будем называть случайными. Как правило, мотивированные речевые ошибки регулярно повторяются в речи носителя языка, а случайные ошибки могут как повторяться (например, при западании клавиши), так и не повторяться. Отметим, что иногда отличить случайную ошибку от мотивированной сложно. Так, употребление слова представить вместо предоставить в контексте представлено право может быть или результатом случайной ошибки (пропуск буквы), или результатом мотивированной ошибки (смешения паронимов).
		Мотивированные речевые ошибки могут различаться степенью серьезности (грамматичности). Помимо серьезных, абсолютно недопустимых грамматических ошибок – типа орфографических ошибок в основах или смешения слов – возможны и ошибки, в результате которых появляются «полуграмматичные» формы (контейнерá, сидевши), которые имеют в словарях стилистические пометы: просторечное, устарелое, разговорное, областное и др.
		Следующий критерий классификации ошибок (мотивированных и случайных) связан с языковыми уровнями, нормы (правила) которых оказываются нарушенными в результате речевых ошибок. В соответствии с этим критерием  речевые ошибки можно классифицировать так:
1) орфографические ошибки: пропуск одной буквы, замена одной буквы, перестановка двух рядом стоящих букв, одна лишняя буква (отдельно может рассматриваться случай удвоения буквы), замена буквы русского алфавита буквой латиницы и др.;
2) морфологические (словоизменительный уровень) ошибки: ошибки в окончаниях (флексиях) при склонении и спряжении слов (рассматриваются различные подклассы таких ошибок), употребление отсутствующих в языке форм слов, несоблюдение правил чередования в основе, употребление незнакомых вариантов слов, испытывающих колебания в роде, одушевленности;
3) синтаксические ошибки: ошибки в моделях управления слов-предикатов, пунктуационные ошибки, нарушение обычного порядка слов (в том числе, в устойчивых словосочетаниях), вставка пробела внутрь слова, пропуск пробела (в том числе, случаи слитного и раздельного написания частиц не и ни);
4) лексико-семантические ошибки: употребление слов в необычном значении, нарушение лексической сочетаемости, семантические противоречия.

Общение человека с системой ИИ (естественный язык и естественность общения) 
Наиболее существенными и привлекательными (в контексте задачи общения с системой ИИ)  свойствами ЕЯ являются:
- максимально широкое использование его человеком в своей повседневной деятельности (это избавляет от необходимости специального изучения формализованного языка общения с ЭВМ и от трудностей, связанных с формулировкой заданий и запросов на таком языке);
- возможность использования естественного языка для выражения качественно различного содержания с любой доступной или желательной человеку степенью строгости и полноты (что гарантирует чрезвычайную широту сферы общения – как в плане охвата самых разнообразных предметных областей, так и в плане варьирования формулировок);
- его открытость и способность служить метаязыком для самого себя (что обеспечивает расширяемость используемых языковых средств).
Эти обстоятельства (обычно упоминается первое – не только потому, что оно действительно важно, но и потому, что оно абсолютно очевидно, лежит на поверхности) служат очень серьезными доводами в пользу общения с системами ИИ именно на естественном языке. Пока исследования носили чисто экспериментальный характер, эти доводы были достаточны. Однако в наше время, для которого характерна практическая переориентация работ, возникают новые проблемы, ранее остававшиеся в тени.
Часть из них: необходимость отчуждения системы от разработчика, надежность и устойчивость ее функционирования, эффективность реализации, наличие средств сопровождения – возникает и при создании традиционного программного обеспечения. Новые моменты связаны с использованием для общения с машиной именно естественного языка.
Среди проблем, особо актуальных на нынешнем этапе исследований и разработок, укажем:
- тщательный анализ вопроса целесообразности использования естественного языка в человеко-машинном общении;
- поиск ситуаций, в которых общение с машиной на естественном языке оправдано технологически и эргономически;
- выявление обстоятельств, учет которых обеспечивает человеку комфортные, естественные условия общения с компьютером;
- анализ пригодности использовавшихся ранее подходов и методов в изменившихся (практическая переориентация) условиях.
Перед автором некоторого искусственного языка общения с машиной (например, языка программирования), конечно же, не стоит вопрос о целесообразности использования созданного языка по прямому назначению. При оценке такого языка речь может идти о выразительных средствах, эффективной реализуемости, легкости усвоения и т.п. Отдельные неудачные решения могут быть изменены в ходе доработки (и отражены в разного рода пересмотренных сообщениях и др.). Объективация языка заключается в создании стандартов, трансляторов, формировании круга пользователей.
Естественный же язык изначально дан разработчикам систем ИИ извне, он объективирован (и активно используется в речевой практике) в большой социальной группе носителей данного языка, которые привыкли к вполне определенным, человеческим условиям общения (в том числе, рассмотренным в начале данной главы). Если эти условия (человеческий фактор) будут игнорироваться, язык общения, возможно, сохранив внешнее сходство с тем или иным ЕЯ, потеряет главное – естественность. А учет этих условий требует от разработчиков систем ИИ очень серьезных дополнительных усилий, поскольку предполагает воссоздание (моделирование) нетривиальных человеческих механизмов работы с языком, наделение системы ИИ – как «собеседника» пользователя – основными чертами (на уровне информационных процессов) собеседника-человека.
Поэтому при создании систем ИИ практической ориентации следует тщательно проанализировать, оправданы ли интеллектуальные и материальные затраты (весьма значительные, в нынешних условиях отсутствия в нашей стране рынка готового программно-информационного обеспечения) на их разработку, экономична ли (с учетом ресурсоемкости) их эксплуатация.
Серьезная практическая задача обеспечения общения с ЭВМ на естественном языке требует серьезного и практичного подхода. В каждой конкретной ситуации необходимо учитывать основательность доводов в пользу общения с системой именно на естественном языке, помнить о реально предоставляемых пользователю удобствах (в частности, об утомительности клавиатурного ввода, о возможностях – пока весьма скромных – технических средств обеспечения общения: устройства распознавания и синтеза звучащей речи, читающие автоматы).
Стремление разработчика или заказчика не отстать от моды, создать «высокоинтеллектуальную» информационную систему, оснащенную средствами естественноязычного интерфейса, не является достаточно веским основанием, а дилетантский подход (в этой новой и чрезвычайно сложной области особенно) не только не приводит к успеху, но и дискредитирует саму идею общения с ЭВМ на естественном языке.
Задачу обеспечения естественного общения человека с машиной можно принять без каких бы то ни было оговорок. Однако ниоткуда не следует, что наиболее удобным и естественным для пользователя (и целесообразным, с точки зрения разработчика) средством такого общения будет естественный язык. Пререкания с «непонятливым» компьютером, ориентированным на ведение диалога с человеком на так называемом ограниченном естественном языке, могут потребовать более значительных усилий, чем изучение искусственного формального языка общения.
Нас интересуют ситуации, в которых необходимость использования естественного языка диктуется глубинными внутренними причинами:
- характер поручаемых системе ИИ заданий, а следовательно, и адресуемых ей сообщений таков (носит предварительный, неформальный характер), что описать их на каком-либо формализованном языке крайне трудно;
- общение пользователя с машиной происходит эпизодически и/или в очень широкой сфере (изучение специального языка общения нецелесообразно, или же он становится необъятным).
Часто в таких случаях альтернативой использованию естественного языка может служить хорошо разработанная схема «выспрашивания» нужной системе информации с помощью традиционных средств организации дружественного интерфейса (меню, опережающий ввод и др.).
Весьма интересен феномен появления гибридных знаковых систем.
Мы знаем, что конструкции естественного языка (слова, словосочетания, предложения, тексты) давно и широко используются в человеко-машинном интерфейсе.
При формулировке общих требований к диалогу часто отмечается, что диалог должен вестись на родном языке пользователя (или на другом понятном и привычном ему языке).
Вспомним:
•	служебные слова в языках программирования, командных и других языках;
•	названия позиций меню, кнопок и т.п.;
•	средства поддержки пользователя:
- сообщения об ошибках,
- справочная информация, 
- внешняя документация.
Можно ли в подобных ситуациях говорить об общении с ЭВМ на естественном языке?
Вряд ли. Средства общения с традиционными компьютерными системами требуют предварительной экспликации, формализации той ситуации, о которой идет речь, привлечения знаний об используемых в системе способах структуризации знаний. Формулируя же адресуемые машине сообщения на естественном языке, человек может не знать: каким набором семантических единиц располагает система ИИ; в какие формальные структуры будет отображаться содержание сообщения; какие компоненты описываемой ситуации являются в настоящий момент значимыми, а какие –  второстепенными.
Более того, оказавшись в абсолютно новых условиях, человек, как правило, не сможет воспользоваться штатными языками общения с компьютером. Эти обстоятельства могут оказаться решающими при выборе языка общения с машиной как для профессионала (который на очередном этапе решения задачи не располагает пока адекватной формальной моделью и вынужден по этой причине отказаться от привычного для него искусственного языка), так и для конечного пользователя (для которого содержательный уровень общения является единственно доступным).

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

Лингвистические банки данных

		Под лингвистическими банками данных (ЛБД) понимаются представленные в электронной форме языковые источники (корпусы текстов) и лингвистические описания. Отметим, что в наше время, в ситуации, когда надежность работы систем оптического распознавания близка (на хороших по качеству печатных текстах) к 100%, в электронную форму легко переводимы и традиционные источники информации о языке. Поэтому можно считать, что в ЛБД можно перевести любые полиграфические источники: тексты на том или ином естественном языке, словари, справочники, книги по лингвистике. Спектр ЛБД достаточно широк: это как необработанные («сырые») корпусы текстов, так и тексты с некоторыми добавлениями, например грамматическими характеристиками слов, стилистическими пометами (разговорное, специальное и т.п.), или описаниями синтаксической структуры предложений (соответствующие корпусы текстов называют размеченными). Сюда также входят разнообразные компьютерные словари: частотные, грамматические, словоформ, тезаурусы, словари словосочетаний и моделей управления, своды грамматических правил и т.п.
		Различаться может и назначение лингвистических банков данных. Часть ЛБД предназначена для автоматизации деятельности лингвистов и разработчиков прикладных систем, часть - для непосредственного использования в системах обработки текста и речи: автокорректорах, системах распознавания текста и речи, информационно-поисковых системах.
		Отметим, что в качестве пользователя ЛБД может выступать как человек (исследователь-лингвист или разработчик программного продукта), так и тот или иной модуль компьютерной системы обработки текстов. В двух этих случаях требования к организации лингвистических банков данных и к степени эксплицитности, строгости и формальности представленных в них описаний естественного языка разнятся весьма существенно.
		Ситуация здесь несимметричная. Пользователь-человек часто может извлечь интересующую его информацию из ЛБД, встроенного в компьютерную систему обработки текстов. Однако компьютерная система обычно не может извлечь нужную для ее работы информацию непосредственно из ЛБД, ориентированного на человека. Особенно остра эта проблема для флективных языков, в частности, для русского языка.
		Так, во всех распространенных русскоязычных словарях (толковых, орфографических, словарях синонимов и антонимов и др.) входом в словарную статью служит так называемая начальная форма слова. Поскольку словари ориентированы на пользователя-человека, по умолчанию предполагается, что он знает правила русского словоизменения (склонения и спряжения) и может распознать в тексте любую форму интересующего его слова, т.е., восстановив начальную форму, добраться до соответствующей словарной статьи. Предполагается также, что он может решить и обратную задачу - употребить слово из словаря в требуемой грамматической форме.
		При использовании словарей в составе компьютерных систем обработки текстов ситуация иная. Самоочевидные для человека грамматические свойства слова, определяющие особенности его склонения/спряжения, должны быть тем или иным способом явно представлены в компьютерном словаре и в программах морфологического анализа и синтеза, позволяющих определять грамматические признаки словоформ текста и генерировать слова в требуемой форме.
		Как распределить знания о чрезвычайно сложных и запутанных правилах русского словоизменения между словарями и программными компонентами?

		Здесь возможны два решения:
•	в словаре описываются только словоизменительные признаки слов (тип и частные особенности склонения/спряжения), а работа по анализу и синтезу словоформ «поручается» программам морфологического компонента компьютерных систем;
•	в словаре приводятся все формы слов, каждой из которых сопоставлены все необходимые признаки (в частности, грамматические: число, падеж, лицо, время, наклонение и др.).
		В целом, задача построения и сопровождения лингвистически полного, обоснованного и покрывающего представительное подмножество выбранного естественного языка ЛБД, особенно в случае пользователя-программы, очень сложна. Ее решение требует привлечения квалифицированных специалистов в области лингвистики и инженерии знаний, создания необходимой инфраструктуры, серьезной финансовой и организационной поддержки (часто – на государственном уровне).

Формальная модель русской морфологии (словоизменения)
Словарь Зализняка
		Одним из широкодоступных (и активно используемых) русскоязычных ЛБД является электронный вариант фундаментального «Грамматического словаря русского языка» А.А.Зализняка. Текст словаря был перенесен на машинные носители в начале 80-х годов. С тех пор словари всех русскоязычных текстовых процессоров, словари практически всех экспериментальных и коммерческих систем машинного перевода и других АОТ-систем строятся на основе словаря Зализняка.
		Полиграфический вариант словаря Зализняка состоит из двух частей: «Грамматические сведения» (около 120 страниц) и собственно «Словарь» (около 740 страниц). В первой части представлена разработанная автором словаря с необычайной тщательностью оригинальная модель русского словоизменения (склонения и спряжения). Во второй приведено около 100 тысяч слов, которым приписаны грамматические индексы, характеризующие тип их словоизменения и схему ударения. Слова упорядочены по концам, что естественно и удобно для грамматического словаря, поскольку слова со сходным грамматическим поведением (одинаковыми суффиксами и окончаниями) располагаются компактными группами.
		Словарная статья в словаре Зализняка состоит из заголовка (начальная форма слова) и словарной (грамматической) информации. Для некоторых слов даются также дополнительные сведения, необходимые для различения вариантов. Статьи с заголовками лев, стричь и прихожая выглядят так:
лев мо 1*b (животное)
лев м 1a (денежная единица)
стричь нсв 8b (-г-)
прихожая ж (п 4a)
		По первому элементу словарной информации определяется грамматический класс (спрягаемое слово, слово субстантивного, адъективного или местоименного склонения 
эти термины будут разъяснены позже), для слов субстантивного склонения также одушевленность и род, для спрягаемых слов – вид. Если первый элемент – «п», то слово относится к словам адъективного склонения; «ж» – к словам субстантивного склонения, женского рода, неодушевленным; «мо» – к словам субстантивного склонения, мужского рода, одушевленным; «нсв» – к спрягаемым словам (глаголам) несовершенного вида.
		Если второй элемент – не цифра, то это означает, что слово изменяется по необычной модели (существительное прихожая изменяется по модели слов адъективного склонения). Остальные элементы словарной статьи либо уточняют тип склонения/спряжения, либо свидетельствуют о наличии в слове чередований (символ *), об отсутствии у слова некоторых форм или о других частных особенностях словоизменения. Буквенный индекс после цифры (или после символа *) характеризует схему ударения во всех формах описываемого слова; эта информация полезна при автоматизированной генерации фонетического словаря словоформ русского языка.
		Отметим, что исходный (полиграфический) вариант словаря Зализняка был ориентирован на пользователя-человека. Основной сценарий использования словаря предусматривал возможность просклонять/проспрягать любое слово из «Словаря» на основе его грамматического описания и правил, приведенных в «Грамматических сведениях». Эти операции, вообще говоря, требовали выполнения некоторых трудноформализуемых действий, определенной языковой компетенции: поиск уместных грамматических таблиц, определение типа чередования, рассуждения по аналогии. Поэтому непосредственное использование словаря Зализняка (даже в электронном виде) в составе компьютерных систем обработки текста/речи затруднительно.
		Разработчики компьютерных словарей, базирующихся на словаре Зализняка, выбирают обычно один из трех путей:
- генерация на основе словаря Зализняка словаря русских словоформ;
- использование электронного «Словаря» в исходной форме и разработка (достаточно сложных) алгоритмов, моделирующих работу с «Грамматическими сведениями»;
- создание на основе словаря Зализняка формальной модели словоизменения и необходимое переструктурирование словарной части (явное введение в словарную статью некоторой информации из «Грамматических сведений»), позволяющее существенно упростить алгоритмы.
		После подобных преобразований компьютерный словарь может использоваться для решения двух практически важных задач:
•	задача морфологического анализа – определения начальной формы слова по произвольной словоформе (и, возможно, грамматических признаков словоформы); 
•	задача синтеза – построения всех форм (или указанной формы) слова по начальной форме.
		Одна из первых формальных моделей русского словоизменения на базе словаря Зализняка (третий из указанных выше путей) была разработана еще в середине 80-х годов на кафедре алгоритмических языков факультета ВМК МГУ под руководством М.Г.Мальковского. Модель была реализована на лиспоподобном языке программирования Плэнер (ЭВМ БЭСМ-6, а позже – МВК «Эльбрус-2» и IBM-совместимые ПК). При этом широко использовались динамические структуры, мощные средства обработки списков и сопоставления образца с выражением. 
		В плэнерских структурах данных явно указывались все морфологические свойства для каждого слова, включая чередования в основе слова. Поэтому плэнерское представление достаточно легко воспринималось человеком, явно отражало морфологические особенности описываемых в компьютерном словаре слов.
		Однако язык Плэнер является интерпретируемым, а следовательно, довольно медленно работающим, что затрудняет его применение в системах, к которым предъявляются высокие требования по быстродействию. Обработка сложной структуры списков требует существенных затрат машинного времени, даже при реализации алгоритма их обработки на компилируемых языках, ориентированных на написание эффективных программ (С, С++). Поэтому было принято решение о переходе к другой структуре словаря и соответствующей модификации алгоритмов анализа и синтеза.
		Плэнерские структуры, описывающие морфологические особенности всех различных классов слов, были пронумерованы. Затем словам/основам и флексиям были сопоставлены соответствующие номера классов. При чередовании в основе и при наличии у слова супплетивных форм, образованных от другой основы (хороший – лучше), были организованы дополнительные входы в словарные статьи.
		Новое представление словаря трудно воспринимаемо для человека. Однако унификация и упрощение структур данных позволили создать условия для значительного увеличения скорости обработки.
Формализация русского словоизменения
		В Формальной модели русского словоизменения (ФМРС) множество слов русского языка разбивается на два основных класса – неизменяемые (Н-слова) и изменяемые, т.е. склоняемые или спрягаемые (И-слова). Совокупность форм И-слова (словоформ) образует его парадигму. В каждой словоформе можно выделить основу и окончание, или флексию (возможно, пустую, которую мы обозначим: -∅), соответствующую конкретной форме И-слова; за флексией может следовать постфикс, например, возвратная частица ся/сь.
		С основой И-слова, Н-словом, флексией и словоформой связывается описание значения соответствующего объекта, включающее описание его грамматических характеристик; лексических связей (синонимы, производные слова); семантического значения (ассоциированные с объектом понятия). Грамматические характеристики определяют сочетаемость основ и флексий и синтаксические признаки объектов всех четырех типов.
		К грамматическим характеристикам морфологического уровня относятся:
морфологический (словоизменительный) класс – М-класс, парадигматический класс – П-класс, чередование, исключение. Синтаксическим показателем является синтаксический класс (С-класс). Если М-класс определяет, как изменяется слово (склоняется, спрягается), то С-класс характеризует его синтаксическое поведение (сочетаемость с другими словами) Как словоизменительные, так и синтаксические признаки определяются набором значений грамматических переменных.
		Грамматическая переменная (ГП) – переменная одного из следующих типов: одушевленность, род, число, падеж, вид, лицо, залог, возвратность, время, наклонение, степень – принимает закодированное целым числом значение из некоторого множества допустимых. Значение ГП род, например, кодируется так: мужской – 1, женский – 2, средний – 3. Если значение неопределенно, указывается список возможных значений или число 0 (обозначает любое допустимое значение ГП).
		Совокупность ГП, по которым изменяется И-слово (свободных ГП), определяет его парадигму, а спектр значений этих переменных – число элементов парадигмы. Множество И-слов с общим набором ГП, общим набором свободных ГП и общим спектром значений переменных образует М-класс. Основе (и словоформе) сопоставлен упорядоченный набор (вектор) значений соответствующих ГП. Так, например, с основой лев- слова лев (денежная единица) связан такой вектор (7 8 2 1 0 0) – слово 7-го М-класса, 8-го П-класса, неодушевленное (2), мужского рода (1), значения ГП число и падеж не определены (0 и 0). Для словоформы левами вектор будет иметь вид (7 2 1 2 5), здесь добавились значения ГП число (2 – множественное) и падеж (5 –  творительный).
		Понятие М-класса является уточнением традиционного понятия «часть речи»: 7-й класс образован в основном существительными, 8-й – прилагательными, 9-й – глаголами. В ФМРС рассматриваются три класса склоняемых И-слов: местоименные (М-класс номер 5), субстантивные (класс номер 7), адъективные (класс номер 8) и один класс спрягаемых (класс номер 9). Представители 5-го и 8-го М-классов изменяются по родам, числам и падежам, 7-го – по числам и падежам, 9-го – по лицам, родам, числам и временам. Отсутствие у И-слова одной или нескольких форм (например, формы родит. падежа множ. числа у слова мгла, форм ед. числа у слова ножницы) не мешает отнести его к М-классу номер 7.
		Подмножество М-класса, представители которого при совпадающих значениях свободных ГП имеют одинаковые флексии, образует парадигматический класс. В ФМРС рассматриваются 24 П-класса для слов субстантивного склонения, 8 – для слов адъективного склонения, 2 – для слов местоименного склонения, 9 – для спрягаемых слов. К 1-му П-классу субстантивных И-слов относятся, например, существительные завод и артист (флексии: -∅, -а, -у, -∅ или -а, -ом, -е – для шести традиционных падежей единственного числа; -ы, -ов, -ам, -ы или -ов, -ами, -ах – для множественного); к 11-му П-классу – карта и корова; к 21-му – болото. К 1-му П-классу местоименных И-слов относятся: притяжательное прилагательное отцов, существительное кабельтов (не изменяется по родам), ко 2-му П-классу – местоимение мой, прилагательное лисий, порядковое числительное третий.
		Хотя П-классы задают более детальную классификацию сочетаемости основ с флексиями чем традиционные типы склонения и спряжения, они недостаточны для описания многих частных особенностей русского словоизменения. Эти особенности можно было бы учесть с помощью еще более дробной классификации П-классов, однако в ФМРС используются другие методы.
		Как исключения описываются случаи сочетания основы с «нестандартной» для данного П-класса и данной формы флексией: -а в форме именит. падежа множеств. числа существительных вместо характерной для 1-го П-класса флексии -ы (глаза, но заводы), пустая флексия вместо флексии -ов в родит. падеже множеств.  числа (глаз, но заводов). Исключением считается и наличие у некоторых существительных 2-го родительного (партитивного) и 2-го предложного (локативного) падежей: кусок сахару, в шкафу, но из сахара, о шкафе. Всего в ФМРС учитываются 26 исключений такого вида.
		К особенностям словоизменения относятся и чередования в основе. В ФМРС учтено 55 чередований, например: ова - у (рис-ова-ть - рис-у-ю), та - щ (клеве-та-ть - клеве-щ-у), е - <пусто> (царев-е-н - царев-н-а). Для И-слов с чередованиями достаточно рассматривать только один «стандартный» вариант основы, указывая тип и контекст чередования в описании значения основы. Так, для стандартного варианта основы царевн- указывается, что при пустой флексии перед последней буквой основы вставляется буква е. Относительно редкие чередования (встречающиеся у 1-3 слов) в ФМРС учитываются по-иному: парадигмы таких слов задаются несколькими основами и Н-словами, образующими семейство слова (основы зай-, зайд- и заш- и Н-слово зайти для глагола зайти). Семейства вводятся и для слов с супплетивными формами (хороший - лучше) или уникальными наборами флексий (некоторые числительные, личные местоимения).
		В синтаксический класс объединяются слова и конструкции с общим набором ГП и общими синтаксическими функциями. Каждому представителю некоторого С-класса сопоставлен (как и в случае М-классов) вектор значений характерных ГП. Для большинства И-слов номер С-класса и набор ГП совпадают с номером и набором ГП М-класса. Так, многие существительные – С-класс номер 7 –  относятся и к 7-му М-классу. Однако некоторые слова изменяются по «необычной» модели: существительные прохожий, гончая склоняются как представители 8-го М-класса.

Библиотека программ «РУССКАЯ МОРФОЛОГИЯ»
Основные программы
Морфологический анализ знакомых слов. Программа МОРФ1
		Программа МОРФ1 строит все возможные разбиения входной словоформы на основу и флексию и ищет соответствующие части в словаре (первоначально МОРФ1 пытается найти в словаре совпадающее со словоформой Н-слово, а затем последовательно рассматривает словоформу как основу с пустой флексией, основу с флексиями длиной 3, 2 и 1) или неизменяемое слово.
		Проверку правильности разбиения – сочетаемости основы и флексии – осуществляет вспомогательная программа, она же устанавливает  значения ГП, определяемые флексией. Когда МОРФ1, отщепив флексию, не может найти полученную основу в словаре, происходит обращение к подпрограмме, применяющей к основе правила чередования. Если и после применения правил чередования найти основу в словаре не удалось, слово признается незнакомым и формируется обращение к программе морфологического анализа незнакомых слов МОРФ2 – список вариантов трактовки словоформы (грамматически корректные разбиения на основу и флексию, неизменяемое слово). 
		Результат работы МОРФ1 (для знакомого слова) – список вариантов анализа, каждый из которых содержит: грамматические признаки словоформы и ссылку на словарную статью, описывающую семантическое значение слова.
Примеры:
стекла 	(7 2 3 1 2)	- существительное (неодуш., ср. род) стекло 
					в форме: ед. число, родит. падеж
			(7 2 3 2 (1 4)) - существительное (неодуш., ср. род) стекло 
				в форме: мн. число, именит. или винит. падеж
			(9 1 1 3 2 1 1) - глагол стечь 
						 в форме: прош. вр., женск. род, ед. число
		Упрощенный вариант программы МОРФ1 – программа МОРФ3 – решает так называемую задачу лемматизации: определяет только начальную форму слова, не формируя список грамматических характеристик словоформы.
Примеры:
стеки			стек,   стечь
стекла		стекло, стечь
стеками		стек
Морфологический анализ незнакомых слов. Программа МОРФ2
		На вход программы поступает сформированный МОРФ1 список вариантов трактовки словоформы.
Пример (словоформа квазибиологом):
		квазибиологом+∅ (ср. космодром/управдом)
		квазибиолог+ом   (ср. биолог+ом)
		квазибиологом    (ср. бегом)
		При обработке незнакомого слова МОРФ2 учитывает флексию и строение основы. В большинстве случаев исследование флексии не позволяет однозначно установить не только П-класс, род слов субстантивного склонения, вид спрягаемых слов, но даже М-класс анализируемого слова, так как, например, флексия -а встречается у слов всех четырех рассматриваемых М-классов (стол-а, красив-а, дядин-а, ворош-а). Для уточнения грамматических признаков незнакомых слов МОРФ2 учитывает следующие составляющие (диагностические сегменты) основы: префикс, суффикс или некоторую цепочку букв в конце основы, последнюю букву основы.
		По префиксу можно обнаружить некоторые Н-слова и установить вид некоторых глаголов. Анализ суффикса помогает установить М-класс, П-класс, род (а иногда и одушевленность) слова субстантивного склонения, вид глагола или даже все нужные (описываемые в словарной статье) грамматические признаки слова. По последней букве основы легко уточняется П-класс, а иногда и М-класс слова. Программа МОРФ2 работает с таблицами, содержащими 28 префиксов и 67 суффиксов. Анализ незнакомого слова МОРФ2 начинает с варианта расщепления с максимальной длиной флексии.
		Если анализируется не отдельно взятое слово, а слово в составе предложения, появляется возможность учета контекста (синтаксических связей данного слова с соседними). Информация о контексте передается программам морфологического анализа от объемлющих их программ синтаксического анализа с помощью предсказаний – списка ожидаемых грамматических признаков обрабатываемого слова. Так, при анализе незнакомого слова Верхневартовск в контексте приехала из далекого Верхневартовска ожидаемые характеристики последнего слова фрагмента таковы: неодушевленное существительное в форме единственного числа, родительного падежа.
		В таких ситуациях результат работы МОРФ2 сопоставляется с предсказаниями, и, в случае соответствия, запоминается. Если же предсказание не подтвердилось, начинает обрабатываться другой вариант разбиения словоформы. Если ожидаемый результат не получен, либо слово признается неизменяемым, либо в нем ищутся и исправляются ошибки.
		Для каждого отобранного варианта формируются результаты анализа словоформы  (и вариант/варианты новой словарной статьи).
Пример (словоформа квазибиологом):
(7 0 1 1 (1 4))	- существительное (одуш. или неодуш., ср. род) 
				квазибиологом в форме: ед. число, именит. или винит. падеж
(7 1 1 1 5)	- существительное (одуш., муж. род) 
				квазибиолог в  форме: ед. число, творит. падеж
(11) 			– неизменяемое слово (возможно, наречие)
Заполнение словаря по грамматическим описаниям слов. Программа СЛОВ1
		Основная сервисная программа автоматической генерации словарных статей – программа СЛОВ1. В ходе ее разработки были составлены таблицы соответствия словарной информации из словаря Зализняка и  словарной информации ФМРС. Отметим, что программа СЛОВ1 автоматизирует трудоемкую, требующую хорошего знания ФМРС работу по составлению словарных статей. Действия, выполняемые программой, зачастую весьма нетривиальны из-за различий морфологической модели словаря Зализняка, и ФМРС. На вход программы поступает словарная статья, взятая из словаря Зализняка или (если такого слова там нет) сформированная экспертом.
		Программа автоматически определяет: 1) основу записываемого в словарь системы слова; 2) номера М-класса, П-класса, С-класса; 3) наличие чередований и их контекст; 4) наличие других частных особенностей словоизменения. При работе с программой словарные статьи кодируются по определенным стандартным правилам, в частности, заменяются символы, отсутствующие на клавиатуре.
		По первому элементу словарной информации из словаря Зализняка в большинстве случаев определяется номер М-класса, у слов субстантивного склонения также одушевленность и род, у спрягаемых слов – вид. Если, например, этот элемент «п», то слово относится к 8-му М-классу; «ж» – к 7-му М-классу, женскому роду, неодушевленное; «мо» – к 7-му М-классу, мужскому роду, одушевленное; «нсв» – к 9-му М-классу, несовершенному виду.
		После определения М-класса происходит переход на соответствующую ветвь алгоритма, где по второму элементу определяется номер П-класса. Если второй элемент не цифра (это означает, что слово изменяется по необычной модели), СЛОВ1 фиксирует несовпадение номеров С-класса и М-класса (т.е. наличие соответствующего исключения) и формирует необходимый фрагмент словарной статьи.
		Остальные элементы исходной словарной статьи либо уточняют номер П-класса, либо свидетельствуют о наличии в слове чередований, исключений или об отсутствии у слова некоторых форм. Например, символ «П2» означает, что у слова есть второй предложный падеж (локатив), символ «*» является признаком чередования. Для определения конкретного номера чередования СЛОВ1 анализирует строение начальной формы слова. Так, при обработке первого варианта слова лев номер чередования (4 – чередование: ь - е) определяется по буквам ле, стоящим перед последней согласной основы (буква в в данном случае неинформативна). Стандартный вариант основы (льв-) определяется по номерам П-класса и чередования.
		Результатом работы программы СЛОВ1 является словарная статья или список таких словарных статей – в случае, когда слово из словаря Зализняка представляется в ФМРС семейством Н-слов и/или основ И-слов (для спрягаемых слов, например, программа строит словарную статью, описывающую личные формы глагола и деепричастия, и несколько статей для причастий).
Заполнение словаря по тексту. Программа СЛОВ2
		Программа СЛОВ1 используется в ситуации, когда список слов, предназначенных для включения в компьютерный словарь, составлен заранее. Другая технологическая схема предполагает
выявление незнакомых слов непосредственно в характерных текстах.
		Режимы/сценарии работы с программой различаются:
 - глубиной лингвистического анализа текста (пословный анализ, частичный синтаксический анализ, полный синтаксический анализ, синтактико-семантический анализ);
 - «степенью самостоятельности» программ формирования словаря (работа без обращения за помощью к человеку, работа в диалоге с пользователем/администратором и под его контролем)
Морфологический синтез форм слова. Программа ФОРМ1
		По словарной статье (знакомого слова) и набору значений ГП строится соответствующая словоформа.
Примеры:
ЛЕВ (животное), творит. падеж, ед. число		(7 0 0 1 5)	  ЛЬВОМ
ЛЕВ (ден.единица), творит. падеж, ед. число	(7 0 0 1 5)	  ЛЕВОМ
Морфологический синтез парадигмы. Программа ФОРМ2
		По словарной статье (знакомого слова)  строится массив всех форм этого слова. Порядок элементов массива определяется номером М-класса.
Примеры:
		синтез всех форм знакомого существительного КАССИРША
КАССИРША		КАССИРШИ		- им.падеж,   ед. и мн.число
КАССИРШИ		КАССИРШ		- род.падеж,  ед. и мн.число
КАССИРШЕ		КАССИРШАМ		- дат.падеж,  ед. и мн.число
КАССИРШУ		КАССИРШ		- вин.падеж,  ед. и мн.число
КАССИРШЕЙ		КАССИРШАМИ		- твор.падеж, ед. и мн.число
КАССИРШЕ		КАССИРШАХ		- предл.падеж,ед. и мн.число
		синтез всех форм знакомого глагола ВОРОШИТЬ
ВОРОШИТЬ 					- начальная форма
ВОРОШИ	ВОРОШИТЕ 			- формы повелит. наклонения
ВОРОШУ 	(БУДУ ВОРОШИТЬ)		- 1 лицо, ед.ч, наст.и буд.вр. 
ВОРОШИШЬ	(БУДЕШЬ ВОРОШИТЬ) 	- 2 лицо, ед.ч, наст.и буд.вр.
ВОРОШИТ 	(БУДЕТ ВОРОШИТЬ)		- 3 лицо, ед.ч, наст.и буд.вр.
ВОРОШИМ 	(БУДЕМ ВОРОШИТЬ)		- 1 лицо, мн.ч, наст.и буд.вр. 
ВОРОШИТЕ	(БУДЕТЕ ВОРОШИТЬ) 	- 2 лицо, мн.ч, наст.и буд.вр.
ВОРОШАТ 	(БУДУТ ВОРОШИТЬ)		- 3 лицо, мн.ч, наст.и буд.вр.
ВОРОШИЛ ВОРОШИЛА ВОРОШИЛО ВОРОШИЛИ  - формы прош.времени
ВОРОША 	ВОРОШИВ			- деепричастия
		Пусть написана управляющая программа, получающая на входе некоторую словоформу, обращающаяся к программе МОРФ1 (и – если слова нет в словаре – к МОРФ2) и генерирующая все формы (программа ФОРМ2) для каждого варианта анализа. Среди этих форм обязательно должна быть входная словоформа. 
Примеры:
обработка незнакомого слова ХРЮША
ВАРИАНТ 1 
склонение по образцу слова НОЖ/БОГАЧ 
* значение ГП "одушевленность" неизвестно *
ХРЮШ 			ХРЮШИ 
ХРЮША 		ХРЮШЕЙ 
ХРЮШУ 		ХРЮШАМ 
ХРЮША / ХРЮШ 	ХРЮШЕЙ / ХРЮШИ 
ХРЮШОМ 		ХРЮШАМИ 
ХРЮШЕ 		ХРЮШАХ 
ВАРИАНТ 2 
склонение по образцу слова МАРШ 
* значение ГП "одушевленность" неизвестно *
ХРЮШ 			ХРЮШИ 
ХРЮША 		ХРЮШЕЙ 
ХРЮШУ 		ХРЮШАМ 
ХРЮША / ХРЮШ 	ХРЮШЕЙ / ХРЮШИ 
ХРЮШЕМ 		ХРЮШАМИ 
ХРЮШЕ 		ХРЮШАХ 
ВАРИАНТ 3 
склонение по образцу слова ТУЧА/КАССИРША 
* значение ГП "одушевленность" неизвестно *
ХРЮША 		ХРЮШИ 
ХРЮШИ 		ХРЮШ 
ХРЮШЕ 		ХРЮШАМ 
ХРЮШУ 		ХРЮШ / ХРЮШИ 
ХРЮШЕЙ 		ХРЮШАМИ 
ХРЮШЕ 		ХРЮШАХ 

ВАРИАНТ 4 
склонение по образцу слова СВЕЖИЙ 
ПОХРЮШЕЕ 		ХРЮШЕЕ 
ХРЮШ 		 	ХРЮША 		ХРЮШЕ 		ХРЮШИ 
ХРЮШИЙ	   	ХРЮШАЯ		ХРЮШЕЕ 		ХРЮШИЕ
ХРЮШЕГО	   	ХРЮШЕЙ		ХРЮШЕГО 		ХРЮШИХ
ХРЮШЕМУ 	   	ЖРЮШЕЙ		ХРЮШЕМУ 		ХРЮШИМ
ХРЮШЕГО&ХРЮШИЙ	ХРЮШУЮ		ХРЮШЕЕ 		ХРЮШИХ&ХРЮШИЕ 
ХРЮШИМ 	 	ХРЮШЕЙ		ХРЮШИМ 		ХРЮШИМИ
ХРЮШЕМ 		ХРЮШЕЙ		ХРЮШЕМ 		ХРЮШИХ
ВАРИАНТ 5 
спряжение по образцу слова ТОЧИТЬ/СЛЫШАТЬ 
ХРЮШИТЬ 
ХРЮШИ		ХРЮШИТЕ 
ХРЮШУ 		(БУДУ ХРЮШИТЬ) 
ХРЮШИШЬ 		(БУДЕШЬ ХРЮШИТЬ) 
ХРЮШИТ 		(БУДЕТ ХРЮШИТЬ) 
ХРЮШИМ 		(БУДЕМ ХРЮШИТЬ) 
ХРЮШИТЕ 		(БУДЕТЕ ХРЮШИТЬ) 
ХРЮШАТ 		(БУДУТ ХРЮШИТЬ) 
ХРЮШИЛ	ХРЮШИЛА	ХРЮШИЛО	ХРЮШИЛИ 
ХРЮША 	ХРЮШИВ 
ВАРИАНТ 6 
неизменяемое слово типа АНТРАША 
ХРЮША
		Заметим, что если бы слово хрюша анализировалось с предсказаниями, результат был бы более точен. Так, при предсказании «существительное женского рода» был бы выдан только третий вариант, при предсказании «форма глагола – только пятый.
обработка незнакомого слова КРОВАТЬ
ВАРИАНТ 1 
спряжение  по образцу слова ПИРОВАТЬ 
* значение ГП "вид" неизвестно *   
   (выбран несовершенный вид)   
КРОВАТЬ
КРУЙ		КРУЙТЕ 
КРУЮ		(БУДУ КРОВАТЬ) 
КРУЕШЬ	(БУДЕШЬ КРОВАТЬ) 
КРУЕТ 	(БУДЕТ КРОВАТЬ) 
КРУЕМ 	(БУДЕМ КРОВАТЬ) 
КРУЕТЕ 	(БУДЕТЕ КРОВАТЬ) 
КРУЮТ 	(БУДУТ КРОВАТЬ) 
КРОВАЛ 	КРОВАЛА 	КРОВАЛО 	КРОВАЛИ 
КРУЯ 		КРОВАВ 
ВАРИАНТ 2 
склонение по образцу слова ПЕЧАТЬ 
* значение ГП "одушевленность" неизвестно *
КРОВАТЬ		КРОВАТИ 
КРОВАТИ 		КРОВАТЕЙ 
КРОВАТИ 		КРОВАТЯМ 
КРОВАТЬ	 	КРОВАТЕЙ / КРОВАТИ 
КРОВАТЬЮ 		КРОВАТЯМИ 
КРОВАТИ 		КРОВАТЯХ 
ВАРИАНТ 3 
неизменяемое слово типа ДЕСКАТЬ