تفاوت
مبتنی بر دانش به عامل حل مساله:
عامل
حل مساله دانش بسیار محدودی دارد.دانش
عامل حل مساله بسیار خاص و غیر قابل انعطاف
است.
عاملهای
مبتنی بر دانش در مواجهه با محیطهای قابل
مشاهده جزیی موفقترند.
عاملهای
مبتنی بر دانش انعطاف پذیرند.
مشکل
منطق این است که در بسیاری از محیطها با
عدم قطعیت مواجه هستیم و منطق نمیتواند
آنرا نشان دهد.
برای
ساخت یک عامل مبتنی بر دانش دو روش وجود
دارد:
اعلانی:
مزیت
این روش امکان استفاده از دانش به روشهایی
است که طراح عامل پیشبینی نمیکرده.
رویه
ای:
مزیت
این روش سرعت اجرای بیشتر است.
دنیای
وامپوس :
قابل
مشاهده جزیی.
قطعی.
غیراپیزودیک.
ایستا.
گسسته
و تک عاملی است(وامپوس
خودش عامل نیست بلکه از ویژگی های محیط
است.)
هر
دنیای ممکن یک مدل است.
جمله
ای که در مدل باشد درست است.
و
مدل با دنیای عامل متفاوت است.
یک
KB
مستلزم
a
است
اگر در هر دنیایی که KB
درست
است a
نیست
درست باشد بعبارت دیگر M(KB)
زیر
مجموعه M(a)
باشد.
وقتی
و تنها وقتی a
مستلزم
b
است
که a
میدهد
b
یک
جمله معتبر باشد.
تعیین
ارضا پذیر بودن NP-Complete
است.
میگوییم
a
مستلزم
b
است
اگر و فقط اگر a^~b
ارضا
نشدنی باشد.
بسیاری
از جملات قابل تبدیل به هورن هستند اما
همه آنها نیستند مثلا a^b
هر
جمله ای قابل نوشتن به فرم نرمال
کوالسکی(استلزامی)
است.
هر
جمله ای را میتوان بر فرم نرمال عطفی CNF
نوشت.
هر
جمله شرطی معتبر یک استنتاج را نشان میدهد.
خاصیت
یکنواختی در منطق گزاره ای و مرتبه اول
برقرار است اما در منطق احتمالی وجود
ندارد.
اگر
n
متغیر
داشته باشیم تعداد مدلها برابر 2^n
خواهد
بود و پیچیدگی زمانی استنتاج شمارش O(2^n)
در
هر بار رزولوشن کامل میتوان تنها یک متغیر
را با نقیض آن حذف کرد.
پیچیدگی
زمانی TT-Entoilsبرابر
2^n
است
و پیچیدگی فضایی آن n.
الگوریتم
رزولوشن یک الگوریتم کامل کاذب است.
زمان
الگوریتم زنجیرسازی رو به جلو خطی برحسب
اندازه پایگاه داده است.
الگوریتم
زنجیر سازی رو به جلو کامل کاذب است.
زنجیر
سازی رو به عقب سریعتر از رو به جلو است.
زنجیر
سازی رو به جلو استدلال مبتنی بر داده است
و زنجیر سازی رو به عقب استدلال مبتنی بر
هدف است.
ورودی
DPLL
بصورت
نرمال عطفی است.
سه
هیورستیک برای DPLL
داریم:
۱.هیورستیک
خاتمه زودهنگام(باعث
میشود تمام زیردرختها بررسی نشوند در
نتیجه الگوریتم زودتر خاتمه یابد.)
۲.هیورستیک
نماد محض.
۳.هیورستیک
عبارت واحد.
الگوریتم
WALKSAT
تپه
نوردی است.
الگوریتم
WALKSAT
در
صورتی که بتواند حالتی پیدا کند که جمله
را ارضا کند آنرا برمیگرداند در غیر
اینصورت وجود failure
به
معنی ارضا ناپذیری نیست!
الگوریتم
WALKSAT
برای
مسایلی که مطمین هستیم ارضا پذیرند مناسبتر
است.
در
مسایل ارضا پذیر سخت WALKSAT
مناسبتر
از DPLL
است.
اگر
از مدار استفاده کنیم باید:
۱.
خاصیت
محلی بودن داشته باشد.
۲.
فیدبکها
دارای عنصر تاخیر باشند.
مشکلات
عوامل مبتنی بر منطق گزاره ای:
۱.نیاز
به تعداد زیادی گزاره برای یک مساله کوچک.
۲.
نیاز
به نگهداری چیزهایی مثل مکان و جهت.
الگوریتم
FC
را
میتوان به دو صورت استفاده کرد یا برای
اثبات درستی یک جمله و یا برای استخراج
دانش و تولید جملات صحیح که حالت دوم نیازی
به هدف ندارد.
استدلال
با زنجیره عقبگرد روی definite
cluaseها
کامل است.
یک
عبارت هورن تنها یک لیترال منفی دارد.
اگر
از KB
بشود
a
را
استنتاج کرد از ترکیب عطفی KB
با
هرچیزی نیز میتوان a
را
استنتاج کرد.
انتشار
واحد در الگوریتم DPLL
برای
حل مسایل SAT
کارکردی
مشابه Forward
chaining روی
عبارت معین دارد.
چیزهایی
که باید از کتاب خوانده شود:
عامل
مبتنی بر دانش.
روشهای
اعلانی و رویه ای.
دنیای
وامپوس.
تعریف
منطق و تعریفهای مرتبط با آن.
تعریف
منطق مرتبه اول.
مدل.
استلزام.
هم
ارزی.
جمله
معتبر.
ارضا
پذیر بودن.
فرم
نرمال هورن.
فرم
نرمال استلزامی یا فرم نرمال کوالسکی.
فرم
نرمال عطفی CNF.
فرم
نرمال KCNF.
فرم
نرمال فصلی DNF.
استنتاج.
خاصیت
(صحت.
کامل
بودن.
کامل
کاذب بودن.
یکنواختی).
استنتاج
شمارش مدل.
استنتاج
با قوانین استنتاج.
قوانین
استنتاج.
الگوریتم
TT-Entoils.
الگوریتم
رزولوشن.
الگوریتم
زنجیر رو به جلو FC.
زنجیر
سازی رو به عقب.
الگوریتم
های بررسی ارضا پذیری جمله(DPLL
و
WALKSAT).
هیورستیک
های (خاتمه
زودهنگام.
نماد
محض و عبارت واحد).
عاملهای
مبتنی بر مدار.
هیچ نظری موجود نیست:
ارسال یک نظر