Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.
ISBN 5-03-001815-8
Скачать (прямая ссылка):
В, 0), отсутствует в G/4 потому, что: 1) ящик не находится в положении С; 2) обезьяна не находится в положении С; 3) обезьяна не сидит на ящике. Операторы, обеспечивающие уменьшение этих различий,— это соответственно f2=PUSH-ВОХ(С), fi = GOTO (С) и /з=СЫМВВОХ. Применение оператора /2 приводит к подзадачам ({(Л, 0, В, 0)}, G/J и ({/г^п)}. Gf2), где отношение sueG/2 получено в рзультате решения первой подзадачи.
Поскольку сначала надо решить ({(Д 0, В, 0)}, Gf2), мы определяем невязку, которая состоит в том, что обезьяна не находится в положении В; для уменьшения этой невязки используется оператор ft = GOTO (В). Применение этого оператора приводит к двум подзадачам ({(Л, 0, В, 0)}, Gft) и ({Msni)}, Gf2). Первая из этих задач теперь является элементарной; ее невязка равна нулю, так как (Л, 0, В, 0) находится в области действия оператора f 1, а этот оператор применим к решению данной задачи. Отметим, что /i(sin) = (?, 0, В, 0), поэтому вторая задача приводится к виду ({(В, 0, В, 0)}, Gf2). Эта задача — тоже элементарная, поскольку (В, 0, В, 0) находится в области действия оператора f%, а /2 применим к решению этой задачи. Процесс последовательного завершения решения ранее порожденных задач продолжается до тех пор, пока не будет решена исходная задача.
В конъюнктивно-дизъюнктивном графе один из узлов, называемый начальным, отвечает описанию исходной задачи, а те узлы, которые соответствуют описаниям элементарных задач называются терминальными. Цель поиска на И/ИЛИ-графе заключается в показе того, что разрешена задача, соответствующая начальному узлу. Определение такого разрешенного узла можно дать рекурсивно следующим образом.
1. Терминальные узлы являются разрешенными, так как они соответствуют элементарным задачам.
2. Если нетерминальный узел имеет дизъюнктивных преемников, то он является разрешенным тогда и только тогда, когда разрешен по крайней мере один из его преемников.
3. Если нетерминальный узел имеет конъюнктивных преемников, то он является разрешенным тогда и только тогда, когда решены все его преемники.
Граф решения — это подграф, состоящий из разрешенных
104 Глава 2
•узлов и демонстрирующий, что разрешен начальный узел. Цель •использования системы продукций или процесса поиска заключается в том, чтобы найти граф решения, связывающий начальный узел с N терминальными узлами. Грубо говоря, такой подграф решения И/ИЛИ-графа аналогичен маршруту в обычном графе. Он может быть получен, если начать движение от узла п и каждый раз выбирать в точности по одной исходящей дуге. 'Из каждого узла-преемника, к которому направлена дуга, выбирается одна исходящая дуга. Таким образом, каждый преемник будет элементом N.
Для отыскания решений на конъюнктивно-дизъюнктивном графе необходим алгоритм, подобный алгоритму А*, но способный надлежащим образом манипулировать конъюнктивными дугами. Таким свойством обладает алгоритм эвристического поиска АО*.
Алгоритм АО*
Шаг 1. Пусть множество G состоит только из узла INIT, отображающего исходное состояние. Для него вычисляется /i(INIT). Шаг 2. До тех пор пока узел INIT не будет снабжен меткой SOLVED (РАЗРЕШЕН) или до тех пор, пока значение h узла INIT не станет больше, чем FUTILITY (НЕУДАЧА), выполняется следующая процедура.
1. Проводятся помеченные дуги из узла INIT и выбирается для расширения один из еще не расширенных узлов, который встречается на этом пути. Выбранному узлу присваивается имя NODE.
2. Сформировываются преемники узла NODE. Если нет ни одного преемника, величине h узла NODE присваивается значение FUTILITY. Это эквивалентно утверждению, что узел NODE неразрешим. Если преемники есть, то для каждого такого узла (называемого SUCCESSOR), не являющегося предком узла NODE, выполняется следующее:
а) добавляется SUCCESSOR к графу G;
б) если SUCCESSOR является терминальным узлом, то ему присваивается метка SOLVED и значение h, равное 0;
в) если SUCCESSOR не является терминальным узлом, вычисляется его значение h.
3. Распространяется полученная информация вверх по графу следующим образом: 5 обозначается множество узлов с меткой SOLVED или со значениями h, которые изменились и потому подлежат пересылке назад, к их родительским узлам. Инициализируется множество 5 так, чтобы оно состояло из одного узла NODE. До тех пор пока 5 не окажется пустым, повторяется следующая процедура:
а) выбирается из 5 узел, ни один из потомков которого в G
Искусственный интеллект
105
не встречается в 5. (Другими словами, необходимо убедиться, что обработка любого узла осуществляется ранее обработки его узлов-предков.) Присваивается обработанному узлу имя CURRENT (текущий), и он исключается из 5;
б) вычисляется стоимость каждой дуги, исходящей из CURRENT. Эта стоимость равна сумме значений h каждого из узлов в конце дуги плюс стоимость, приписанная самой дуге. Присваивается новое значение h узлу CURRENT, равное минимальной из стоимостей, только что вычисленных для исходящих из него дуг;
в) помечается наилучший исходящий из узла CURRENT путь, снабжая меткой дугу минимальной стоимости в соответствии с результатами, полученными на предыдущем шаге;
