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

Поскольку эффективность простого поиска низка, возникает необходимость определения пути, по кото­рому следует начать поиск в первую очередь. При эвристическом поиске, например алгоритме А*, разра­ботанном на первых этапах исследования искусствен­ного интеллекта, руководствуются оценочными функ­циями, которые не всегда бывают точными (имеют априорные значения). Об алгоритме А* рассказано ниже.

В эпоху инженерии знаний возникла идея реализа­ции выводов (поиска) на основе знаний. Шире стали применять эвристические знания (в смысле не обяза­тельно достоверных знаний, т. е. знаний, содержащих нечеткости). В качестве наиболее характерного примера можно привести программу AM, которая откры­вает новые математические понятия. Как подчеркнул создатель этой программы Д.Б. Ленат, эвристические знании в ней играют важную роль. Эта программа также будет рассмотрена ниже.

Алгоритм А*

Большинство поисковых задач можно сформулиро­вать как задачи поиска в пространстве состояний пути от исходного состояния заданной задачи до целевого состояния путем повторения возможных преобразова­ний (с помощью операторов). При этом для организа­ции поиска в пространстве состояний удобно исполь­зовать дерево поиска (или его более общую форму — граф). К основным методам систематического просмо­тра пространства состояний относятся вертикальный и горизонтальный поиск. В алгоритме А* использова­ны априорные оценки стоимости пути до целевого состояния (разновидность эвристических знаний), что обеспечивает высокую эффективность поиска.

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

2	4	3		1	2	3
1	8	5		4	5	6
7		6		7	8
Начальное состояние                                   Целевое состояние

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

1) перемещение пустого квадрата влево (при этом слева есть квадрат);

2) перемещение пустого квадрата вверх (при этом вверху есть квадрат);

3) перемещение пустого квадрата вправо (при этом справа есть квадрат);

4) перемещение пустого квадрата вниз (при этом внизу есть квадрат).

Используя эти операторы, будем осуществлять поиск в пространстве состояний. Рассмотрим также сле­дующую оценочную функцию как функцию, регламен­тирующую выбор эффективного направления поиска. Пусть f(n) — стоимость оптимального пути к цели от первой вершины (начального состояния) через n вер­шин дерева поиска. Разделим f(n) и представим ее следующим образом:

f(n)=g(n)+h(n),

где    g(n) - стоимость оптимального пути от первой вершины до n-й вершины;

h (n) - стоимость оптимального пути от n-й вер­шины до цели.

Будем считать, что перемещение одной шашки в игре в восемь имеет стоимость 1, а до цели ведет оптимальный путь с минимальной стоимостью.

В процессе поиска в общем случае нельзя точно знать f(n), поэтому рассмотрим априорное значение . В момент прохождения n-й вершины g(n) из­вестно, поэтому можно записать

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

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

Здесь важно, что , а именно если ап­риорное значение стоимости от n-й вершины до цели () меньше или равно истинной стоимости опти­мального пути к цели (), то это гарантирует, что обязательно будет найден оптимальный путь. Поиск с использованием функции () называется алгоритмом А*.

В этой игре в качестве ) выбрано число шашек, находящихся не на своих местах, причем  (не достигнем цели, пока число перемещений меньше числа шашек, находящихся не на своих местах). Сле­довательно, рис. 6.1 также представляет поиск по ал­горитму А*. Если же выбрать , то мы имеем горизонтальный поиск, при котором прежде всего рас­крываются близлежащие вершины (число таких вер­шин возрастает), оптимальный путь при этом в конце концов находится. Если ,то мож­но доказать, что число вершин, раскрытых при поиске с использованием функции , всегда меньше, чем при поиске с использованием функ­ции . А именно, h(n) можно рас­сматривать как объем эвристических знаний, предска­зывающих стоимость пути до цели, следовательно, объем эвристических знаний h₂(n) больше, чем h₁(n).

Программа  AM

