На первом шаге построения подцепочки используются знания о соответствии типов выводимых фактов типам целей, явно представленные в базе знаний РГЗ конструкциями следующего вида:
Комментарий: утверждение о равенстве значения слота объекта заданной величине
Содержание цели:[“equal”, Объект, Слот, Величина]
Факт:val(“equal”,Объект, Слот, Величина)
Тип цели:“equal”
Трудность цели:1
Приведенная конструкция представляет знания о том, что при отсутствии в текущем состоянии задачи фактов вида, указанного в поле «факт», следует добавлять в граф планирования цели типа “equal”. Достижение данной цели, то есть, успешное доказательство равенства, повлечет добавление в базу задачи факта равенства значения слота указанной величине.
Полученная подцепочка целей для вывода недостающих фактов последовательно объединяется с цепочкой целей, запись которой предписана действиями стереотипа. При их объединении важен порядок, поскольку только после вывода недостающих фактов действия стереотипа могут быть выполнены.
Алгоритм построения ассоциативного уточнения плана таков:
1) Стереотипы с близкими ситуациями оцениваются согласно критерию «полезности».
2) Для каждого стереотипа, признанного «полезным», строится цепочка целей для вывода недостающих фактов. Остальные стереотипы в построении уточнения не используются.
3) Для каждого «полезного» стереотипа вычисляется трудность построенной цепочки и проверяется условие «доступности».
4) «Доступные» стереотипы проходят проверку комбинированным критерием.
5) Для каждого стереотипа, прошедшего все проверки, строится часть уточнения, т.е. цепочка, полученная на шаге 2, последовательно объединяется с цепочкой целей из действий стереотипа, связанного с рассматриваемой ситуацией.
6) Все полученные на шаге 5 части уточнения параллельно объединяются.
При вставке полученного уточнения в граф планирования из него удаляются цепочки, приводящие к появлению в графе так называемого «порочного круга», если таковые входят в состав уточнения. «Порочным кругом» называется состояние графа, при котором одна и та же подцель два раза встречается на каком-либо из допустимых путей в графе. Недопущение возникновения в графе «порочного круга» осуществляется средствами поддержки работы с графом.
Одним из свойств ассоциативного уточнения является то, что любая из его параллельно объединенных цепочек целей содержит недостигнутые цели (цели для вывода недостающих фактов). Этим свойством ассоциативное уточнение отличается от дедуктивного, в котором могут быть цепочки из элементарных целей, не требующих уточнения и считающихся достигнутыми сразу после занесения в граф планирования. Вставка ассоциативного уточнения в граф не может привести к окончанию решения, поскольку на всяком появившемся новом пути в графе будут лежать недостигнутые цели. Следовательно, ассоциативный метод должен использоваться при решении задач в сочетании с другими методами планирования решений.
Преимущества использования ассоциативного планирования состоят в том, что когда нет распознанных ситуаций, а решение еще не окончено, система может продолжить планирование ассоциативным методом (если будет найден подходящий стереотип с близкой ситуацией), а также в том, что система может вести более широкие рассуждения, нежели те, что предусмотрены набором функциональных стереотипов. Для решения задачи могут быть использованы стереотипы, которые при применении традиционных методов (прямой цепочки рассуждений и обратной цепочки рассуждений) неприменимы.
Заканчивая рассмотрение метода ассоциативного планирования, приведем описание его алгоритма. Метод итеративный, алгоритм представляет собой последовательность шагов повторяющихся до тех пор, пока не будет получен план, или не возникнет тупик в решении. Действия, совершаемые на каждом шаге таковы:
1) Среди неуточненных и недостигнутых целей в графе целей выбирается текущая цель (ТЦ) для уточнения.
2) Формируется активный контекст ТЦ.
3) Определяется набор стереотипов пригодных для уточнения текущей цели, ситуации которых считаются близкими. Стереотипы из набора оцениваются в соответствии с критериями «полезности», «доступности» и комбинированным критерием. С каждым стереотипом, удовлетворяющим всем критериям, связывается цепочка целей для вывода недостающих фактов.
4) Если подходящих стереотипов нет, то ТЦ заносится в «черный список», и осуществляется переход на следующий шаг планирования.
5) По набору стереотипов, отобранных ранее, строится ассоциативное уточнение ТЦ. Уточнение заносится в граф.
6) Осуществляется переход на следующий шаг планирования.
4. Примеры решений геометрических задач
Рассмотрим несколько примеров решения задач. Для поиска решений будет использоваться, так называемая, стратегия объединенного уточнения, при которой совместно применяются ассоциативное планирование и обратная цепочка рассуждений.
Задача №1
Дано: ABCD - трапеция с основаниями AB и CD. Окружность O описана около ABCD. AC - диаметр. AB=20 см, AD=10 см.
Найти: площадь трапеции ABCD.
На первом шаге планирования текущей целью выбирается цель, поставленная в задаче. Объединенное уточнение, построенное для нее, состоит из двух цепочек целей: найти площадь треугольника ABC, найти площадь треугольника ACD и вычислить SABCD как сумму найденных площадей; доказать, что ABCD - прямоугольник и вычислить SABCD как произведение AB*AD.
Вторая альтернатива в уточнении получена на основе близкой ситуации. Вид графа планирования после вставки уточнения изображен на рис. 4. Такое же уточнение могло быть получено и при использовании обратной цепочки рассуждений, но для этого необходимо добавление в базу знаний решателя дополнительного стереотипа. Ассоциативное планирование, основанное на аналогии между ситуациями функциональных стереотипов, позволяет в данном случае обойтись без расширения базы знаний.
На втором шаге текущей выбирается цель «доказать, что ABCD прямоугольник», поскольку она лежит на более дешевом пути. Эта цель уточняется цепочкой из четырех целей: доказать, что угол abc=90°, доказать что угол bcd=90°, доказать что угол adc=90°, доказать что угол bad=90° и записать, что ABCD является прямоугольником по определению.
При дальнейшем планировании происходит уточнение целей на нижнем пути (этот путь является более дешевым). За четыре шага производится доказательство того, что все углы ABCD являются прямыми. По окончании шестого шага планирования на нижнем пути в графе не остается недостигнутых вершин, и решение заканчивается. Объяснение полученного решения имеет вид:
Угол abc - прямой, так как противолежащая ему в треугольнике ABC сторона AC является диаметром описанной вокруг ABC окружности О. Угол bcd=180-abc=90, так как они внутренние односторонние при основаниях AB и CD трапеции ABCD. Угол adc - прямой, так как противолежащая ему в треугольнике АCD сторона AC является диаметром описанной вокруг АCD окружности О. Угол bad=180-adc=90, так как они внутренние односторонние при основаниях CD и AB трапеции ABCD. Четырехугольник ABCD - прямоугольник, так как все углы (abc, bcd, adc, bad) равны 90. Площадь прямоугольника ABCD=AB*AD=20*10=200.
Данный метод решения имеет ряд преимуществ по сравнению с методом прямого вывода. Во-первых, все цели, появляющиеся при планировании имеют непосредственное отношение к поставленной задаче, и не производится вывода лишних фактов. Во-вторых, сравнительно немного времени тратится на счет. Это происходит, поскольку при ассоциативном планировании рассуждений число фактов, анализируемых распознавателем ситуаций, значительно меньше, а на работу распознавателя в РГЗ приходятся основные временные затраты. Преимущества стратегии объединенного уточнения перед методом обратной цепочки рассуждений связаны с использованием ассоциативного планирования, ведь именно благодаря использованию ассоциаций в самом начале решения появляется путь, который в последствии ведет к достижению поставленной цели.
Задача №2
Дано: окружность О описана около треугольников ABC и MNF, отрезки AB и MN равны, угол mfn равен 90, угол fmn равен 45, величина отрезка BC равна 3, величина отрезка AC равна 4.
Найти: площадь треугольника ABC.
На первом шаге решения текущей целью выбирается цель, поставленная в задаче - «найти площадь ABC». Для нее строится уточнение: найти АВ и вычислить площадь по формуле Герона или найти угол acb и вычислить площадь ABC по формуле SABC=Ѕ*AC*BC*sin(acb). После вставки уточнения граф планирования имеет структуру, изображенную на Рис. 6.
Следующей целью для уточнения выбирается цель «найти величину AB». Объединенное уточнение, построенное для нее на втором шаге, состоит из трех альтернатив: найти acb и вычислить АВ по теореме косинусов; или найти MN и записать значение AB, поскольку AB=MN; или найти acb, найти bac и вычислить AB по теореме косинусов. Структура графа планирования изображена на рисунке 7. Фактически на первых двух шагах ассоциативное планирование не вносит в ход решения никакого вклада, так как предлагаемые им пути решения совпадают с теми, которые найдены методом обратной цепочки.
Ситуация меняется на третьем шаге решения. Текущей выбирается цель «найти величину acb», и для нее строится уточнение: найти bac, найти abc и вычислить acb по теореме о сумме углов треугольника; или доказать, что AB является диаметром окружности O и записать, что acb - прямой угол, поскольку опирается на диаметр. При этом вторая альтернатива в уточнении построена на основе стереотипа с близкой ситуацией. Вид графа планирования после вставки уточнения изображен на рисунке 8.
Текущей целью на четвертом шаге решения выбирается цель «найти величину MN», так как она лежит на самом дешевом пути. Для нее строится уточнение: найти величину FN, найти величину FM и вычислить MN по теореме косинусов; или найти FN и вычислить MN по теореме синусов. Поскольку цель «найти величину FN» лежит на двух путях в графе, на пятом шаге она выбирается текущей. Уточнение, построенное для этой цели, имеет вид: найти величину угла fnm и вычислить FN по теореме косинусов. При построении уточнения считается условно достигнутой цель «найти величину FM», входящая в контекст текущей цели.
На шестом шаге решения для уточнения выбирается цель «доказать, что AB является диаметром O», поскольку она лежит на одном из дешевых путей и является более трудной, чем остальные недостигнутые цели. С привлечением ассоциативного планирования строится уточнение цели: доказать, что MN является диаметром и записать, что AB диаметр, так как он является хордой окружности O, равной ее диаметру. На седьмом шаге цель «доказать, что MN является диаметром O» получает тривиальное уточнение: применить доказательство 215 (MN является диаметром, так как MN гипотенуза прямоугольного треугольника, около которого описана окружность O). В графе планирования появляется путь-решение, которому соответствует такое объяснение: Отрезок MN - диаметр окружности O, описанной около прямоугольного треугольника MNF, так как он является гипотенузой MNF. Сторона AB треугольника ABC является диаметром описанной около него окружности O, так как AB=MN - диаметру O. Угол acb - прямой, так как противолежащая ему в треугольнике ABC сторона AB является диаметром описанной около ABC окружности O. Площадь треугольника ABC вычисляется как S = 0.5*BC*AC*sin(acb) = 6.
Решение задачи получено за семь шагов, при этом два шага затрачены на уточнение подцелей, лежащих в стороне от решающего пути. Тем не менее, при применении стратегии объединенного уточнения все факты, добавляемые в базу задачи, связаны с искомой целью, вывод лишних фактов не производится, меньше временные затраты на сопоставление ситуаций.
Подведем итог рассмотренным примерам решения задач. Практика показывает, что использование ассоциативного планирования позволяет повышать эффективность поиска решений некоторых задач. Реализация в решателе этого нового метода планирования, дает значительные преимущества по сравнению с системами, ориентированными на использование традиционных методов решения.
программирование геометрический задача алгоритм
Литература
1. Вакин В. В., Корухова Л. С., Любимский Э. З., Малышко В. В. Ассоциативные методы планирования решений сложных задач. - М.: Препринт Института прикладной математики им. М. В. Келдыша РАН, № 81, 1997 г.
2. Корухова Л. С., Любимский Э. З. О процедурности и непроцедурности в задачах планирования целенаправленной деятельности. - М.: Известия Академии Наук. Серия: «Техническая кибернетика», № 5, стр. 72-78, 1994.
3. Корухова Л. С., Любимский Э. З., Малышко В. В. Реализация стратегий планирования на основе управляющих стереотипов. - М.: Препринт Института прикладной математики им. М. В. Келдыша РАН, № 13, 2000 г.
4. Forgy C. L. RETE: A fast algorithm for the many pattern / many object pattern match problem. Artificial Intelligence, Vol. 19, pp. 17-37, 1982.
5. Kolodner J. L. Case-Based Reasoning. Los Altos, CA: Morgan Kaufmann. 1993.
6. McDermott J. R1: a rule-based configurer of computer systems. Artificial Intelligence, Vol. 19, pp. 39-88. 1982.
7. Melis E., Whittle J. External Analogy in Inductive Theorem Proving. Proceedings of the 21st German Annual Conference on Artificial Intelligence (KI-97). Albert-Ludwigs University. 1997.
8. Melis E. Proof Planning with Multiple Strategies. Proceedings of the 14th Annual Conference of the Canadian Association for Distant Education (CADE-98). 1998.
9. Miranker D.P., Lofaso B.J. The organization and performance of a TREAT-based production system compiler. - The IEEE Transactions on Knowledge and Data Engineering. Vol. 3, No. 1, pp. 3-9 March 1991.