LINUX.ORG.RU
Форум — Development  

Набор правил «Условие->Действие»; умеет ли такое Пролог или кто еще?


0

0 

Есть такая задача (она кажется на удивление стандартной и общей, у
меня к ней сводятся сразу несколько задач, на первый взгляд
несвязанных):

Есть объекты, которые можно описать вектором параметров.

Есть набор правил:

Condition1 -> Action1
..............
ConditionN -> ActionN

Нужно сгенерировать код который выполнит те Action для которых Condition
выполнен.

Каждый Condition это булевская комбинация примарных выражений.  Примарное выражение это тест из достаточно ограниченного набора типов:
например это может быть тест одной переменной на равенство, или меньше-больше
Это может быть тест на то матчится ли переменная регэкспом.
Это может быть тест на то что линейный функционал от набора переменных
больше нуля.

Таким образом для примарных выражений очень часто можно автоматически
вывести информацию о логическом следовании: например зная значение
одного выражения можно узнать значения некоторых других.
Более того в случае когда примарные выражения это тест линейного
функционала от нескольких переменных, то там можно автоматически
вывести отношения следования когда зная значения нескольких выражений
можно узнать значения многих других.

Разумеется нужно сгенерировать tree-like код, который сможет
учитывать зависимости выражений и не будет делать лишние вычисления.

Алгоритм который я собираюсь использовать таков: я беру набор всех
встречающихся примарных выражений.  Дальше я смотрю каждое
примарное выражение.  Каждое примарное выражение это разделение пространства на две части.  Так как примарные выражения имеют
фиксированную структуру, то как правило я могу определить совместность
набора примарных выражений, таким образом я могу подсчитать L -- кол-во
Action'ов не имеющих пересечения с одной части пространства,  я смогу подсчитать
R -- кол-во Action'ов не имеющих пересечения с другой частью пространства.
Еще могут быть Action'ы лежащие и там и там.
Дальше я возьму примарное выражение для которого минимально
выражение max(L, R).  И сгенерирую код который вычислит его
и разветвит код на 2 бранча.

Далее в каждом бранче я проведу редукцию набора правил
с учетом знания значения этого выражения.
И повторю процесс для каждого бранча.


Теперь вопросы, является ли эта задача стандартной, есть ли у нее имя?
Какие другие алгоритмы для ее решения есть?

Эта задача кажется ложащейся на Пролог.  Умеет ли Пролог ее оптимально
решать?  Или какие-нибудь другие языки?
★★★★★

> Эта задача кажется ложащейся на Пролог. Умеет ли Пролог ее оптимально решать?

В принципе, да. Насчет "оптимально" -- зависит от опыта и радиуса кривизны рук.

> Или какие-нибудь другие языки?

Jess -- Java Expert System Shell:

http://herzberg.ca.sandia.gov/jess/

У меня, в принципе, еще неплохая книга есть, "Jess in Action -- Rule-Based Systems in Java". Где качал -- уже не помню, могу поделиться. Только пиши на eugine.kosenko@gmail.com.

Правила описываются на лисп-подобном языке, что позволяет совместить описание паттернов и императивного поведения действий. Так как ядро на Java, легко интегрируется с Java NetBeans, что позволяет создавать достаточно развитые приложения, в отличие от того же Пролога.

Система, конечно же, закрытая коммерческая, но лицензия позволяет бесплатное использование в академических целях.

> Теперь вопросы, является ли эта задача стандартной, есть ли у нее имя?

Да, это реализация систем, основанных на правилах. В частности, это все экспертные системы, хотя применение движков на правилах шире.

Я, например, заинтересовался такими системами, когда понадобилось реализовать адаптивную систему валидации данных, когда в зависимости от обстоятельств нужно выключать отдельные универсальные правила проверки. Правда, как всегда, я вначале сделал, а только потом начал смотреть, как это сделать правильно :-).

> Какие другие алгоритмы для ее решения есть?

Вообще говоря, классическим является алгоритм Рети (Rete), основанный на одноименных сетях. В книжке, что я рекомендовал, есть его описание в главе 8 части 2. Сам я, правда, не добрался, чтобы разобраться.

eugine_kosenko ★★★
()

резюмируя:

Есть основное свойство примарных выражений: если есть набор их либо их отрицаний, можно узнать совместны ли они. Это основное свойство может быть использовано для логического вывода одних выражений из других.

Теперь имея набор правил нужно скомпилировать его в дерево решений, которое способно найти набор Действий для любого вектора параметров и сделает это вычислив как можно меньше примарных выражений

dilmah ★★★★★
() автор топика
Ответ на: комментарий от eugine_kosenko

спасибо, читаю сейчас про сети Рети на вики

dilmah ★★★★★
() автор топика
Ответ на: комментарий от tailgunner

> А так же CLIPS

The CLIPS expert system shell (http://www.ghgcorp.com/clips/CLIPS.html), an open-source rule engine written in C, was the original inspiration for Jess. Jess and CLIPS were written by entirely different groups of people, however, and their implementations have always been very different. Jess is dynamic and Javacentric, so it automatically gives you access to all of Java’s powerful APIs for networking, graphics, database access, and so on; CLIPS has none of these facilities built in. Still, there is a strong similarity between the rule languages supported by these two systems. Many of the core concepts of Jess were originally derived from CLIPS, which was itself influenced by early rule engines like OPS5 and ART.

NOTE FOR CLIPS USERS

The Jess rule engine and Jess does not implement everything that CLIPS does (COOL, the CLIPS Object Oriented Language, is one notable example). If you have previous experience using CLIPS, don’t assume you can skip over this part of the book.

Там в книжке вообще неплохой обзор дан. :-)

eugine_kosenko ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development