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

В первой и третьей задачах можноРис.81, 2, 3: AC1, 2: AB3: AC1, 2: BC1: AC2: AB1: CB1: BA2: BC1: ACвновь применить метод редукции задач, и свести их к элементарным задачам. Весь процесс редукцииможно схематически представить в виде дерева (рис. 8). Вершины дерева соответствуют решаемымзадачам/подзадачам, причем листья дерева – элементарным задачам перемещения дисков, а дугисвязывают редуцируемую задачу с ее подзадачами.Заметим, что рассмотренная стратегия сведения задачи к совокупности подзадач может быть применена и в случае, когда начальнаяконфигурация задачи о пирамидке содержит не три, а большее число дисков. В любом случае, существенным является порядок, в которомрешаются результирующие задачи: например, вторая задача не может быть решена ранее первой. Таким образом, в случае подхода,основанного на редукции задач, мы получаем также пространство, но состоящее не из состояний, а из задач/подзадач (точнее, ихописаний). При этом роль, аналогичную операторам в пространстве состояний, играют операторы, сводящие задачи в подзадачи.

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

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

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

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

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

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

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

Разрешимость этой вершины зависит от разрешимости других вершин графа.Сформулируем общее рекурсивное определение разрешимости вершины в И/ИЛИ-графе: заключительные вершины разрешимы, так как они соответствуют элементарным задачам; вершина, не являющаяся заключительной и имеющая дочерние И-вершины, разрешима тогда итолько тогда, когда разрешима по крайней мере одна из ее дочерних вершин; вершина, не являющаяся заключительной и имеющая дочерние ИЛИ-вершины, разрешима тогда итолько тогда, когда разрешима каждая из ее дочерних вершин.Если в процессе поиска удалось показать, что начальная вершина разрешима, то это значит, чтообнаружено решение исходной задачи, которое заключено в так называемом решающем графе.Решающий граф – это подграф И/ИЛИ-графа, состоящий только из разрешимых вершин идоказывающий разрешимость начальной вершины.Рис.10P0M1P1M2P2P3P5P4M332P6 P7P8Для И/ИЛИ-графа, изображенного на рис.10, разрешимыми являются (кроме заключительных)вершины M1, M2, P2, P3.

Этот граф содержит два решающих графа: первый состоит из вершин P0, M1, P1,P2 и P5 ; а второй – из вершин P0, M2, P3, P4 и P5. Заметим, что вершины M3 и P6 не являютсяразрешимыми (M3 неразрешима в силу неразрешимости вершины P6).Пример: задача символьного интегрированияВ качестве примера применения метода редукции рассмотрим решение задачи символьногоинтегрирования, т.е. нахождения неопределенного интеграла F(x)dx. Обычно эта задача решаетсяпутем последовательного преобразования интеграла к выражению, содержащему известные табличныеинтегралы. Для этого используется несколько правил интегрирования, в том числе: правилоинтегрирования суммы функций, правило интегрирования по частям, правило вынесения постоянногомножителя за знак интегрирования, а также применение алгебраических и тригонометрическихподстановок и использование различных алгебраических и тригонометрических тождеств.Для формализации этой задачи в рамках подхода, основанного на редукции задач, необходимоопределить форму описания задач/подзадач, операторы редукции и элементарные задачи.

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