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

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

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

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

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

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

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

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

منابع

• Forgy, C.L. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem, Artificial Intelligence, 19 (1982), pp. 17–37.
• Winston,P.H. Artificial Intelligence, Third Edition, Addison-Wesley, 1992, pp. 119–161.
• Giarratano,J. and Riley,G. Expert Systems: Principles and Programming, PWS Publishing Co., 1994 pp. 513–545.