Пролог откат назад VS Rete откат
В моем классе меня обучали алгоритму обратного отслеживания Prolog и алгоритму Rete forprop, но мне также сказали, что Rete можно использовать для создания backprop.
Как это работает? Чем он похож / отличается от Пролога?
Например, это одно из упражнений, которые мне дали:
(R1) 24fingers and antennas => origin(mars)
(R2) shy and 5feet => origin(mars)
(R3) shy and 4arms => origin(venus)
(R4) looksDownWhenTalking => shy
(R5) fleesWhenSeen => shy
Целью является приведение следующих фактов установления происхождения иностранца:
(F1) fleesWhenSeen
(F2) 4arms
В Прологе мы бы решали эту проблему с помощью шаблона, соответствующего цели origin(X) против RHS правил. Правило совпадает с R1, R2 и R3, поэтому сначала сработает R1, и мы попытаемся решить подзадачи 24fingers and antennas который потерпит неудачу
Затем мы вернемся к началу и активируем R2, который в конечном итоге потерпит неудачу, и, наконец, вернемся назад и активируем R3, что успешно.
Так X заканчивается привязанным к venus в успешном запросе, и алгоритм заканчивается.
Теперь, как бы мы выполнили то же упражнение, используя алгоритм rete backprop?
Я наивно предполагаю, что мы будем использовать список подзадач, начиная с origin(X), чтобы начать запуск правил, чья RHS соответствует подцелям.
Но мне неясно, как алгоритм Rete позаботится о возврате в случае отказа некоторых подцелей, или как он узнает, что он добился успеха, когда решит определенное подмножество целей.
2 ответа
Не существует стандартной реализации для поддержки обратной цепочки в системе прямой цепочки. Гибридные инструменты реализовали эту функциональность, используя различные методы. Один метод, управляемый данными обратной цепочки, описан здесь: http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/. Некоторая дополнительная информация: JESS против DROOLS: обратное сцепление и http://herzberg.ca.sandia.gov/docs/70/rules.html.
Объяснение алгоритма Rete приведено здесь: http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218.
В Прологе используется унифицированный алгоритм, который в отличие от сопоставления с образцом имеет шаблоны с обеих сторон (цель / глава правила).
редактировать
Здесь много информации о Рете и Прологе.
Построение экспертных систем в Прологе
http://www.amzi.com/distribution/files/xsip_book.pdf
http://www.oopweb.com/Prolog/Documents/XSIP/Volume/08performance.htm
ТЕОРЕТИЧЕСКИЕ РАМКИ И РЕАЛИЗАЦИЯ ПРОЛОГОВОГО ИНТЕРПРЕТАТОРА