AI-2009 Day 11 (Лекции 2009 года), страница 3

Полное пространство состояний задачи о пирамидке представлено включает 27 вершин.

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

1. переместить диски 1 и 2 с колышка А на колышек В ( 1, 2 : А В);

2. переместить диск 3 с колышка А на колышек С ( 3 : А С);

3. переместить диски 1 и 2 с колышка В на колышек С ( 1, 2 : В С).

На рис. 7(б) показано исходное состояние для третьей задачи.

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

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

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

Аналогично представлению в пространстве состояний, формализация задачи в рамках подхода, основанного на редукции задач, включает определение следующих составляющих:

• формы описания задач/подзадач и описание исходной задачи;

• множества операторов и их воздействий на описания задач;

• множества элементарных задач.

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

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

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

И/ИЛИ графы. Решающий граф

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

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

Если некоторая вершина такого графа имеет непосредственно следующие за ней (дочерние) вершины, то либо все они являются И-вершинами, либо все они – ИЛИ-вершины. Заметим, что если у некоторой вершины И/ИЛИ-графа имеется ровно одна дочерняя вершина, то ее можно считать как И-вершиной, так и ИЛИ-вершиной как, например, вершину F на рис.9(б) .

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

Вершину И/ИЛИ-графа, соответствующую описанию исходной задачи, будем называть начальной вершиной. Вершины же, которые соответствуют описаниям элементарных задач, будем называть заключительными вершинами. В графе, показанном на рис.10, начальной является вершина P₀, а заключительными – вершины P₁, P₄, P₅, P₇ и P₈ (они изображены жирными кружками).

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

Сформулируем общее рекурсивное определение разрешимости вершины в И/ИЛИ-графе:

• заключительные вершины разрешимы, так как они соответствуют элементарным задачам;

• вершина, не являющаяся заключительной и имеющая дочерние И-вершины, разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин;

• вершина, не являющаяся заключительной и имеющая дочерние ИЛИ-вершины, разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин.

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

Для И/ИЛИ-графа, изображенного на рис.10, разрешимыми являются (кроме заключительных) вершины M₁, M₂, P₂, P₃. Этот граф содержит два решающих графа: первый состоит из вершин P₀, M₁, P₁, P₂ и P₅ ; а второй – из вершин P₀, M₂, P₃, P₄ и P₅. Заметим, что вершины M₃ и P₆ не являются разрешимыми (M₃ неразрешима в силу неразрешимости вершины P₆).

Пример: задача символьного интегрирования

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

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

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

Элементарные задачи интегрирования соответствуют табличным интегралам, к примеру, sin(x)dx = - cos(x) + C. Отметим, что поскольку каждая из таких табличных формул содержит переменные, на самом деле она является схемой, задающей бесконечное множество элементарных задач.

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

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

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

1. применения подстановки z=tg(x);

2. эквивалентного преобразования подынтегрального выражения;

3. применения правила интегрирования суммы функций.

При этом одна из трех результирующих подзадач оказывается элементарной, а две остальные решаются за один шаг (первая – путем вынесения постоянного множителя за знак интеграла, вторая – применением подстановки z=tg(w) ).

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

7