Робототехника.Фу, Ли, Гонсалес (962794), страница 91
Текст из файла (страница 91)
б24 б) Вычислить д($1)ССЕ88ОК = д(ВЕЗТМОРЕ)+ стоимость прохода от ВЕЗТМОРЕ к $ПССЕЗЬОК. в) Проверить, совпадает ли Я)ССЕЬБОК с какой-либо вершиной нз списка ОРЕМ (т. е. была ли она уже создана, но не обработана). Если дз, назовем эту вершину 01.0. Поскольку данная вершина уже существует в графе, мы можем отбросить 81)ССЕЯЗОК и добавить 010 в список преемников ВЕЬТМОРЕ. Теперь решим, надо ли определять путь от вершины ОЕР к ВЕЗТМОРЕ. Поскольку ОЕР и 31)ССЕВЗОК по сушеству являются одной и той же вершиной, надо сравнить их значение д.
Если путь к ОЕР через его предшественника де. шевле, чем путь к 31)ССЕЗЗОК через ВЕЬТМОРЕ, то ничего не надо делать. Если путь к вершине Я)ССЕЬЬОК дешевле, вновь устанавливаем путь от вершины 000 к ВЕЬТМОРЕ, присваиваем значению д(010) значение, соответствующее более дешевому пути, и вычисляем новое значение 1(01.0).
г) Если вершина ЯПССЕЗЯОК не входит в список ОРЕМ, проверяем, входит ли она в список СЕОЯЕР. Если входит, этой вершине из списка С1.ОЗЕР присваиваем имя 01.0 и заносим ее в список преемников вершины ВЕЬТМОРЕ, Проверяем так же, как на шаге 2в, какой путь лучше — новый или старый, и аналогично определяем путь и значения 1 и д. Если мы только что определили лучший путь к вершине ОЕР, мы должны распространить улучшение на всех преемников этой вершины, Таким образом, вершина ОЕР определяет своих преемников, а эти преемники в свою очередь определяют своих преемников. Так продолжается до тех пор, пока каждая ветвь не закончится вершиной, которая либо находится в списке ОРЕМ, либо не имеет преемников. Чтобы распространить новую стоимость вниз, осуществляем поиск первого типа в глубину на дереве, начинающемся с вершины 010, меняем для каждой вершины значение д (и соответственно значение 1).
Для каждой ветви графа поиск заканчивается, когда вы либо достигли вершины, не имеюшей преемников, либо вершины, для которой уже был найден эквивалентный или же лучший путь. Это условие легко проверить. Поскольку мы идем вниз к вершине, проверяем, имеется ли путь от предшественника вершины к ней.
Если да, продолжаем распространение. Если нет, значение д уже определяет лучшую часть пути. Поэтому на этом шаге распространение может быть прекращено. Но, возможно, что с новым значением д, полученным далее, путь, вдоль которого мы следовали, окажется лучшим, чем путь через текушего предшественника. Поэтому они оба сравниваются между собой. Если путь через текушего предшественника все же лучше, прекрашаем распространение. Если же путь, вдоль которого распространялось улучшение, все же лучше, вновь определяем предшественника и продолжаем распространение.
525 д) Если вершина 5ЦССЕ55ОК не находится ни в ОРЕГ), ни в С) 05ЕП, заносим ее в ОРЕМ и добавляем в список преемников вершины ВЕЗТХООЕ. Вычисляем /(5ЦССЕ55ОК) = = /(5ЦССЕ55ОК) + Л(5УССЕ550й). Легко видеть, что А*-алгоритм представляет собой алгоритм поиска на графе, которыв использует Г(п) в качестве функции оценивания для упорядочивания вершин. Отметим, что, поскольку д(п) и й(п) складываются, важно, чтобы значение й(п) являлось мерой стоимости прохода от вершины и к целевой вершине. Целью процедуры поиска является определение пути в пространстве состояний от начального состояния к целевому.
Имеются два направления, в которых такой поиск может осуществляться: 1) вперед из начального состояния и 2) назад из целевого состояния, В модели производягцей системы имеется набор правил как для вывода набора промежуточных состояний вперед, так и для вывода назад. При выводе вперед левые части, или предусловия, соответствуют текущим состояниям, а правые части (результаты) используются для генерации новых вершин до тех пор, пока не будет достигнуто целевое состояние. При выводе назад правые части соответствуют текущим состояниям, а левые части используются для генерации новых вершин, представляющих собой новые целевые состояния, которые необходимо достичь. Это продолжается до тех пор, пока одно из целевых состояний не будет соответствовать начальному состоянию. Описав процесс поиска как последовательное применение ряда правил, легко создать алгоритмы поиска, ие зависящие от направления поиска, Конечно, имеется возможность комбинации поиска вперед и назад.
В этом случае одновременно отыскивается путь как из целевого состояния в конечное, так и путь из конечного состояния в целевое до тех пор, пока они не пересекутся. Такая стратегия называется стратегией двунаправленного поиска. 10.3. ПРОБЛЕМА СВЕДЕНИЯ ЗАДАЧИ К ПОДЗАДАЧАМ Другой подход к решению задачи основан на проблеме сведения задачи к подзадачам. Основная идея заключается в разбиении задачи на подзадачи, которые в свою очередь разбиваются на подзадачи, и так до тех пор, пока исходная задача не сведется к ряду тривиальных задач, имеющих очевидные решения.
Оператор сведения задачи преобразует описание задачи в описание ряда подзадач. К данному описанию задачи могут применяться многие операторы, Применение каждого 526 оператора также приводит к необходимости решения ряда подзадач. Поскольку не все из них в свою очередь могут быть решены, необходимо применять несколько операторов для решения всех возникаюьцих подзадач.
Это снова требует организации процесса поиска Разбиение задачи на ряд подзадач обы шо представляется в виде графа. Предположим, что задачу Л можно решить, если будут решены три подзадачи В, С и 0 (рис. 10.9). Дуги, ведущие из вершины Л к вершинам В, С и О, назовем И-дугами. Тогда вершины В, С и 0 называются И-вершинами, С дру~ой Рвс. 10ть Граф И!ИЛИ. стороны, если задача В может быть решена в случае решения одной из подзадач Е и Р, то в этом случае будем использовать дугу ИЛИ, Полученный граф называется графом И/ИЛИ (рис.
10.9). Легко видеть, что методы поиска, рассмотренные в равд. 10.2, сводятся к графу И/ИЛИ, с помощью которого мы хотим найти единственный путь из начальной вершины к нелевой. Пример. Граф И1ИЛИ для задачи «Обезьяна и бананы» приведен на рис. 10.10. В данном случае задача представляется тройкой (5, Р, 6), где 5 — набор начальных состояний, г — набор операторов и 6 — набор целевых состояний. Поскольку для данной задачи набор операторов г является постоянным и начальное состояние представляется в виде (Л, О, В, 0), то можно исключить символ г и описать задачу как ((Л,О, В,О), 6).
Один из путей выбора операторов сведения задачи заключается в применении понятия различие. Короче говоря, различие для тройки (5, г", 6) представляет собой список причин, по которым ни один из элементов набора 5 не входит в набор 6. (Если 527 в Ц и н о 9 Ъ ф ж ш в. о а хотя бы один из элементов набора Я входит в О, задача решается и различие отсутствует.) В примере из равд. 10.2.1 Р = ((ь (г !з, !4) = (до!о(0) рцзЬЬох(Р), с!1гпЬЬох, дгазр).
Сначала мы вычисляем различие для начальной задачи. Дело в том, что список (А,О,В,О) не может удовлетворять решению, поскольку в нем последний элемент не равен 1. Оператором, уменьшающим это различие, является оператор ! = дгазр. Используя !4 для разбиения начальной задачи, мы получаем следующую пару подзадач: (((Л, О, В, 0)), 6Ь) и ((!4(з~)) 6), где 6Ь представляет собой набор описаний состояний, к которым прйменим оператор (4, и з1 — состояние, входящее в 6ы, полученное при решении подзадачи (((Л, О, В„ О))), 0Ь). Для решения задачи (((А, О, В, 0)), 0Ь) сначала надо вычислить ее различие.
Состояние, описываемое (((А, О, В, 0)), 6д), не входит в 6ш поскольку: 1) ящик не находится в точке С; 2) обезьяна не находится в точке С; 3) обезьяна не находится на ящике, Операторами для уменьшения этих различий являются ~г —— рцзЬЬох(С), (1 — — во!о(С) и (г — — с1!шЬЬох соответственно, Применяя оператор !г, получаем подзадачи (((Л, О, В, 0)), 6!г) и (!г(зц), 6!г), где зц ~ О!г вытекает из решения первой подзадачи. Поскольку сначала должна быть решена подзадача (((А, О, В, 0)), 6гг), то для нее вычисляется различие.
Различие состоит в том, что обезьяна не находится в точке В и оператор, который устраняет его, есть !1 = яо!о(В). Этот оператор затем используется для сведения задачи к паре подзадач (((А, О, В, 0)), 60) и ф(згп, О!г). Теперь первая из этих за. дач является элементарной. Ее различие равно О, поскольку (Л, О, В, 0) входит в область определения оператора !ь с помощью которого можно решить эту задачу. Отметим, что 11(вгп) = (В,О, В, 0), поэтому возникает вторая задача (((В, О, В, О)), 0Ь). Эта задача также является элементарной, поскольку (В, О, В, 0) входит в область определения оператора (г, с помощью которого можно решить эту задачу, Процесс последовательного решения подзадач должен продолжаться до тех пор, пока исходная задача не будет решена. В графе И/ИЛИ одна из вершин, называемая начальной вершиной состояния, соответствует описанию исходной задачи. Вершины графа, соответствующие описаниям элементарных задач, называются конечными вершинами.
Целью процесса поиска на графе является доказательство того, что задача, соответствующая начальной вершине, имеет решение, т. е. что начальная вершина является решаемой, Рекурсивное определе529 ние решаемой вершины может быть дано следующим образом: !. Конечные вершины являются решаемыми вершинами, поскольку они соответствуют элементарным задачам. 2. Если вершина, не являющаяся конечной, имеет преемников типа ИЛИ, она является решаемой вершиной только тогда, когда по меньшей мере один из ее преемников является решаемым.
3. Если вершина, не являюшаяся конечной, имеет преемников типа И, она является решаемой только тогда, когда все преемники являются регзаемымн, Граф решения, который является подграфом, состоящим нз решаемых вершин, показывает, что начальная вершина является решаемой. Целью производящей системы нли процесса поиска является нахождение графа решения от начальной вершины к конечным вершинам. Граф решения, определяюший путь от вершины ц к набору вершин Ч графа типа И/ИЛИ, в некоторой степени аналогичен пути на обычном графе.
Он может быть получен, если начало пути определить в вершине и и каждый раз выбирать только одну выходящую из нее дугу. Для каждой вершины-преемника, к которой направлена эта дуга, мы продолжаем выбирать только одну выходящую из нее дугу. И так до тех пор, пока в конце концов каждый преемник, созданный таким образом, не войдет в набор Лl, Для определения решений на графе И/ИЛИ нам необходим алгоритм, подобный алгоритму А*, но способный выбирать И-дуги соответствующим образом. Такой алгоритм для реализации эвристического поиска на графе И/ИЛИ называется АО*-алгоритмом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
