انتساب
تهی معتبر است!
اگر
یک csp
بصورت
افزایشی فرموله بندی شده باشد میتوان
آنرا با جستجوی عمقی با حداکثر عمق محدود
حل کرد و جواب حتما در عمق n
خواهد
بود.
جستجوی
عقبگرد یک الگوریتم ناآگاهانه است و برای
مسایل بزرگ کارآمد نیست.
هیورستیک
MRV
به
سوال اینکه متغیر بعدی به این سوال اینکه
متغیر بعدی که باید مقدار بگیرد بهتر است
کدام باشد؟ جواب متغیر بعدی بهتر است
متغیری باشد که مقادیر معتبر باقیمانده
برای آن کمتر از بقیه باشد پاسخ میدهد.
هیورستیک
MRV
باعث
میشود شاخه های بیشتری هرس شوند.
و
فاکتور انشعاب موثر را کمتر میکند.
هیورستیک
درجه ای به این سوال که متغیر بعدی که باید
مقدار بگیرد بهتر است کدام باشد؟ جواب
متغیری را انتخاب کن که در تعداد بیشتری
از محدودیهای متغیرهای بدون انتساب نقش
داشته باشد میدهد.
هیورستیک
درجه ای سعی میکند فاکتور انشعاب را در
آینده کاهش دهد.
هیورستیک
MRV
قدرتمندتر
است اما هیورستیک درجه ای میتواند راهگشا
باشد.
هیورستیک
LCV
به
این سوال پاسخ میدهد پس از اینکه متغیری
انتخاب شد مقادیر آن بهتر است به چه ترتیبی
بررسی شوند؟ جواب ابتدا مقادیری را بررسی
کن که کمترین محدودیت را روی مقادیر معتبر
متغیرهای بدون انتساب ایجاد میکند را
میدهد.(کاری
به انتخاب گره ندارد!)
هیورستیک
LCV
سعی
میکند بیشترین قابلیت انعطاف را برای
انتسابهای بعدی داشته باشد در نتیجه
احتمال عقبگرد را کم کند.
اگر
به دنبال تمام جوابها باشیم نه اولین راه
حل هیورستیک LCV
هیچ
تاثیری ندارد!)
بررسی
پیشرو نه به اینکه کدام گره را انتخاب
کنیم و نه به اینکه به گره انتخاب شده چه
مقداری دهیم جواب نمیدهد.
فقط
وقوع تضاد در آینده را تشخیص میدهد.
بررسی
پیشرو وجود تناقض را زودتر از BT
تشخیص
میدهد.
بهتره
اول FC
بزنیم
بعدش MRV.
بررسی
سازگاری یال میتواند تناقضها را زودتر
از FCتشخیض
دهد.
پیچیدگی
AC-3
برابر
O(n^2d^3)
است.
الگوریتم
AC-3
تمام
ناسازگاری ها را نمیتواند تشخیص دهد.
سازگاری
گره همان سازگاریk
به
ازای k=1
است.
سازگاری
یال همان سازگاری k=2
است.
الگوریتم
AC-3
فقط
این ناسازگاری را برطرف میکند.
سازگاری
مسیر همان سازگاری k=3
است.
اگر
یک csp
قویا
سازگار n
باشد
میتوان بدون عقبگرد حل کرد.
در
الگوریتم BT
ممکن
است عقبگرد غیرهوشمند مفید نباشد.
در
جاهایی که از بررسی پیش رو یا از روشهای
سازگاری k
استفاده
میشود استفاده از پرش به عقب زاید است.
پرش
به عقب ساده در برخی موارد کاربرد ندارد
و باید از پرش به عقب با هدایت هوشمند
استفاده کرد.
پرش
به عقب ساده و پرش به عقب با هدایت برخورد
هم در شرط انجام برخورد و هو در نحوه اجرای
پرش تفاوت دارند.
یک
امتیاز جستجوی محلی امکان تنظیمات آنلاین
در صورت تغییر صورت مساله است.
راهکار
تغییر در ساختار گراف مساله csp
عبارتند
از:
۱.
تقسیم
مساله به چند زیر مساله مستقل.
پیچیدگی
زمانی این روش O(n/c
* d^c) است(این
روش وقتی موثر است که c
نسبت
به n
کوچک
باشد.
در
غیر این صورت فرقی نمیکند و همچنین هر
مساله ای را نمیتوان به این روش حل کرد.)
۲.
استفاده
از الگوریتم سریعتر برای مسایل با ساختار
درختی پیچیدگی این روش O(nd^2)
است.
۳.
تبدیل
مساله اصلی به یک مساله با ساختار درختی(از
طریق حذف نود.
با
پیچیدگی O(d^c
* (n-c)*d^2) که
نسبت به n
خطی
است.
از
طریق تبدیل گراف محدودیت به درختی که هر
گره آن یک زیرگراف از گراف اصلی است.
با
پیچیدگی O(nd^2c).
۴.
توجه
به مقادیر متغیرها(مثلا
حذف جایگشتها)
برای
حل مسایل csp
جستجوی
عمق نخست مناسبتر است.
چیزهایی
که باید از کتاب خوانده شود:
تعریف
(csp
دامنه
.
انتساب
و … ).
مدل
سازی محدودیت.
فرموله
بندی ارضای محدودیت.
تعویض
پذیری.
الگوریتم
عقبگرد BT.
هیورستیک
یک متغیر با کمترین مقدار باقیمانده
MRV.هیورستیک
درجه ای.هیورستیک
مقدار با کمترین محدودیت LCV.
بررسی
پیش رو FC.
انتشار
محدودیت.
تعریف
یال سازگار و سازگار کردن یال.
نگهداری
سازگاری یال MAC.
الگوریتم
AC-3.
تعریف
سازگاری k
و
قویا سازگار k.
ناسازگاری
ALLDIFF.
تشخیص
ناسازگاری در محدودیت منبع.
ناسازگاری
در محدودیت حدود.
مجموعه
برخورد.هدایت
برخورد.
هیورستیک
کمترین برخورد.تقسیم
مساله به چند زیر مساله مستقل.
استفاده
از الگوریتم سریعتر برای مسایل با ساختار
درختی.
تبدیل
مساله اصلی به یک مساله با ساختار درختی.
توجه
به مقادیر متغیرها
هیچ نظری موجود نیست:
ارسال یک نظر