الگوریتم رته

از ویکی جامع پردیس دانشگاهی دانشگاه قم
پرش به: ناوبری، جستجو
سیستم های خبره
مقاله بعدی:داده کاوی
مقاله قبلی:الگوریتم مارکوف

Forgy: Introduced pattern matching to detect changes in matches , the Rete algorithm.

Compiles rule memory into networks that avoid duplication between rules and over time , as the network is updated only when the rule base is changed.

در سال 1979 ، چارلز فوجی از دانشگاه کارنگی ملون ، الگوریتم رته را پیشنهاد داد که منجر به OPS شد.

OPS = Official Production System

OPS → OPS2 → OPS3 → OPS4 → OPS5 → OPS89 → ... CLIPS

اطلاعات مربوط به قواعد (قانون‌ها یا همان تولیدها) در قالب شبکه ، ذخیره می‌شود. بنابراین Rete یک گراف جهت‌دار ، حلقوی و ریشه‌دار است . هر مسیر از ریشه تا برگ ، سمت چپ قوانین است و هر گره ، جزئیاتی که بر قوانین ، منطبق هستند ، ذخیره می‌کند.

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

الگوریتم رته.JPG


نکته
CLIPS یکی از پوسته‌هایی است که از الگوریتم رته ، در موتور استنتاج خود بهره می‌گیرد.


CLIPS = C Language Integrated Production System

Design using the C programming language at NASA /Johnson Space Center with the specific purpose of providing high portability , low cost , and easy integration with external systems.

شکل زیر چرخه استنتاج در CLIPS را نشان می‌دهد:

چرخه استنتاج در CLIPS.JPG

مثال:با فرض پایگاه دانش و حافظه کاری ، شبکه رته را آنالیز کنید.

Rule Memory :

A(x) ˄ B(x) ˄ C(y) → add D(x)

A(x) ˄ B(y) ˄ D(x) → add E(x)

A(x) ˄ B(x) ˄ E(x) → delete A(x)

Working Memory:

{ A(1) , A(2) , B(2) , B(3) , B(4) C(5) }

شکل زیر یک شبکه رته نشان می‌دهد:

شبکه رته.JPG

جواب: باتوجه به تعریف الگوریتم رته هر مسیر از ریشه تا برگ سمت چپ قوانین هستند با توجه به شکل زیر fact ها یا حقایق در سمت چپ وقوانین در سمت راست می‌باشند .

با توجه به شکل بریده شده الگوریتم زمانی می‌تواند به ادامه کار خود بپردازد که A=B باشد یعنی بر سر راه آن یک شرط قرار دارد

If A=B then …

تنها زمانی که شرط برقرار باشد الگوریتم میتواند مسیر خود را ادامه دهد

مقدار x در A برابر 1و2 می‌باشد

مقدار x در B برابر 2و3و4 می‌باشد

یعنی زمانی شرط برقرار است که مقدار x در AوB برابر 2 باشد.

حل مثال رته.JPG

بر طبق Rule memory که داشتیم (A(X) ^ B(X) ^ C(y) → add D(x همانطور که در شکل زیر می‌بینید قانون ما صدق می‌کند پس می‌توانیم D را اضافه کنیم.

حل مثال رته2.JPG

همانطور که در شکل بالا مشاهده می‌کنید اضافه شدن D باعث اضافه شدن نود D در شکل پایین می‌شود.

حل مثال رته3.JPG

همانطور که در شکل زیر می‌بینید برای ادامه الگوریتم مانند مرحله اول دوباره شرطی باید برقرار باشد یعنی A باید با B برابر باشد و تنها زمانی این برابری پابرجاست که مقدار A و B برابر با 2 باشد .

زمانی که شرط برقرار شد به یک Rule memory دیگر می‌رسیم که داشتیم (A(X) ^ B(y) ^ D(x) → add E(x و بر طبق همین قانون E اضافه می‌شود.

حل مثال رته4.JPG

همانطور که در شکل زیر مشاهده می‌کنید با اضافه کردن E نود E به وجود می‌آید.

حل مثال رته5.JPG

همانطور که در شکل زیر مشاهده می‌کنید با اضافه شدن نود E و برقرار بودن شرط A=B و برقرار بودن قانون

A(X) ^ B(X) ^ E(x) → delete A(x)

تنها زمانی که مقدار A و B و E برابر با 2 باشند باعث حذف A می‌شود که در این مثال A برابر با 2 می‌باشد و با حذف شدن A کل الگوریتم می‌ایستد .

حل مثال رته6.JPG

و در آخر شکل کلی الگوریتم رته ما به شکل زیر می‌شود:

Tatbighe rete.JPG

مزیت الگوریتم رته

1. سرعت زیاد دسترسی به قوانین

مشکلات و محدودیت‌های الگوریتم رته

1. حافظه زیاد مورد نیاز

2. پیچیدگی ساختار