Intel_Nils (526801), страница 23
Текст из файла (страница 23)
Пусть 6у представляет собой множество состояний, к которым применим ). Тогда мы имеем подзадачу, описываемую тройкой (5, Р, 6т). Как только такая подзадача решена и названо состояние' Атее 6п мы можем сформулировать элементарную задачу ((к), р,()(к))), где ((к) — состояние, достнгающееся после применения оператора ( к состоянию я.
Эта задача элементарная, так как она решается просто 1!7 4,10. Различия путем применения ключевого оператора 1. У нас остается теперь задача, описываемая тройкой ((((й)), р, 6). Таким образом, когда может быть найден ключевой оператор 1 в пространстве состояний, можно воспользоваться следующим способом редукции задачи: (Мы упростили эту схему, не указав на ней элементарной подзадачи ((я), р, щй))).) Этн две результирующие задачи могут быть в дальнейшем решены либо путем непосредственного перебора в пространстве состояний, либо путем дальнейшего их сведения.
Если наша стратегия состоит в том, чтобы прибегнуть к дальнейшему сведению задач к подзадачам, то нам нужно определить некоторый ключевой оператор для задачи (5, Р, 61) и т. д. В большинстве задач нам не удается всегда выделить единственный ключевой оператор, про который заведомо известно, что применение его совершенно необходимо при решении задачи. Вместо этого нам удается лишь указать некоторое подмножество операторов, таких, что один из них с достаточно высокой степенью правдоподобия является таким существенным оператором. Каждый оператор из этого подмножества образует пару результирующих подзадач.
Процесс перебора, опирающийся на эту идею, приводил бы к построению графа «И1ИЛИ» при поиске решения среди различных альтернатив, Прежде чем у нас возникнет возможность применить этот метод, следует для любой задачи поиска в пространстве состояний указать некоторый способ построения множества операторов, которые могут быть кандидатами в ключевые. В следующем разделе мы опишем один конкретный метод, основанный на различиях (б1Негепсез). 4.10.
РАЗЛ ИЧИЯ Один из способов нахождения операторов, которые предположительно могут быть ключевыми, состоит в вычислении различия для данной задачи (5, Р, 6). Попросту говоря, различие для тройки (5, г, 6) это есть частичный список причин, по которым элементы множества 5 не удовлетворяют тем условиям, которым должны удовлетворять целевые состояния (множество 6). (Если некоторый элемент множества 5 находится в 6, то 1!8 Гл. 4, Горедсгавленил, допускающие сведение задач к подзадачам наша задача решена и никакого различия нет.) Например, если множество целевых состояний 6 определяется некоторой груп- пой условий, налагаемых на состояния, и если некоторый эле- мент з я 5 удовлетворяет части, но не всем этим условиям, то различием может служить частичный перечень тех условий, ко- торым элемент з ие удовлетворяет.
Если эти условия могут быть расположены в порядке их важности, то в качестве различия можно было бы выбрать просто самое важное из них. Далее, каждому возможному различию мы ставим в соответ- ствие некоторый оператор (или множество операторов) в про- странстве состояний.
Это и есть операторы, которые могут быть ключевыми. Некоторый оператор ставится в соответствие раз- личию только в том случае, когда его применение может устра- нить это различие. Проиллюстрируем работу этого процесса применительно к задаче об обезьяне и бананах. Эта задача обсуждалась нами в гл. 2 в связи с использова- нием схем описаний состояний. Напомним, что этн схемы имели форму (яс, х, у, з), где чу — положение обезьяны в горизонталь- . ной плоскости (двумерный вектор); х равен 1 или 0 в зависи- мости от того, находится обезьяна на ящике или нет соответ- ственно; у — положение ящика в горизонтальной плоскости (двумерный вектор); г равен ! или 0 в зависимости от того, по- лучает обезьяна бананы или нет соответственно, Имеются четыре оператора, действия и условия применимо- сти которых даются следующими правилами переписывания: о,о,о.о.а — -""""' и,о.„,ч, о,о .о, .в — """-"""' и,о,, в, и( .о..п ' "'"' о, о..п.
)'о(с, 1, с, 0) +(с, 1, е, !), где с — точка пола, расположенная прямо под бананами. Условие выполнения поставленной цели выполняется для описаний состояний лишь в том случае, когда последний элемент в этой схеме описания состояния равен !. Начальное состояние дается списком (а, О, Ь, 0). Если Р = (Го„)з,1з,1о) — множество из четырех операторов, а 6 — множество целевых состояний, то наша исходная задача принимает вид (((а, О, Ь, 0)), Р, 6). Так как в этой задаче множество операторов остается неизменным, то символ Р можно опустить и обозначить всю задачу про; сто как (((а, О, Ь,-О)), 6). 4.!д Разлычая ыв Теперь процедура сведения задачи к совокупности подзадач с использованием понятия ключевых операторов может быть описана следующим образом: Прежде всего вычисляем различие для исходной задачи.
Для списка (а, О, Ь, О) мы получаем, что он не удовлетворяет поставленной цели, так как последний элемент в нем не равен 1. Ключевой оператор (ответственный за уменьшение этого различия — это оператор 1««схватить». (Мы предполагаем, что связи между возможными различиями и их ключевыми операторами заданы решателю задач с самого начала.) Используя оператор 1« для сведения вервоначальной задачи, мы приходим к следующек паре подзадач: (((а, О, Ь, О)), Оь) и (Д„(з,)), б), где ОЬ вЂ” множество описаний состояний, к которым применим оператор 1« (описання состояний из области определения оператора )«), а з~ †.
состояние в бй, получаемое в результате решения подзадачи. Так как прежде всего мы должны решить первую задачу из указанной пары, то применим к ней ту же самую процедуру. Сначала вычислим различие. Состояние, описываемое четверкой (а, О, Ь, О), не входит в бь по той причине, что Ящик не находится в точке с. Обезьяна не находится в точке с. Обезьяна не на ящике. Если теперь этот список утверждений взять в качестве разли- чия, то мы выделяем следующие ключевые операторы: (, — передвинуть (с), ), — подойти (с), ~з — взобраться. Далее мы по очереди применяем каждый нз этих ключевых операторов, с тем чтобы построить альтернативные пары ре- зультирующих задач. Первый из ключевых операторов исполь- зуется для сведения задачи ((а, О, Ь, О), бь) к такой паре за- дач: (1.1) (((а, О, Ь, О)), бь), (-1.2) Щ,(зп)).
О,,), где зп ~ бь получается в результате решения задачи 1.1. Так как сначала необходимо решить задачу !.1, то мы вы- числяем.ее различие. Обезьяны нет в точке Ь. ТЛЕ Пространства состояний вмсигего уровня Это различие дает нам ключевой оператор ), — подойти (Ь). Затем этот ключевой оператор используется для разбиения задачи (((а, О, Ь, 0) ), 61,) на две: (1.!1) ((а,О, Ь, 0), 61,), (1.12) ((), (зш)), 61,). Первая из этих задач элементарная; для нее различие равно.
нулю, поскольку (а, О, Ь, 0) находится в области определения оператора 1» Следовательно, можно начать работать с задачей 1.12. Продолжим наше описание процесса еще на один шаг впеРед. Мы видим тепеРь, что Те(змт) есть (Ь, О, Ь, 0), так что задача 1.12 превращается в задачу ((Ь, О, Ь, 0), 6ь). Эта задача также элементарная, поскольку (Ь, О, Ь, 0) находится в области определения оператора /ь Такой процесс завершения решений задач, построенных ранее, продолжается до тех пор, пока не будет решена исходная задача. На рис.
4.14 изображен граф типа «И/ИЛИ», дающий дерево решения для этой задачи. Числа около вершин графа показывают порядок, в котором исследовались различные задачи в ходе описанного процесса перебора. Оказалось, что рассмотренный нами порядок привел к решению еще до того, как были подвергнуты изучению незанумерованные задачи, но в общем случае мог потребоваться дополнительный перебор. Анализируя граф решения на рис. 4.14, нетрудно построить последовательность операторов, решающую исходную задачу: (подойти (Ь), передвинуть (с), взобраться, схватить). В методе, использующем ключевые операторы, задача расщепляется на части с последующим уменьшением объема необходимых поисковых усилий.
(Пространство перебора в задаче об обезьяне и бананах настолько мало, однако, что в этом случае использование ключевых операторов не дало заметного увеличения эффективности.) Для того же, чтобы воспользоваться ключевыми операторами, решателю задач должна быть сообщена процедура вычисления различий и процедура, позволяющая связывать с ними ключевые операторы, Возможность установления хороших связей между различиями и операторами сильно зависит от конкретной задачи. 4.11.
ПРОСТРАНСТВА СОСТОЯНИИ ВЫСШЕГО УРОВНЯ Процесс сведения задачи к подзадачам, основанный на использовании ключевого оператора 1 и примененный к задаче (8, го, 6), приводит к двум «И» подзадачам (5, г', 61) и !22 Гл. 4. Представления, допускающие сведение задач к подзадачам ((Г(й)),г,6), где бг — множество состояний, к которым применим оператор Г, а д — элемент множества бг. Часто оказывается необходимым решать первую из результирующих задач (5,г", бг) еще до того, как вторая может быть сформулирована и решена.
Тогда весь этот процесс решения задачи путем ее редукции удобнее представить в пространстве состояний высисгго уровня. В пространстве состояний высшего уровня описанием состояния служит упорядоченный список описаний задач. (Отдельные задачи в этом списке должны быть решены в том порядке, в котором они там помещены.) Оператор построения дочерних вершин в пространстве состояний высшего уровня использует различия и ключевые операторы для создания двух подзадач, заменяющих первую задачу из этого списка,(Это делается до тех пор, пока первая из задач списка не окажется элементарной; в последнем случае она просто убирается из списка. Обычно удаление элементарной задачи из списка соответствует применению ключевого оператора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
