Intel_Nils (526801), страница 19
Текст из файла (страница 19)
В задаче о пирамидке описание подзадач может быть сделано в виде списка, содержащего два списка. Так, описание задачи [(113), (333)] означает: «Преобразовать расположение (113) в расположение (333)». Часто удобно описывать задачу на языке элементов представления в пространстве состояний.
Мы видели, что любая задача поиска в пространстве сос1ояний может быть представлена как совокупность трех составляющих: 1. Множество о начальных состояний. 2. Множество Р операторов, отображающих описания состояний в описания состояний. 3. Множество б целевых состояний.
Тогда тройка (о, Р, О) определяет задачу, и она может быть использована как описание задачи. В задаче о пирамидке мы использовали именно это обозначение, хотя, поскольку множество Р операторов в пространстве состояний предполагалось одним и тем же для всех задач, в описаниях задачи оно в явном виде не присутствовало. 96 Гл, 4. Представления, допускающие сведение задач к подзадачам После того как задачи и подзадачи описаны в виде троек (о, р, 6), естественно рассматривать этн подзадачи как задачи нахождения пути между определенными состояниями-вехами в пространстве состояний. Например, в задаче о пирамидке подзадачи ((111) Ф (122)), ((122) Ф (322)) и ((322) Ф (333)1 определяют такие состояния-вехи (122) и (322), которые обладают тем свойством, что через них пройдет и окончательный решающий путь.
То обстоятельство, что в подходе, связанном с сведением задачи к подзадачам, используются понятия состояний, операторов и целей при описании подзадач, само по себе еще не озна-' чает, что этот подход и подход с использованием пространства состояний по существу совпадают. На самом деле, как мы уже отмечали, последовательный перебор в пространстве состояний — это тривиальный случай сведения задачи к подзадачам; по этой причине подход, связанный со сведением задачи к совокупности подзадач, можно рассматривать как более общий метод решения, чем последовательный' перебор в пространстве состояний. Можно было бы также рассматривать подход, основанный иа сведении задачи к подзадачам, просто как способ перечисления отдельных этапов поиска подпутей между предполагаемыми состояниями-вехами в пространстве состояний и управления процессом компоновки подпутей в полные решения.
4.3. ОПЕРАТОРЫ СВЕДЕНИЯ ЗАДАЧИ К ПОДЗАДАЧАМ Оператор сведения задачи к подзадачам преобразует описание задачи во множество результирующих, или дочерних, описаний задач. Это преобрааование таково, что решение всех дочерних задач обеспечивает решение исходной родительской задачи.
Когда множество дочерних задач состоит нз одного элемента, мы имеем простейший случай замены одной задачи другой, ей эквивалентной. Для данного описания задачи может существовать много операторов сведения, каждьуй из которых применим. Применение каждого такого оператора порождает альтернативные множества подзадач. Некоторые из этих подзадач могут оказаться неразрешимыми, так что нам придется перепробовать несколько операторов, чтобы построить такое множество, все члены которого разрешимы. Таким образом, снова возникает задача перебора. Один класс задач связан с доказательством ') того, что определенные утверждения истинны.
Пусть Я вЂ” утверждение, истин- 1) В этой главе наше обсуждение лоназательств будет носить совершенно неформальный характер. В последуюшах главах предмет доказательства него роль в решении задач будут рассмотрены более строго. 97 4.4. Онисанин ээементарнэм задач ность которого мы хотим доказать, а Т вЂ” множество посылок, которыя' предполагаются верными. Тогда под 5) Т (чнтается «5 при данном Т») мы будем понимать задачу доказательства утверждения 5, исходя из посылок Т. Общая схема для сведения к подзадачам задач такого вида состоит в том, чтобы ввести в исходную задачу новые посылки, а затем сформулировать дополнительные задачи на доказательство этих новых посылок.
Так, при редукции задачи 5~Т мы добавляем, скажем, Ф посылок и получаем следующее множество результирующих задач: 5~~Т, Хо Х„..., Х„ Х,)Т, Хю ..., Хн Х )Т где Хь Хь ..., Хл — это л добавочных посылок. Часто этот оператор редукции задачи применяется так, чтобы в каждый момент времени добавлялась лишь одна посылка. Тогда 5')Т сводится к множеству 5')Х, Т и Х(Т. Символы посылок Х,, ..., Хн можно было бы рассматривать как переменные, принимающие значения из некоторого множества посылок. Тогда каждое возможное значение этих переменных соответствовало бы применению отдельного оператора сведения задачи. Этим переменным могут быть сразу же приданы определенные значения в виде конкретных посылок (содержащих, возможно, новые переменные), но вместо этого их можно оставить в виде переменных, имея в виду, что конкретные значения могут быть им приданы в процессе дальнейшего сведения. Позже мы рассмотрим некоторые из предлагаемых подходов к выбору конкретных значений для посылок.
Часто нам будет нужно в качестве частных значений выбрать более чем одно множество посылок, так что наше доказательство может вернуться назад н, пойти по другим альтернативным направлениям. чя. ОПИСАНИЯ ЭЛЕМЕНТАРНЫХ ЗАДАЧ Конечная цель всякого рода сведений задачи к подзадачам состоит в получении таких элементарных задач, решения которых очевидны. Этими задачами могут быть как задачи, решающиеся за один шаг перебора в пространстве состояний, так и другие более сложные задачи, имеющие известные нам решения.
Кроме того, что эти элементарные задачи играют очевидную роль в остановке процесса перебора, иногда они испольауются для ограничения процесса построения альтернативных множеств результирующих .задач в течение процесса сведения 4 зач. 493 ЯВ Гл. 4. Представлении, допускающие сведение задач к подзадачам задачи. Это ограничение возникает вследствие того, что одна или более из этих результирующих задач оказываются принадлежащими определенному подклассу элементарных задач.
4ен «И/ИЛИ» ГРАФЫ Для изображения расчленения задачи на альтернативные множества результирующих задач удобно воспользоваться гра-. фоподобной структурой. Так, предположим, что задача А может быть решена либо путем решения задач В и С, либо путем решения задач Р и Е, либо путем решения задачи Р. Это соотношение изображается структурой иа рнс. 4.4. В вершинах структуры указаны те задачи, которые они представляют. Рис. 4.5.
«И(ИЛИ» граф. Р н с. 4.4. Структура, показывнюшзи различные множе- ства подзадач длн А Задачи В и С составляют одно множество результирующих задач, задачи Р и Š— другое, а задача Р— третье. Вершины, соответствующие одному множеству, помечены специальным значком, связывающим подходящие к ним дуги. В структуру обычно вводятся некоторые дополнительные вершины, так чтобы каждое множество, содержащее более одной результирующей задачи, группировалось под своей собственной родительской вершиной. Прн этом структура на рис. 4.4 преобразуется в структуру, изображенную на рис.
4.5. На этом рисунке добавленные вершины У и М служат отдельнымироднтельскими вершинами для множеств (В, С) и (Р„Е) соответственно. Если считать, что вершины У и М играют роль описаний задач, то мы видим, что задача А сведена к одиночным альтернативным подзадачам Ф, М или Р.
По этой причине вершины,'помеченные Ф, М и Р, называются «ИЛИ» вершинами. 4Х «И/ИЛИ» графы Задача Ф сводится к одному множеству подзадач В н С, причем обе они должны быть решены, чтрбы была решена задача У. По этой причине вершины, помеченные В и С, называются «И» вершинами. Вершины типа «И» выделяются отметкой, сделанной на идущих к ннм дугах. Структуры, подобные той, что изображена на рис. 4.5, называются «И/ИЛИ» графами.
Если некоторая вершина «И/ИЛИ» графа имеет непосредственно следующие за ней вершины, то либо все они являются «ИЛИ» вершинами, либо все они — «И» вершины. (Если у некоторой вершины имеется ровно одна непосредственно следующая за ней вершина, то ее можно считать как «И» вершиной, так и «ИЛИ» вершиной.) Заметим, что в частном случае, когда вершин типа «И» вообще нет, мы получаем обычный граф того типа, который появлялся при переборе в пространстве состояний. Но из-за наличия вершин типа «И» в «И/ИЛИ» графах эти структуры существенно отличаются от обычных графовых структур.
Для них тре. буются свои собственные специализированные приемы поиска, что и служит главной причиной, по которой мы делаем различие между двумя подходами к решению задач. При описании «И/ИЛИ» графов мы будем продолжать пользоваться такими терминами, как родительские вершины, вершины, непосредственно следующие за данной (дочерние), дуга, соединяющая две вершины, и т. д., придавая им очевидный смысл. На языке «И/ИЛИ» графов применение одиночного оператора сведения задачи к подзадачам к некоторому описанию задачи обычно будет означать, что по очереди сначала будет построена промежуточная «ИЛИ» вершина, а затем непосредственно следующие за ней «И» вершины. (Исключение составляет случай, когда множество подзадач состоит из одного элемента.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
