PDF-лекции, страница 21

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

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

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

Впрочем, этоусловие взаимной независимости результирующих задач можно несколько ослабить. Метод редукцииприменим также, если решения получающих подзадач зависят друг от друга, но при этом существуеттакой порядок их редукции, при котором найденные решения одних, более ранних подзадач неразрушаются при решении других, более поздних – как в головоломке о ханойской башне, в которойважен лишь порядок решения выделяемых подзадач.66Рис.11tg4xdxz=tgxz4 2 dz1+z1(-1+z2+ 1+z2 )dz-dzz2dz 1dz+z2z=tgwdzdwДень 12. Различия и ключевые операторыВ заключение целесообразно обсудить ряд общих идей, на которых может быть основанаредукция задач. К их числу прежде всего относится идея выделения так называемых ключевыхоператоров и различий состояний.

Будем далее предполагать, что задачи и подзадачи описываются впространстве состояний как тройки вида ( SI , O, SG ), где SI и SG – соответственно начальное и целевоесостояния, или же как двойки (SI , SG ), если предполагать неизменным при поиске множество Oоператоров преобразования состояний.Часто при поиске в пространстве состояний нетрудно обнаружить один оператор, которыйобязательно должен входить в решение задачи (по сути, применение этого оператора есть необходимыйшаг решения этой задачи). Такой оператор и называется ключевым оператором в пространствесостояний. К примеру, в задаче о пирамидке ключевым оператором был оператор переноса на нужныйколышек самого большого диска 3.Ключевой оператор может быть использован для следующего способа сведения исходной задачик подзадачам.

ПустьOp – найденный в пространстве состояний задачи ключевой оператор (OpO) ;SOp – множество состояний, к которым применим ключевой оператор Op;Op(s) – состояние, полученное в результате применения ключевого оператора Op к состоянию s (s SOp).Тогда исходную задачу можно свести к трем подзадачам:первая задача (SI , SOp) состоит в поиске пути от начального состояния исходной задачи к одномуиз состояний, к которому применим ключевой оператор Op; вторая задача является элементарной, она заключается в применении этого ключевого оператора; третья задача (Op(s) , SG) состоит в поиске пути от состояния, полученного применениемключевого оператора, к целевому состоянию исходной задачи.Порядок решения перечисленных задач существен (третья задача не может быть решена раньшепервой и второй, также как вторая – раньше первой).

Для решения первой и третьей задач может бытьприменен опять метод редукции с помощью ключевого оператора, или же их решение может бытьнайдено непосредственным поиском в пространстве состояний.Для большинства задач не удается всегда однозначно выделить ключевой оператор, гораздочаще удается найти множество операторов-кандидатов в ключевые (т.е. операторов, с большой67вероятностью могущих стать ключевыми). Таким образом, в общем случае необходим процесс перебораоператоров-кандидатов, каждый из которых образует свое множество результирующих задач (этотперебор и означает поиск на И/ИЛИ-графе задачи).Самый важный вопрос при таком способе редукции задач состоит в том, как найти кандидаты включевые операторы. Один из способов, предложенных и опробованных впервые в одной из наиболееизвестных систем искусственного интеллекта “General Problem Solver” - GPS (А.Ньюэлл, Г.Саймон,Дж.Шоу – 1957 г.), заключается в выявлении различий для начального и целевого состояний задачи.Различие легче всего формализовать как несоответствие различных элементов описанийначального и целевого состояний.К примеру, в задаче об обезьяне и банане различием можно считать неравенствосоответствующих элементов списков, описывающих два состояния.

Тогда при сравнении состояний(ТО,П,ТЯ,0) и (ТЯ,П, ТО,1) выявляются три различия – соответственно в первых, третьих и четвертыхэлементах списков.С каждым различием в системе GPS был связан один или несколько операторов, призванныхустранять или уменьшать это различие. Эти операторы и являлись по сути кандидатами в ключевые. Накаждом этапе работы система определяла различие между текущим состоянием (объектом) задачи ицелевым состоянием (объектом), а затем выбирала и пыталась применить оператор для уменьшениянайденного различия. В общем случае операторы включали в себя предусловия (условия применимости),выполнение которых было необходимо для их применения, в этом случае GPS сводила исходную задачук задаче достижения нужного условия.В задаче об обезьяне и банане естественно связать различия и операторы-кандидаты в ключевыеследующим образом: Различие в первом элементе списка-описания состояния (положение обезьяны в плоскостипола) – операторы Перейти и Передвинуть. Различие во втором элементе (положение обезьяны по вертикали) – оператор Взобраться. Различие в третьем элементе (положение ящика) – оператор Передвинуть. Различие в четвертом элементе (содержимое руки обезьяны) – оператор Схватить.Ясно, что для реализации рассмотренных идей в виде алгоритма или программы должна быть, вопервых, специальная процедура сравнения описаний состояний и вычисления различий.

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

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

Ключевая идеяэтой эвристики такова: поиск различий между тем, что дано в поставленной задаче, и тем, что надо получить; последовательное устранение найденных различий с помощью подходящих средств–операций.68Работая в соответствии с этой эвристикой, 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.