Программа AM, разработанная Д. Б. Ленатом, предназначена для «открытия»    новых понятий в обла­сти целых чисел. Для руководства «открытиями» (что можно рас

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

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

На рис. 6.2 показана структура фрейма ПРО­СТЫЕ ЧИСЛА, открытого этой программой. Эвристи­ческие знания описываются в форме правил (типа ЕСЛИ—ТО) и добавляются в соответствующие слоты фреймов. Глобальная структура управления основана на механизме «списка заявок»; задания, которые предстоит выполнить, прежде всего, регистрируются в списке заявок с указанием приоритета («интереса»), из списка выбирается задание с наиболее высоким интересом и выполняется. Во время выполнения зада­ния подбираются соответствующие правила (подби­раются также правила из фреймов высшего уровня через указатели в слоте ОБОБЩЕНИЕ текущего фрейма, затем эти правила используются.

Устанавливаются слоты ОПРЕДЕЛЕНИЯ, ПРИМЕРЫ, ОБОБЩЕНИЯ, СПЕЦИАЛИЗАЦИЯ, ПРЕДПОЛОЖЕНИЯ, АНА­ЛОГИ, ИНТЕРЕС, ЦЕННОСТЬ

(вводится оценка — число от 0 до 1000)

Рис. 6.2. Фрейм понятия «простые числа», полученный про­граммой AM

Функции правил можно классифицировать следую­щим образом:

1) Вставка содержимого в слот специального по­нятия выполняется при перечислении ПРИМЕРОВ некоторого понятия, при построении ПРЕДПОЛОЖЕ­НИЙ, при обновлении слота ЦЕННОСТЬ.

Кроме пра­вильных примеров в слоте ПРИМЕРЫ можно приве­сти подтверждающие граничные примеры (в слоте ГРАНИЦЫ), контрпримеры (в слоте НЕУДАЧА), граничные контрпримеры (в слоте ГРАНИЦЫ-НЕ­УДАЧИ). В слоте ПРЕДПОЛОЖЕНИЯ определяют­ся эквивалентность с другим понятием, особенно­сти, обобщения, связь через некоторый преди­кат и т. п.

2) Проверка слотов некоторого понятия — прове­ряя правильность содержимого слота, обнаружи­ваются интересные факты через систематизацию и связь с другими понятиями (обобщение, особенно­сти и т. д.).

3) Генерация новых понятий — с этой целью ис­пользуются обобщения, выделение особенностей, об­работка контрпримеров, подобие, связь с обратным явлением, синтез функций, проекция, упрощение, пря­мое произведение множеств и другие операции. Но­вый фрейм создается и вводится в слот ОПРЕДЕЛЕ­НИЯ (как описание на языке ЛИСП этого опреде­ления);

4) Регистрация нового задания в списке заявок.

5) Критерии оценки интереса к понятию и зада­нию — используются симметрия, частота появления понятия, индивидуальность, связь с другими интерес­ными понятиями, непрерывность по отношению к по­следнему заданию (механизм концентрации внима­ния) и другие факторы.

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

Программа AM запускалась несколько раз, всего сгенерировано (открыто) около 200 новых понятий. Примерно половина из них представляют определен­ный интерес и хорошо известны в математике. К ним относятся следующие понятия:

1) простые числа (2, 3, 5, 7, 11, 13, 17, 19, …: имеют только два делителя) — определяются так, как на рис. 6.2;

2) квадраты простых чисел (4, 9, 25, 49, 121, 169, 289 …: имеют три делителя);

3) однозначность разбиения на простые множите­ли (все числа однозначно представляются в виде произведения простых чисел);

4) все числа (больше 1) можно представить в виде суммы простых чисел;

5) четные числа больше 2 можно представить в виде суммы двух простых чисел (гипотеза Гольдбаха);

6) существование пар простых чисел Р и Р + 2 и другие понятия.

Разумеется, самой программе AM трудно давать названия новым понятиям, такие названия, как простые числа, даются уже позже людьми, интерпрети­рующими их смысл.

Существенное отличие программы AM от поиска при решении традиционных задач заключается в от­сутствии строгих правил поиска. Цель поиска этой программы — максимально проявить самостоятель­ность (выполнять задания с наивысшим уровнем приоритета). Поиск в бесконечном пространстве организуется за счет того, что из эвристических правил отыскиваются наиболее интересные. (Ленат выдвинул интересную гипотезу: может быть можно провести аналогию между тем, как программа AM делает осмысленные шаги, абстрагируясь от цели, и скрытой в генах информацией, которая руководит направлениями эволюции животного мира?)

Программа AM имеет одно ограничение: ее эври­стические правила фиксированы. Чем дольше рабо­тает программа, тем меньше эффективность начальных эвристических правил, особенно для новых ситуа­ций. Преодолеть это ограничение может программа

EURISKO, она обладает механизмом генерации но­вых эвристических правил под руководством эври­стических метаправил.