Intel_Nils (526801), страница 20
Текст из файла (страница 20)
В этом случае образуется ровно одна вершина, а именно «ИЛИ» вершина.) Таким образом, подходящей структурой„моделирующей метод расчленения задачи на подзадачи, является граф типа «И/ИЛИ». Одна из вершин этого графа, называемая начальной вершиной, соответствует описанию исходной задачи. Те вершины графа„которые соответствуют описаниям элементарных задач„называются заключительными вершинами.
Цель процесса поиска, осуществляемого иа «И/ИЛИ» графе, — показать, что начальная вершина разрешима. Общее определение разрешимости вершины в «И/ИЛИ» графе можно сформулировать рекурсивно следующим образом: Заключительные вершины разрешимы (так как они соответствуют элементарным задачам). Если у вершины, не являющейся заключительной, непосредственно следующие за ней вершины оказались вершинами 100 Гя.
4, Представления, допускающие сведение эадач к подэадачам «ИЛИ», то она разрешима тогда и только тогда, когда разрешима по крайней мере одна из этих вершин. Если у вершины, не являющейся заключительной, непосредственно следующие за ней вершины оказались вершинами «И», то она разрешима тогда н только тогда, когда разрешима каждая из этих вершин. Тогда решающий граф определяется как подграф из разрешимых вершин, который показывает (в соответствии с приве- 4(енным определением), что начальная вершина разрешима. г ! в Ряс 4.6. Некоторые примеры «И/ИЛИ» графов я решающих графов.
Для графа (б) имеется более одного решения. Иа рис. 4.6 приведены примеры «И/ИЛИ» графов. Заключительные вершины обозначены буквой /, разрешимые вершины изображены черными кружочками, а решающие графы выде. лены жирными линиями. Если у некоторой вершины «И/ИЛИ» графа, не являющейся заключительной вершиной, вовсе нет следующих за ней вершин, то мы говорим, что такая вершина неразрешима. Появление таких неразрешимых вершин может означать, что и другие вершины графа (и даже начальная вершина) могут оказаться не* 4.6.
Представление с помощью недетерминароеаннис программ' !О! разрешимыми. Общее определение неразрешимой вершины дается рсчгурснвно следующим образом: Вершины, не являющиеся заключительными и не имеющие следующих за ними вершин, неразрешимы. Если у вершины, не являющейся заключительной. непосредственно следующие за ией вершины оказались вершинами '«ИЛИ», то она неразрешима тогда и только тогда, когда неразрешима каждая из этих вершин. Если у вершины, не являющейся заключнтельноя,непосредственно следующие за ней вершины оказались вершинами «И», то она неразрешима тогда и только тогда, когда неразрешима по крайней мере одна из этих «И» вершин. На рнс. 4.6 неразрешимые вершины отмечены незачерненными кружочками. Показанные на рис.
4.6 «И/ИЛИ» графы заданы в явной форме. Точно так же, как в случае решения задач в пространстве состояний, редко.случается, чтобы граф, на котором дол. жен осуществляться перебор, задавался в явной форме. Как правило, такой граф определен неявно посредством описания исходной задачи и операторов редукции задачи.
Удобно ввести оператор Г построения непосредственно следующих (дочерних) вершин, который, будучи примененным к описанию задачи, порождает все множества следующих из него описаний задач. (Применение оператора Г означает применение всех применимых операторов сведения задачи к подзадачам.) Так, в случае рис.
4.5 применение оператора Г к алгоритму А образует всю ту структуру «И/ИЛИ» графа, которая изображена на рисунке. Процесс решения задачи тогда состоит в том, чтобы построить достаточную часть этого «И/ИЛИ» графа, из которой было бы видно, что начальная вершина разрешима. Мы отложим до следующей главы рассмотрение эффективных методов поиска.
4В: ПРЕДСТАВЛЕНИЕ «И/ИЛИ» ГРАФОВ С ПОМОЩЬЮ НЕДЕТЕРМИНИРОВАННЫХ ПРОГРАММ ') Мы можем ввести некоторые дополнительные элементы не- детерминированных программ, с тем чтобы эти программы можно было использовать для представления процесса построения «И/ИЛИ» графа. По аналогии с оператором присваивания ВЫБОР (в котором программная переменная принимается равной любому элементу некоторого множества) мы можем определить оператор присваивания ВСЕ. В последнем программная переменная принимается равной всем элементам некоторого ') При первом чтении »тот раздел можио опустить. 102 Гл.
4. Прздстазлеиия, долускающие сведение задач к кодзадачаи множества. (Представьте себе, что вычисление после оператора ВСЕ разветвляется на множество фиктивных параллельных про цессов, в каждом из которых в качестве значения программной переменной берется своя величина.) Р и с. 4.7. Недетерминированная программа„ определяющая <Й/ИЛИ» граф. ИСХОДНОЕ ПОЛОЖЕНИЕ: Программная переменная у (принимающая значения из области описаний задач) полагается равной входной структуре данных х, описывающей задачу.
ВЫБОР: Значение программной переменной У (принимающей значения нз области миожесгв описаний задач) полагается равным некоторому элементу множества Г (у) миоясесгв дочерних вершин для прежнего значения у ВСЕ: Новое значение у принимается равным всем элементам множества у. На рис. 4.7 изображена блок-схема недетерминированной программы, определяющей «И/ИЛИ» граф. Для простоты здесь опущены условия окончания, но они состояли бы в.совершенно очевидных проверках, разрешимы вершины или неразрешимы. В общем случае оператор ВСЕ обозначается на блок-схемах следующим образом: Структура данных х служит входом в эту программу, структура данных у — программной переменной, а функция г представляет собой функцию, отображающую прямое произведение областей изменения х и у в некоторое подмножество области изменения у.
Снова для обозначения этого подмножества мы будем пользоваться символом (г); операция у ч-ВСЕ (г) делает 4.б. Представление с номощью нвдетерминированных нрограим !03 новые значения программной переменной у равными всем членам множества (г). Мы также вводим обозначение Л-ветвления.
Это ветвление на л направлений, в котором используется и предикатов рт(х,у), ..., рн(х,у). Эти предикаты имеют значение Т (истина) или ео (ложь) на той области, которая является прямым произведением областей изменения х и у. (Снова х — входная структура данных, а у — программная переменная.) Значение хотя бы одного нз этих предикатов должно быть Т.
Каждый предикат соответствует некоторой ветви, н выбираются все те ветви, соответствующие предикаты которых имеют значения Т. (Представьте себе опять фиктивные параллельные процессоры, начинающие работать на каждой из выбранных ветвей.) На блок-схемах Л-ветвления изображаются так: И опять, обычные детерминированные ветвления являются частными случаями Л-ветвлений. Точно так же, когда значением функции г(х,у) является один элемент, операторы ВЫБОР, ВСЕ и обычные детерминированные операторы совпадают. При конкретном осуществлении недетерминированной программы делается один определенный выбор'в ~/-ветвлениях и операторах ВЫБОР и производятся все возможные выборы в Л-ветвлениях н операторах ВСЕ.
Множество всех возможных конкретных реализаций определяет некоторое «И/ИЛИ» дерево. В данной реализации содержится много путей (ветвления на Л-ветвлениях и операторах ВСЕ). Ее выполнение завершается, если завершается каждый из ее путей. Если для любого входа существует по крайней мере одна завершающая реализация, то говорят, что эта программа правильно определена. Использование всех этих недетерминированных (и детерминированных) элементов дает возможность применять для описания задач недетерминированные программы.
Как пример рассмотрим задачу. о восьми ферзях. В этой задаче требуется на обычной шахматной доске расставить восемь ферзей так, чтобы ни один нз них не находился под ударом других ферзей. Недетерминированная блок-схема программы для этой задачи показана на рис. 4.8. На этой блок-схеме гт и ст представляют собой 184 Гл. 4. Представления, дозревающие сведение задач к подзадачам координаты 1-го ферзя по горизонтали и по вертикали соответ- ,(г,с11) Рис. 4.8. Недетермииироваииая программа для задачи е восьми ферзях. ственно. Преднкат «побить ((го с~), (гь с1))» имеет значение Т лишь тогда, когда 1-й ферзь с координатами (то се) может по- бить 1-го ферзя с коордмнатамн (гь с1).
4.7. Примеры сведение вадики к совокупности подвидак 105 4Л. ПРИМЕРЫ СВЕДЕНИЯ, ЗАДАЧИ К СОВОКУПНОСТИ ПОДЗАДАЧ Задача Символического интегрирования В задаче символического интегрирования мы хотим иметь автоматический процесс, который будет воспринимать в качестве входной величины любой неопределенный интеграл, скажем ) кейпЗхНх, и выдавать на выходе ответ: ((/9)з(пЗх— — ((/Зх) созЗк.
Мы будем считать, что в нашем распоряжении имеется таблица таких простых интегралов, как ис(и = —. )' з!пие(и= — сози, ) а'с(и=а"!од,е и т. д. Тогда любая задача символического интегрирования может быть представлена как задача преобразования данного интеграла в выражения, содержащие лишь табличные интегралы. Для простоты мы будем описывать задачу интегрирования функции 1(х) по х выражением ~! (х) с(х. Описания элементарных задач даются просто табличными интегралами. Мы видим, что каждая из формул на самом деле является схемой, определяющей бесконечное множество элементарных задач. Члены этого множества получаются путем подстановки выражений вместо переменных, содержащихся в этих' формулах.
Для того чтобы определить, является лн данный интеграл примером некоторой элементарной формулы, нужно применить оператор сведения, который отыскивает те подстановки, после которых интеграл и формула совпадают. Операторы сведения задачи к подзадачам могут быть основаны на правиле интегрирования по частям, на правиле интегрирования суммы функций и других правилах преобразования, таких, как правила, содержащие алгебраические и тригонометрические подстановки. Правило интегрирования по частям имеет вид ) и Ып=и ) ее'Π— ~ О Ни. Это правило мы можем использовать для оправдания следующего сведения задачи к подзадачам: 106 Гл 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
