فهرست مطالب
عنوان صفحه
فصل اول: مقدمه
-
مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem) …………………………………….. 3
-
تعریف مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem):……………………………………….. 3
-
الگوریتمهای کلاسیک مسائل ارضاء محدودیت…………………………………………………………………………………………………….. 5
-
CSP به عنوان یک مسئله جستجو…………………………………………………………………………………………………………………….. 7
-
بهبود کارآیی الگوریتمهای جستجوتوسط توابع اکتشافی یا به عبارتی هیوریستیک ها………………………………………. 8
-
محدودیتهای ویژه………………………………………………………………………………………………………………………………………………… 12
-
کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت……………………………………………………………………………….. 12
-
ساختار مسئله………………………………………………………………………………………………………………………………………………………. 12
-
-
سیستمهای چند عامله………………………………………………………………………………………………………………………….. 14
-
حل مسائل CSP توسط سیستمهای چند عامله؛(DCSP)………………………………………………………………. 16
فصل دوم: مروری بر تحقیقات پیشین
-
مرور کلی………………………………………………………………………………………………………………………………………………. 19
-
الگوریتمهای هرس دامنه……………………………………………………………………………………………………………………… 22
-
الگوریتم تصفیه…………………………………………………………………………………………………………………………………………………… 22
-
الگوریتم فرا استدلال………………………………………………………………………………………………………………………………………….. 25
-
-
الگوریتمهای اکتشافی…………………………………………………………………………………………………………………………… 27
-
الگوریتم عقبگرد نامتقارن………………………………………………………………………………………………………………………………………. 28
-
الگوریتم الزام ضعیف نامتقارن…………………………………………………………………………………………………………………………………. 32
-
-
الگوریتمهایی که از ترکیب روشهای متمرکز و توزیع شده استفاده می کنند…………………………………….. 33
-
الگوریتم APO……………………………………………………………………………………………………………………………………………………….. 33
-
-
الگوریتمهای ناقص……………………………………………………………………………………………………………………………….. 37
-
الگوریتم DBA …………………………………………………………………………………………………………………………………………………… 37
-
الگوریتمهای مبتنی بر کلونی مورچه ها در حل مسائل ارضاء محدودیت توزیع شده…………………………………………. 37
-
فصل سوم: طراحی و پیاده سازی روشهای پیشنهادی برای مسائل DCSP و بررسی نتایج حاصله
-
معیارهای ارزیابی کیفیت روشهای حل مسائل ارضاء محدودیت توزیع شده…………………………………. 44
3-1-1- میانگین زمان اجرای الگوریتم با افزایش مقیاس مسأله………………………………………………………………………………………. 45
3-1-2- میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل ………………………………………………………………………….. 45
3-1-3- تعداد پیام های ارسال و دریافت شده……………………………………………………………………………………………………………………. 45
3-1-4- NCCC …………………………………………………………………………………………………………………………………… 45
3-1-5- قانونی و کامل بودن………………………………………………………………………………………………………………………………………………… 46
-
محکها و مجموعه داده ای مورد استفاده برای آزمایشات………………………………………………………………. 45
3-2-1- مسأله n-وزیر ……………………………………………………………………………………………………………………………………………………….. 46
3-2-2- مسأله رنگآمیزی گراف ……………………………………………………………………………………………………………………………………….. 47
3-2-3- مسائل زمانبندی …………………………………………………………………………………………………………………………………………………… 48
3-2-4- مسائل ارضاء محدودیت باینری ……………………………………………………………………………………………………………………………. 51
3-3- طراحی و پیاده سازی روشهای پیشنهادی و نتایج حاصله از آنها………………………………………………………. 52
3-3-1- استفاده از ترکیب الگوریتمهای تکاملی و سیستمهای چندعامله برای حل مسائل ارضاء محدودیت ……………… 52
3-3-2- قدرت مورچه ها در حل مسائل ارضاء محدودیت توزیع شده……………………………………………………………………………… 60
فصل چهارم: روش جدید ارائه شده
4-1- مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی…………………………………………………….. 69
-
توصیف مسائل ارضاء محدودیت توزیع شده؛(DCSP) ……………………………………………………………………………….. 69
-
تعریف محدودیت Alldiff یا Alldifferent ………………………………………………………………………………………………. 70
-
توابع اکتشافی …………………………………………………………………………………………………………………………………………………… 70
-
تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ……………………………………………………………. 71