الگوریتم تورینه (Rete Alghorithm)، الگوریتم تطابق الگوی کارآمدی برای پیاده‌سازی سامانه‌های خِبره‌ٔ مبتنی بر قانون‌ها (Rules) است. الگوریتم تورینه در سال 1979 توسط دکتر چارلز فورگی از دانشگاه کارنگی ملون طراحی شده است. مفهوم تورینه بعنوان پایهٔ بسیاری از سامانه‌های خبره مانند OPS5, JESS, CLIPS و LISA درآمده است ولی اولین بار در OPS5 بکار گرفته شد.

یک پیاده‌سازی ساده‌ از یک سیستم خبره ممکن است هر قانون را به ازای واقعیت‌های (Facts) موجود در پایگاه دانش بررسی نموده و در صورت لزوم آن قانون را فعال کند و سپس سراغ قانون بعدی برود (و زمانی که قوانین به انتها رسید در یک حلقه به اولین قانون بازگردد). حتی برای پایگاه‌های دانش با تعداد واقعیت‌ها و قوانین متوسط نیز این دیدگاه ساده‌انگارانه بیش از حد کند عمل می‌کند.

الگوریتم تورینه یا Rete (که از لغت لاتین "rete" به معنای تور یا شبکه مشتق شده‌است) پایه‌ای برای پیاده‌سازی بهینه‌تر یک سامانهٔ خبره را تأمین می‌کند. یک سامانهٔ خبره‌ٔ مبتنی بر تورینه، شبکه‌ای از گره‌ها را می‌سازد که در آن هر گره (بجز ریشه) هم‌ارز با یک الگو است که در بخش سمت چپ یک قانون رخ می‌دهد. مسیری که از ریشه به یک گره‌ٔ برگ وجود دارد، بخش سمت چپ یک قانون را به طور کامل توصیف می‌کند. هر گره حافظه‌ای دارد از واقعیت‌هایی که الگوی مد نظر آن گره را داشته‌اند.

زمانیکه واقعیت‌های تازه‌ای وارد می‌شوند یا واقعیت‌هایی تغییر داده می‌شوند، ویژگی‌های این واقعیت‌های جدید در سراسر شبکه منتشر می‌شود و موجب می‌گردد که گره‌ها وضعیت خاصی که آن واقعیت با الگوی موجود در گره مطابق می‌شود را در حافظه‌ٔ خود ثبت کنند. زمانیکه یک واقعیت یا ترکیبی از واقعیت‌ها باعث ارضای کلیه‌ٔ الگوهای یک قانون شدند، به یک گره‌ٔ برگ می‌‌رسیم و قانون هم‌ارز آن فعال می‌شود.

الگوریتم تورینه به شکلی طراحی شده است که حافظه مصرفی را فدای سرعت بیشتر می‌نماید. در اغلب مواقع، سرعت این روش در مقایسه با پیاده‌سازی ساده‌انگارانه‌ای (که در بالا توصیف شد) چند برابر است (چرا که کارآیی الگوریتم تورینه به شکل نظری مستقل از تعداد قوانین موجود در سیستم است). هر چند در سیستم‌های خبرهٔ بسیار بزرگ، استفاده از الگوریتم تورینه به شکل بدون تغییر مشکلات کمبود حافظه را بوجود می‌‌آورد. از زمان طراحی الگوریتم تورینه، الگوریتم‌های دیگری – چه مبتنی بر تورینه و چه الگوریتم‌های کاملاً جدید – طراحی شده‌اند که نیاز به حافظهٔ کمتری دارند.

[ویرایش]

ویژگی‌های کارکردی الگوریتم تورینه

• قوانین حاصله می‌توانند با هدف بهینه‌سازی فرآیند تطبیق الگو مرتب‌سازی مجدد گردند.
• الگوریتم تورینه یک درخت تصمیم‌گیری می‌سازد که الگو را در تمامی قوانین پایگاه دانش ادغام می‌کند.
• این الگوریتم از یک گراف دارای ریشه، بدون دور و جهت دار بعنوان درخت تصمیم‌گیری استفاده می‌کند.

The Rete algorithm is an efficient pattern matching algorithm for implementing rule-based ("expert") systems. The Rete algorithm was designed by Dr. Charles L. Forgy of Carnegie Mellon University in 1979. Rete has become the basis for many popular expert systems, including JRules, OPS5, CLIPS, JESS, Drools, and LISA.

A naïve implementation of an expert system might check each rule against the known facts in the Knowledge base, firing that rule if necessary, then moving on to the next rule (and looping back to the first rule when finished). For even moderate sized rules and facts knowledge-bases, this naïve approach performs far too slowly.

The Rete algorithm (usually pronounced either 'REET' or 'REE-tee', from the Latin 'rete' for net, or network) provides the basis for a more efficient implementation of an expert system. A Rete-based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left-hand-side of a rule. The path from the root node to a leaf node defines a complete rule left-hand-side. Each node has a memory of facts which satisfy that pattern.

As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered.

The Rete algorithm is designed to sacrifice memory for increased speed. In most cases, the speed increase over naïve implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system). In very large expert systems, however, the original Rete algorithm tends to run into memory consumption problems. Other algorithms, both novel and Rete-based, have since been designed which require less memory.

Contents [hide] 1 Rete II 2 Rete III 3 Reference 4 External links

[edit]

Rete II

In the 1980s Charles L. Forgy developed a successor to the Rete algorithm named Rete II [1]. Unlike the original Rete (which is public domain) this algorithm was not disclosed. Rete II claims better performance for more complex problems (even orders of magnitude).

[edit]

Rete III

While at RulesPower, now acquired by Fair Isaac, Charles L. Forgy developed Rete III [2], a successor to Rete II. Rete III claims even better performance than Rete II for problems that involve both complex rules and large collections of facts.

[edit]

Reference

• Charles Forgy, "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19, pp 17-37, 1982

[edit]

External links

• Detailed and accessible description of Rete, also describes variant named Rete/UL, optimised for large systems (PDF)
• Rete information on Drools.org, Drools is an open source rules engine implementation
• Rete information on Jess
• ILog, rule management system that uses Rete
• ILOG JRules product page, JRules is a pure Java rule engine offering. JRules uses the Rete Plus algorighm for one of its optimized engine execution choices.
• ILOG Rules for .NET product page, Rules for .NET is a pure .NET rule engine offering. Rules for .NET uses a proprietary Rete algorighm for one of its optimized engine execution choices.
• Fair Issac Rules product page, rules management system that uses Rete III
• According to the Rules

Retrieved from "http://en.wikipedia.org/wiki/Rete_algorithm"

Categories: Algorithms