user857

الگوریتم 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
4-3- توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن…………………………………………………………………… 73
4-4- حل یک مثال با استفاده از این الگوریتم…………………………………………………………………………………………….. 80
4-5- ارزیابی و مقایسه الگوریتم ما با دیگر روشها………………………………………………………………………………………. 82
4-6- نتیجه گیری و برشمردن مزایا و معایب این روش…………………………………………………………………………….. 84
فصل پنجم: نتیجه گیری
5-1- نتیجه گیری……………………………………………………………………………………………………………………………………… 87
5-2- پیشنهادات و کارهای آینده………………………………………………………………………………………………………………. 89
فهرست منابع……………………………………………………………………………………………………………………….. 90
فهرست تصاویر
عنوان صفحه
شکل 1-1 مثالي از مساله CSP [4] …………………………………………………………………………………………………………………. 4
شکل 1-2 یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54] ……………………….. 5
شکل 1-3 (الف) نواحی استرالیا (ب) عملکرد توابع اکتشافی مختلف بر روی این نقشه [2] …………………………………………… 11 شکل 1-4 زیرمسأله های مستقل در گراف محدودیت [2] ……………………………………………………………………………… 13
شکل 1-5 کاهش گراف محدودیت به درخت توسط حذف گرهها [2] ………………………………………………………….. 13
شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2] ……………………………………………………………. 14
شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[4] ………………………………. 15
شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20
شکل 2-2 چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4] ……………………………………………………………………………………………………………………………………. 24
شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسئله 4 وزیر[4] ………………………………………………………………………… 29
شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 29
شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسئله 4 وزیر[4] …………………………………………………………………….. 30
شکل 2-6 سیکل 4 و 5 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………… 30
شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31
شکل 2-8 سیکل 7 و 8 از الگوریتم ABT بر روی مسئله 4وزیر[4] ………………………………………………………….. 31
شکل 2-9 سیکل 9 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31
شکل 2-10 سیکل 10 از الگوریتم ABT بر روی مسئله 4وزیر [4] ……………………………………………………………… 32
شکل 2-11 الگوریتم APO [22] ……………………………………………………………………………………………………………………. 35
شکل 2-12 مثالی از گراف ساختار [44] …………………………………………………………………………………………………………. 39
شکل 2-13 ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… 40
شکل 3-1 جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. 46
شکل 3-2 یک جواب برای مسأله 8-وزیر …………………………………………………………………………………………………………. 47
شکل 3-3 مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… 48
شکل 3-4 مثالي از مساله CSP [4] …………………………………………………………………………………………………………………. 52
شکل 3-5 مدل فرض شده از محیط شبکه مانند عاملها[3] ……………………………………………………………………………. 53
شکل 3-6 میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [3] ……………………………………. 58
شکل 3-7 مقایسه الگوریتم MAEA-CSPs با 4 الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59
شکل 3-8 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… 63
شکل 3-9 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63
شکل 3-10 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .32 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 63
شکل 3-11 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.3 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64
شکل 3-12 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .72 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 64
شکل 3-13 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.7 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65
شکل 4-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72
شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA ………………………………………………………………………………………………….. 80
شکل 4-3 مرحله 5 از الگوریتم DACA ………………………………………………………………………………………………………….. 81
شکل 4-4 مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82
شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از 4 تا 104 در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82
فهرست جداول
عنوان صفحه
جدول 3-1 نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… 59
جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکمهای متفاوت …………………………………………….60
جدول4-1 مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل ……… 82
جدول4-2 مقایسه روش پیشنهادی ما با روش ERA از لحاظ میانگین زمان اجرا ……………………………………….. 82
فصل اول
مقدمه
از سال 1974، مسائل ارضاء محدویت (CSP) در مسأله پردازش تصویر پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر و رنگ آمیزی گراف گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی و تخصیص منابع و دیگر مسائل کاربردی بزرگ میتوانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار میروند [4].
از طرف دیگر موقعیتهایی وجود دارد که در آن یک مسأله بایستی در یک مد توزیع شده حل شود به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه میخواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در چنین مواقعی عاملها برای رسیدن به یک هدف مشترک تلاش میکنند. هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار میکنند [4].
مسأله ارضاء محدودیت توزیع شده (DCSP) در واقع حالت توزیع شدهی مسألهی ارضاء محدودیت کلاسیک است که در آن متغیرها بین عاملهای مستقل توزیع شدهاند. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را مالک میشوند و مقدار آن را کنترل میکنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم میگیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها میتواند با همسایه اش در گراف محدودیت ارتباط برقرار کند. هر عامل سعی میکند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب میشود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر میباشد [4] و [22]. این مسأله عمومی کاربردهای زیادی در زندگی واقعی دارد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده است. به عبارت دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است میتواند به عنوان DCSP طرح ریزی شود.
در این تحقیق به مسائل ارضاء محدودیت توزیع شده پرداخته میشود که در آن عاملها در یک مد توزیع شده برای یافتن یک راه حل ممکن برای مسأله تلاش میکنند.
مسأله ارضاء محدودیت
تعریف مسأله ارضاء محدودیت
به عنوان یک تعریف رسمی، یک CSP را میتوان با سه جزء اصلی آن تعریف کرد[3]:
یک مجموعه متناهی از متغیرها ، {x = {x1, x2, …, xn؛
یک مجموعه دامنه D، شامل یک دامنه گسسته و متناهی برای هر متغیر؛
D = {D1, D2, …, Dn} , Di = {d1, d2, . . ., d|Di| } for xi , i = 1, 2, . . . , n ;
یک مجموعه از محدودیتها، { C = {C1(x1 ), C2(x2 ), …, Cm(xm)، که xi ، i=1, 2 , . . . ,n، زیرمجموعهای از x است و Ci(xi) تعیین کننده مقادیری است که متغیرهای درون xi نمیتوانند به صورت همزمان به خود بگیرند. به عنوان مثال یک محدودیت به صورت 〈C({x1, x2}) = 〈d1, d2 بدین معنی است که وقتی x1 = d1 آنگاه مقدار d2 نمیتواند به x2 انتساب یابد و زمانی که x2 = d2 است x1 نمیتواند مقدار d1 بگیرد.
بنابراین فضای جستجوی S یک مسأله CSP عبارت است از یک ضرب کارتزین ازn مجموعه دامنه متناهی، به عبارت دیگر، S = D1 × D2 × . . . × Dn . یک راه حل برای یک CSP به صورت: s = 〈s1, s2, …, sn 〉 ∈ S، عبارت است از یک انتساب از مقادیر به متغیرها به طوریکه این انتساب تمام محدودیت ها را ارضاء کند. در اینجا یک مثال ساده از توصیف یک مسأله CSP داریم:
x = {x1, x2, x3}
D = {D1, D2, D3}, Di = {1, 2, 3}, i = 1, 2, 3
C = {C1 ({x1, x2}) = <1,3>, C2({x1, x2}) = <3,3>,
C3 ({x1, x3}) = <2,1>, C4({x1, x3}) = <2,3>,
C5 ({x1, x3}) = <3,1>, C6({x1, x3}) = <3,3>,
C7 ({x2, x3}) = <1,1>, C8({x2, x3}) = <1,2>,
C9 ({x2, x3}) = <1,3>, C10({x2, x3}) = <2,1>,
C11 ({x2, x3}) = <3,1>}
تمام راه حلهای ممکن برای مسأله ای که به صورت بالا توصیف شده است عبارت است از: 〈〈1,2,2 ، 〈〈1,2,3 ، 〈〈2,2,2 ، 〈〈2,3,2 ، 〈〈3,2,2 .
به بیانی سادهتر، یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. شکل 1-1 مثالی ساده از یک مسأله CSP را نشان میدهد که داراي سه متغير x1, x2, x3 و محدوديتهاي x1<>x3 و x2<>x3 است.

شکل 1-1 مثالي از مسأله CSP [4]
همانطور که گفته شد بسیاری از مسائل دنیای واقعی میتواند برای حل شدن به صورت یک مسأله CSP فرموله شوند. شکل 1-2 یک طرح جامع از به کار بردن تکنیک ارضاء محدودیت برای حل مسائل را نشان میدهد. با داشتن یک توصیفی از مسأله یک راه برای تعیین اینکه چگونه این مسأله میتواند توسط تکنیک ارضاء محدودیت حل شود تعریف سه جزء: متغیرها، دامنه متغیرها و محدودیتهاست. اگر بتوان این سه جزء را برای مسأله تعریف کرد این مسأله میتواند توسط تکنیکهای ارضاء محدودیت حل شود [54].

شکل 1-2 یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54]
الگوریتمهای کلاسیک مسائل ارضاء محدودیت
به طور کلی 4 الگوریتم به عنوان الگویتمهای کلاسیک حل مسائل CSP معرفی شده است [1]:
الگوریتم بازگشت به عقب (BT)، الگوریتم عمیق شونده تکراری (IB)، الگوریتم بررسی رو به جلو (FC)، الگوریتم پرش رو به عقب (BJ).
این الگوریتمها از ساختار درختی برای نشان دادن حالت فعلی جستجو استفاده میکنند. هریک از گره های درخت میتواند به عنوان یک راه حل جزئی در نظر گرفته شود. به طور همزمان مقادیر برخی از متغیرها از هر گره توسط یک لایه گره تصمیم گیری والد شناسایی میشود، این متغیرها متغیرهای گذشته نامیده میشوند. در مقابل متغیرهای گذشته متغیرهای آینده هستند که مقدار متغیرشان در یک گره انتخاب نشده است و مقدار این متغیرها ممکن است در یک زمان بعد تعیین شود. علاوه بر این متغیرهای جاری نیز داریم که در واقع همان متغیرهایی هستند که در حال حاضر در نظر گرفته شده اند. شاخه های درخت مقادیر ممکن متغیرهاست. بعد از انتخاب یک شاخه در درخت الگوریتم یک مقدار را به متغیر انتساب خواهد داد و توسط راه حل یافته شده تا اینجا مقادیر ناسازگار را از محدوده مقادیر متغیرهای آینده حذف خواهد کرد. چند الگوریتم بالا در نحوه برخورد با متغیر های آینده متفاوت هستند.
الگوریتم BT
هر گره یک مقدار برای آن متغیر که در حال مقایسه با راه حل جزئی جاری است، مشخص خواهد کرد. اگر محدودیتی نقض شد یا برخوردی با مقادیر متغیرهای گذشته داشت آنگاه برای مقدار دیگری برای آن متغیر جستجو میشود. زمانی که تمامی مقادیر در محدوده جاری جستجو شد اگرهیچ مقداری برای آن متغیر یافت نشود که با مقادیر متغیرهای گذشته در تناقض نباشد آنگاه الگوریتم به متغیر قبلی باز خواهد گشت تا مقداری دیگر از محدوده آن متغیر را بیابد. اگر هر متغیر مقداری از محدوده اش را به خود بگیرد در حالیکه هیچ محدودیتی نقض نشده است این الگوریتم خاتمه خواهد یافت.
الگوریتم IB
این الگوریتم اساسا یک الگوریتم جستجوی اول- عمق است با یک مقدار آستانهb . اگر B مجموعه آستانه جاری باشد و یک گره از درخت جستجو یا یک متغیر b بار ملاقات شده باشد آنگاه به زیر-گرههایی که ممکن است نادیده گرفته شوند دسترسی پیدا نخواهد کرد. اگر در این محدوده راه حلی پیدا نشود مقدار آستانه رفته رفته افزایش مییابد. اما اگر یک راه حل یافته شود یا مقدار آستانه b بزرگتر مساوی بزرگترین تعداد شاخه های درخت جستجو باشد این الگوریتم ممکن است خاتمه یابد.
الگوریتم FC
فرایند الگوریتم FC اساسا مشابه الگوریتم بازگشت به عقب است با این تفاوت که در این الگوریتم هر بار که برای یک متغیر عملیات انتساب انجام میشود الگوریتم FC تعدادی از مقادیر ناسازگار با مقدار متغیر جاری را از دامنه مقادیر دیگر متغیرها حذف میکند. اگر دامنه ای خالی شود مقدار انتسابی به متغیر جاری رد خواهد شد؛ در غیر اینصورت، الگوریتم FC این روند را برای دیگر متغیرها ادامه خواهد داد تا زمانی که به همه متغیرها مقداری انتساب یابد. اگر متغیر جاری همه مقادیرش رد شود عملیات بازگشت به عقب به متغیر قبلی انجام میشود. اگر هیچ متغیری برای بازگشت به عقبی وجود نداشته باشد مسأله غیر قابل حل است.
الگوریتمBJ
تنها تفاوت بین الگوریتم BT و BJ فرایند بازگشت به عقب آنهاست، مابقی دو الگوریتم یکسان است. وقتی نیاز به بازگشت به عقب باشد الگوریتم BJ به دنبال متغیرهایی خواهد گشت که باعث شکست شده اند. اگر هر مقدار از دامنه متغیر فعلی با مقدار متغیر های قبلی برخورد داشته باشد الگوریتم به نزدیکترین متغیری که باعث شکست شده است به عقب باز خواهد گشت نه اینکه تنها به متغیر قبلی برگردد. به عبارت دیگر این الگوریتم از روشی هوشمند در زمان بازگشت به عقب استفاده خواهد کرد. در این روش مجموعه ای داریم به نام مجموعه برخورد، مجموعه برخورد متغیر x شامل همه متغیرهایی است که قبلا مقدار گرفته اند و در گراف محدودیت به x متصل شدهاند. حال اگر در زمان حل مسأله نیاز به عقب گرد باشد، الگوریتم به آخرین گره از مجموعه برخورد آن متغیری که در آن به شکست رسیده است برمیگردد، یعنی به متغیری از آن مجموعه که نسبت به سایر اعضای مجموعه دیرتر مقداردهی شده است.

CSP به عنوان یک مسأله جستجو
یک مسأله CSP را میتوان توسط فرموله سازی افزایشی به صورت یک مسأله جستجوی استاندارد ارائه کرد [2]. برای این کار داریم:
حالت اولیه: انتساب تهی، که در آن هیچ متغیری مقدار ندارد.
تابع مابعد: انتساب یک مقدار به یکی از متغیرهای بدون مقدار. این مقداردهی بایستی به صورتی باشد که هیچ یک از محدودیت ها را نقض نکند.
آزمون هدف: آیا انتساب فعلی انتساب کاملی است؟
هزینه مسیر: یک هزینه ثابت برای هر مرحله در نظر گرفته میشود.
با استفاده از فرموله سازی مسائل CSP به صورت مسائل جستجو، میتوان از هر یک از الگوریتمهای جستجو برای حل این مسائل استفاده کرد.
از آنجایی که هر راهحل یک انتساب کامل میباشد بنابراین اگر مسأله ای دارای n متغیر باشد آنگاه راه حل در عمق n یافت خواهد شد و درخت جستجو نیز دارای عمق n میباشد. با توجه به این جستجوی عمقی برای CSP ها مناسبترند. از آنجایی که مسیری که از طریق آن به هدف میرسیم چندان اهمیتی ندارد بنابراین میتوانیم از فرموله سازی حالت کامل استفاده کنیم که در آن هر حالت یک انتساب کامل میباشد که ممکن است برخی از محدودیتها را ارضا نکند. از الگوریتمهای جستجوی محلی مانند تپه نوردی میتوان برای حل این مسائل استفاده نمود.
بهبود کارآیی الگوریتمهای جستجو توسط توابع اکتشافی
سیستم‌های پیچیده اجتماعی، تعداد زیادی از مسائلِ دارایِ طبیعتِ ترکیباتی را پیش روی ما قرار می‌دهند. مسیر کامیون‌های حمل‌ونقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید جایابی شوند، شبکه‌های ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابط‌های رادیویی می‌بایست دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازه‌های لازم بریده شوند؛ از این دست مسائل بی‌شمارند. تئوری پیچیدگی به ما می‌گوید که زمان حل مسائل ترکیباتی اغلب چندجمله‌ای نیستند. این مسائل در اندازه‌های کاربردی و عملی خود به قدری بزرگ هستند که نمی‌توان جواب بهینۀ آنها را در مدت زمان قابل پذیرش به دست آورد. با این وجود، این مسائل باید حل شوند و بنابراین چاره‌ای نیست که به جواب‌های زیر بهینه بسنده نمود؛ به گونه‌ای که دارای کیفیت قابل پذیرش بوده و در مدت زمان قابل پذیرش به دست آیند. چندین رویکرد برای طراحی جواب‌های با کیفیت قابل پذیرش تحت محدودیت زمانی قابل پذیرش پیشنهاد شده است.
الگوریتم‌هایی وجود دارند که می‌توانند یافتن جواب‌های خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آنها الگوریتم‌های تقریبی می‌گویند. الگوریتم‌های دیگری هستند که تضمین می‌دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به آنها الگوریتم‌های احتمالی گفته می‌شود. جدای از این دو دسته، می‌توان الگوریتم‌هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسأله مورد بررسی را به همراه داشته‌اند؛ به این الگوریتم‌ها، الگوریتم‌های اکتشافی گفته می‌شود.
توابع اکتشافی عبارتند از معیارها، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر. توابع اکتشافی نتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد.
خاصیت توابع اکتشافی خوب این است که ابزار ساده‌ای برای تشخیص خط مشی‌های بهتر ارائه دهند و در حالی که به صورت شرطی لازم، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌کنند اما اغلب به صورت شرط کافی این تضمین را فراهم ‌آورند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. توابع اکتشافی با استفاده از روش‌هایی که نیازمند ارزیابی‌های کمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارایه می‌نمایند، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود.
الگوریتمهای جستجو اغلب برای افزایش کارایی به دانش مرتبط با جهان مسأله نیاز دارند، اما مسائل CSP میتوانند بدون دانش وابسته به جهان مسأله به صورت کارایی حل شوند. روشهای عمومی قادرند با پاسخ به سوالات زیر توابع اکتشافی عمومی مناسبی را جهت افزایش کارایی الگوریتمهای حل مسائل CSP پیشنهاد دهند:
متغیر بعدی که قرار است مقدار بگیرد کدام است؟
مقدار گیری بر اساس چه ترتیبی انجام شود؟
مقداردهی متغیر جاری چه پیامدهایی برای سایر متغیرهای انتساب نیافته دارد؟
چگونه میتوان از تکرار مسیرهای منجر به شکست جلوگیری کرد؟
برخی از این توابع اکتشافی عبارتند از:
تابع اکتشافی حداقل مقادیر باقیمانده(MRV)
این تابع اکتشافی برای انتخاب متغیر بعدی که مقدار نگرفته است متغیری با کمترین مقادیر مجاز را انتخاب میکند. نامهای دیگر این تابع اکتشافی محدودترین متغیر و اولین شکست میباشند. علت نامگذاری اولین شکست آن است که اینگونه متغیرها، به احتمال زیاد به زودی به حالت شکست خواهد رسید.
2- تابع اکتشافی بالاترین درجه (MCO)
اگر تمام دامنه ها دارای یک اندازه باشند، تابع اکتشافی MRV نخواهد توانست در انتخاب اول هیچ کمکی بکند. تابع اکتشافی بالاترین درجه متغیر داری بالاترین درجه محدودیت در مقایسه با سایر متغیرهای مقدار نگرفته را انتخاب میکند.
3- تابع اکتشافی مقدار با حداقل محدودیت (LCV)
پس از انتخاب متغیر، مقدار خاصی برای انتساب باید انتخاب شود. تابع اکتشافی مقدار با حداقل محدودیت، مقداری را برای یک متغیر انتخاب میکند که در گراف محدودیت باعث ایجاد کمترین محدودیت در متغیرهای مجاور گردد.
در شکل 1-3 عملکرد این توابع اکتشافی برای رنگ آمیزی نقشه ایالات و نواحی استرالیا به نحوی که هیچ دو ناحیه ای رنگ یکسان نداشته باشند نشان داده شده است.

(الف)
تابع اکتشافی LCV
تابع اکتشافی MRV
تابع اکتشافی درجه

(ب)
شکل 1-3 (الف) ایالات و نواحی استرالیا. رنگ آمیزی این نقشه میتواند به صورت مسأله ارضاء محدودیت نمایش داده شود. هدف انتساب رنگها به هر ناحیه است، چنانچه هیچ دو ناحیه همسایه ای رنگ یکسان نداشته باشند. قسمت (ب) نحوه عملکرد توابع اکتشافی مختلف بر روی این نقشه نشان میدهد [2] .
محدودیتهای ویژه
برخی از محدودیتها آنقدر زیاد در مسائل اتفاق میافتند که میتوان آنها را به عنوان حالتهای خاص بررسی کرد.
محدودیت Alldiff : همه متغیرها بایستی مقادیر متفاوت داشته باشند. مسأله 8-وزیر یا پازل ریاضیات رمزی از این دسته محدودیتها دارد.
به شکلی رسمیتر میتوان محدودیت Alldiff را به صورت زیر تعریف کرد[56]:
با داشتن یک مجموعه از متغیرهای X={x1, x2, . . . , xn} با دامنه های D1, . . . , Dn ، مجموعه ای از چندتایی های مجاز به وسیله Alldiff(X) عبارتند از:
{ (d1, d2, . . . , dn) | di ϵ Di , di ≠ dj ∀ i ≠ j }
محدودیت Atmost یا Resource: مقدار همه متغیرها بایستی حداکثر یک مقدار مشخص باشد.
کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت
الگوریتمهای جستجوی محلی برای حل بسیاری از مسائل CSPبسیار موثرند. در این حالت از فرموله سازی حالت کامل استفاده میشود که در آن در ابتدا به هر متغیر حالت اولیه ای نسبت داده میشود و سپس در هر مرحله تابع مابعد مقدار یکی از متغیرها را تغییر میدهد. به عنوان مثال در مسأله 8-وزیر در ابتدا هر وزیر به تصادف درون یک ستون قرار میگیرد و سپس تابع مابعد یک وزیر را انتخاب نموده و آن را به جای دیگری درون همان ستون منتقل میکند. در انتخاب یک مقدار جدید برای یک متغیر، تابع اکتشافی حداقل تناقض ها بهترین اکتشاف میباشد. این تابع همواره مقداری را انتخاب میکند که کمترین برخورد را با سایر متغیرها ایجاد میکند.
ساختار مسأله
منظور از ساختار مسأله در مسائل CSP نحوه بیان محدودیتهاست. پیچیدگی حل یک CSP به شدت وابسته به ساختار گراف محدودیت است. گاهی میتوان از ساختار مسأله به منظور شناخت سریع و آسان راه حل استفاده نمود. اصولا مسائل CSP به صورت گراف محدودیت بیان میشوند که در موارد خاص میتوان این ساختار را تا حدودی ساده تر کرد، همانگونه که تنها راه برخورد با مسائل دشوار دنیای واقعی، تجزیه این مسائل به مسائل کوچکتر است. اولین راه برای این کار شناخت زیر مسأله های مستقل درگراف است. به عنوان مثال در شکل زیر T قسمتی مجزا از سایر متغیرهاست. به عبارتی رنگ آمیزی T و رنگ آمیزی سایر گرهها دو مسأله مستقل هستند پس هر جوابی برای T و هر جوابی برای سایر گرهها، در کنار هم جواب نهایی را تشکیل میدهند. متأسفانه این قبیل مسائل بسیار نادر هستند.

شکل 1-4 زیرمسأله های مستقل در گراف محدودیت[2]
ساختار بعدی در مسائل CSP ساختار درختی است. به عبارتی گراف محدودیت مسأله یک درخت است. زمان اجرای هر مسأله CSP با ساختار درختی نسبت به تعداد متغیرها دارای رابطه ای خطی میباشد. از آنجایی که حل یک CSP درختی آسان است میتوان گرافهای محدودیت را به درخت تقلیل داد. دو راه اساسی برای این کار شامل:
حذف گرهها: این روش شامل انتساب مقادیر به یکسری از متغیرهاست به نحوی که متغیرهای باقیمانده یک درخت را تشکیل دهند. به عنوان مثال در شکل زیر با انتساب یک مقدار به متغیر SA میتوان آن را از گراف ومقدار انتسابی به آن را از دامنه دیگر متغیرها حذف کرد و به این صورت یک ساختار درختی را پدید آورد.

شکل 1-5 کاهش گراف محدودیت به درخت توسط حذف گرهها [2]
تجزیه گراف محدودیت به چند زیرمسأله همبند: در این مدل هر زیر مسأله مستقلا حل میشود و سپس راه حلهای بدست آمده با هم ترکیب میشوند.

شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2]
شرایط لازم برای تجزیه گراف محدودیت به شرح زیر است:
– هر متغیر در گراف اصلی باید حداقل در یکی از مسائل آورده شده باشد.
– هر محدودیت در گراف اصلی (و متغیرهایش) باید حداقل در یکی از زیرمسائل آورده شده باشد.
– اگر یک متغیر در دو زیر مسأله در درخت آورده شود، آن متغیر باید در تمامی زیرمسائلی که در مسیر اتصال آن دو زیر مسأله قرار دارند نیز آورده شود.
سیستمهای چند عامله
برطبق [5] و [6]، به طور کلی یک عامل را میتوان به این صورت تعریف کرد: یک عامل، یک موجودیت فیزیکی یا مجازی است که اساسا دارای خصوصیات زیر است:
– قادر است در یک محیط زندگی یا عمل کند.
– میتواند محیط محلی را درک کند.
– با یک سری اهداف مشخص کار میکند.
– تا حدودی رفتارهای واکنش گرایانه دارد.
البته این تعریف برای عامل بسیار جامع است و آنچه که یک عامل ارائه میدهد برای مسائل مختلف متفاوت است.
هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار میکنند. به طور کلی چهار عنصر در هنگام معرفی سیستمهای چند عامله مطرح میشود تا مسأله حل شود: الف) معنی و هدف هر عامل، ب) محیطی که تمامی عاملها در آن زندگی میکنند، ج) تعریف محیط محلی با ذکر این نکته که عاملها تنها قدرت درک محیط محلی خود را دارند و د) رفتارهایی که هر عامل میتواند برای رسیدن به هدف انجام دهد [7].
حال اینکه چرا مهم است که سیستمهای چند عامله وجود داشته باشد؛ موقعیتهایی وجود دارد که در آن یک مسأله نیاز دارد در یک مد توزیع شده حل شود، یا به این دلیل که یک کنترل کننده مرکزی امکانپذیر نیست یا به این دلیل که میخواهد استفاده مناسبی از منابع توزیع شده داشته باشد. یک مثال خوب برای این موضوع شبکه های حسگر است. چنین شبکه هایی حاوی چندین واحد پردازشی، هر کدام با قابلیت یک حسگر محلی، با قدرت پردازش محدود، منبع تغذیه محدود (مثلا باطری) و ارتباط محدود بین آنهاست. علیرغم این محدودیتها، این شبکه ها هدفشان فراهم آوردن چند سرویس کلی است. شکل 1-7 یک شبکه حسگر برای تهویه هوای یک ساختمان را نشان میدهد. هر حسگر تنها میتواند ناحیه محلی خودش را مانیتور کند همچنین تنها میتواند با همسایه هایش ارتباط داشته باشد. سوأل این است که این تک حسگرها چه الگوریتمی باید اجرا کنند بطوریکه این قطعات با هم یک تصویر قابل اعتماد از کل را داشته باشند [4].

شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان [4]
حل مسائل CSP توسط سیستمهای چند عامله؛(DCSP)
وقتی یک مسأله قرار است توسط سیستمهای چند عامله حل شود فرم مسأله به یک حالت توزیع شده تبدیل میشود. مسأله ارضاء محدودیت توزیع شده حالت توزیع شدهی مسألهی ارضاء محدودیت کلاسیک است که پیش تر به طور کامل توصیف شد. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را حمل و کنترل میکنند. مسأله ارضاء محدودیت توزیع شده اولین بار توسط سیکارو، یوکو و همکارانشان به صورت رسمی مطرح شد [9] و [10]. به طور کلی یک مسأله ارضاء محدودیت توزیع شده شامل یک 4تایی مرتب P = <V, A, D, C > است که هر جزء آن به صورت زیر تعریف میشود:
یک مجموعه متناهی از n متغیر، {V = {x1, x2, …, xn؛
یک مجموعه متناهی از g عامل، {A = {a1, a2, …, ag؛
یک مجموعه دامنه D، شامل یک دامنه گسسته و متناهی برای هر متغیر:
D = {D1, D2, …, Dn} , Di = {d1, d2, . . ., d|Di| } for xi , i = 1, 2,. . . , n ;
یک مجموعه از محدودیتها، { C = {C1(x1 ), C2(x2 ), …, Cm(xm) ، که xi ، i=1, 2 , . . . , n ، زیرمجموعه ای از x است و Ci(xi) تعیین کننده مقادیری است که متغیرهای درون xi نمیتوانند به صورت همزمان به خود بگیرند. به عنوان مثال یک محدودیت به صورت 〈C({x1, x2}) = 〈d1, d2 بدین معنی است که وقتی x1= d1 آنگاه مقدار d2 نمیتواند به x2 انتساب یابد و زمانی که x2 = d2 است x1 نمیتواند مقدار d1 بگیرد.
هدف نهایی حل مسأله ارضاء محدودیت توزیع شده، مشابه مسأله ارضاء محدودیت استاندارد که پیشتر تعریف شد، هنوز یافتن مقادیری برای انتساب به متغیرهاست که کل محدودیت های موجود را ارضاء کند. یک الگوریتم خوب در این فیلد الگوریتمی است که تضمین میکند که یک پروسه با یک راه حل قانونی و در یک مدت زمان قابل قبول خاتمه مییابد و یا نشان دهد هیچ راه حل قانونی وجود ندارد. منظور از راه حل قانونی راه حلی است که به هر متغیر یک مقدار از مقادیر دامنه اش انتساب یافته باشد به طوریکه هیچ محدویتی از محدودیتهای تعریف شده در مسأله نقض نشده باشد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب میشود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر میباشد. هر عامل سعی میکند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. بسیاری از مسائل مطرح در دنیای واقعی و مسائل چند عاملی را میتوان تحت این مدل در نظر گرفت، که از جمله میتوان به مواردی نظیر زمانبندی توزیع شده [11]، مسائل انتساب منابع توزیع شده [12] و نگهداری واقعیات یا صحت چند عاملی [13]، اشاره کرد.
فصل دوم
مروری بر تحقیقات پیشین
مرور کلی
همانطورکه پیشتر گفته شد، تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حسگر بیسیم، کنترل علائم راهنمایی شهری، شبکه های حسگر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیرهای توزیع شده است. به عبارت دیگر هر مسألهای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است میتواند به عنوان DCSP طرح ریزی شود. با توجه به وسعت این دسته از مسائل، الگوریتمهای متنوعی برای حل آنها از سال 1991 تاکنون ارائه شده است. برخی از این الگوریتمها مانند الگوریتم عقب گرد نامتقارن (ABT) [14]، و الگوریتم الزام ضعیف نامتقارن (AWC) [15]، کاملا توزیع شده هستند در حالیکه برخی دیگر از ترکیب روشهای توزیع شده و متمرکز استفاده میکنند. یکی از موفق ترین الگوریتمهای مطرح در دسته دوم الگوریتم (APO) است که توسط میلر و لزر ارائه شده است[16]. با یک دید گسترده تر میتوان یک دسته بندی همانند شکل 2-1 را برای الگوریتمهای مسائل ارضاء محدودیت توزیع شده در نظر گرفت:
32575559055
شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP
به طور کلی الگوریتم هایی که برای حل DCSP وجود دارند میتواند به دو گروه تقسیم شوند: کامل و ناقص. الگوریتم های کامل، الگوریتم هایی هستند که یافتن راه حل را، البته اگر وجود داشته باشد، تضمین میکنند و یا وقتی که مسأله راه حلی ندارد از کار متوقف میشوند. الگوریتم های کامل خود به دو گروه تقسیم میشوند: روشهای کاملا توزیع شده و دوم ترکیب روشهای توزیع شده و متمرکز. الگوریتم های کاملا توزیع شده، الگوریتم هایی هستند که یک گره مرکزی ندارند. و هر گره نیز اطلاعات محدودی درباره محدودیتهایش دارد. در این گروه، عامل ها با هم هماهنگ میشوند تا مسأله را با استفاده از دانش محدودی که دربارهاش دارند حل کنند. یوکو و سایرین همکاری های مهمی در الگوریتم های کاملا توزیع شده داشتهاند. آنها الگوریتم عقبگرد نامتقارن را ایجاد کردند که کامل بودن را تضمین میکند[36-32]. بعدها این الگوریتم را به الگوریتم کارامدتری با نام الزام ضعیف نامتقارن، با معرفی ترتیب پویا در میان عاملها، گسترش دادند.
گروه دیگر الگوریتم های کامل، الگوریتم هایی هستند که در واقع از ترکیب روشهای توزیع شده و متمرکز استفاده میکنند. در این دسته الگوریتمها برخی عامل ها در تلاشند تا اطلاعاتی را از عامل های دیگر جمع آوری کنند تا مسأله را از بنیاد حل کنند و سپس اجازه دهند عامل های شرکت کننده مقادیری را که برای متغیرهایشان انتخاب شده است را بدانند. APO مثال خوبی برای این گروه از الگوریتم ها است. استفاده از درجه ای از متمرکز سازی به الگوریتم ها اجازه میدهد با پیامهای کمتری نسبت به الگوریتم های کاملا نامتمرکز مسأله را حل کنند. از سوی دیگر این متمرکز سازی آسنکرونی حل مسأله را کاهش میدهد. به عبارت دیگر همانطور که برخی از عامل ها اطلاعاتشان را به یال مرکزی میفرستند تا پردازش شود، بار محاسباتی به طور نامتقارنی بین عامل ها تقسیم میشود که منجر به کاهش دادن همزمانی پروسه حل مسأله میشود[31].
در چارت بالا یک طبقه بندی کلی از الگوریتم های اصلی در این زمینه را نشان دادهایم که در واقع میتوان گفت این چارت تقسیم بندی خوبی از الگوریتم هایDCSP بر اساس دو ویژگی مهم این الگوریتم ها یعنی کامل بودن و متمرکزسازی انجام میدهد.
میتوان گفت کامل بودن ویژگی بسیار مطلوبی است اما این ویژگی در مسائل ترکیبی دشوار، غیر قابل حل است. از اینرو، رویکردهای ناقص پیشنهاد شدهاند که جامعیت را کنار گذاشتهاند و سعی در پیدا کردن سریع راه حل نسبتا خوب به شیوه فرصت طلبانه نمودهاند. این شیوه ها معمولا از برخی توابع اکتشافی استفاده میکنند تا جست و جو را به سمت قسمتهای امید بخشتری از فضای جستجو بکشانند. الگوریتم انفجاری توزیع شده و الگوریتم احتمالی توزیع شده DSA مثالهای خوبی از الگوریتم های ناقص DCSP هستند. الگوریتم احتمالی توزیع شده، تکنیک تپه نوردی توزیع شده است که مشهورترین نسخه آن DSA–B است که با مجبور کردن عاملها به تغییر تخصیص هایشان با احتمال p عمل میکند. هم چنین ایده اولیه DSA این است که مکررا عاملها را وادار به بهبود همزمان مجموعه تخصیص های ناقص و موقت برای متغیرهایشان کنند، در حالی که چنین مجموعه های موقتی را تا زمانی که راه حلی برای نمونهای از مسائل ارضا محدودیت توزیع شده پیدا کنند به هم ارتباط میدهند.
از آنجا که CSP، پایه و اساس DCSP است، بسیاری از الگوریتمهای مطرح شده برای حل CSP نیز پایه الگوریتمهای مطرح برای حل DCSP هستند. مثلا الگوریتم عقبگرد نامتقارن نسخه توزیع شده الگوریتم عقبگرد است که قبلا توضیح داده شد، و یا الگوریتم الزام ضعیف نامتقارن نسخه توزیع شده الگوریتم الزام ضعیف متمرکز است که در ادامه توضیح خواهیم داد.
در الگوریتم ABT هر عامل یک مقدار تصادفی از مقادیر موجود در دامنه اش را به متغیرش منتسب میکند. از آنجا که در این الگوریتم هر عامل یک شماره الویت دارد، اگر مقدار منتسب به متغیر یک عامل با مقدار عاملهای با اولویت بالاترش سازگار نباشد عامل کم اولویتتر باید مقدارش را تغییر دهد. به زبان دیگر، در چنین شرایطی عامل کم اولویتتر تمام مقادیر ممکن برای انتساب به متغیرش را بررسی میکند و در صورت عدم وجود مقدار سازگاری، به عقب باز میگردد.
الگوریتم موفق دیگر، AWC است که بسیاری از خصوصیات ABT را به ارث میبرند اما از یک روش ابتکاری جدید به نام کمترین برخورد سود میبرد. با استفاده از این روش احتمال اتخاذ تصمیمات بد و انتخاب راه حل های نامناسب کاهش مییابد. کارآیی این دو الگوریتم با استفاده از انواع روشهای ابتکاری و هوشمند ارائه شده به سرعت بهبود یافته است.
در ادامه ابتدا چند نمونه از الگوريتم هاي جستجوي آسنکرون کاملا توزیع شده که در آنها هر عامل متناظر با يک متغير است و اين عاملها براي حل CSP به صورت آسنکرون عمل ميکنند، را توصيف ميکنیم سپس نمونهای از مدل ترکیبی توزیع شده و متمرکز را تشریح میکنیم. پس از آن نمونهای از تلاشهای موفق انجام شده در حل این نوع مسائل به صورت ترکیبی از روشهای توزیع شده و متمرکز و در پایان یکی از کارهای اخیرا انجام شده در این فیلد بر پایه الگوریتمهای ناقص را بررسی خواهیم کرد.
مدل ارتباطي زير را درنظر ميگيريم :
عاملها از طريق ارسال پيغام با هم ارتباط برقرار ميكنند.
تاخير دريافت پيغام، متناهي است.
بين هر جفت عامل پيغامها به ترتيب ارسال، دريافت ميشوند.
به علاوه عاملهایی که داراي اتصالاتي به xi هستند، همسايه xi ناميده ميشوند. فرض ميکنيم که هر متغير همسايگانش را ميشناسد.
الگوریتمهای هرس دامنه
تحت الگوریتمهای هرس دامنه عاملها به منظور حذف مقادیری از دامنه اشان با همسایههایشان ارتباط برقرار میکنند. ما به دو نمونه از این دسته الگوریتم به صورت مشروح اشاره میکنیم: الگوریتم تصفیه و فرا استدلال.
2-2-1- الگوریتم تصفیه
در این روش هر گره، دامنه اش را به همسایه اش اطلاع میدهد و سپس هر گره مقادیری از دامنهاش که با مقادیر دریافتی از همسایه اش سازگار نیست را حذف میکند و این روند تکرار میشود.
Procedur Revise(xi, xj)
Forall vi ϵ Di do
if there is no value vj ϵ Dj such that vi is consistent with vj then
Delete vi from Di
به طور خاص هر گره xi با دامنه Di به صورت مکرر روند Revise(xi,xj) را برای هر همسایه xj ، تکرار میکند. این پروسس زمانی خاتمه مییابد که هیچ حذف دیگری اتفاق نیفتد و یا تا زمانیکه دامنه یکی از متغیرها خالی شود (که در این مورد هیچ راه حلی برای این مسأله وجود ندارد). حال اگر الگوریتم با یک مقدار در هر دامنه خاتمه یابد، آنگاه مجموعهای از مقادیر تشکیل یک راه حل را میدهند و اگر با چند مقدار در هر دامنه خاتمه یابد نتیجه نامعلوم است. مسأله ممکن است یک راه حل داشته باشد یا نداشته باشد. به طور واضح، الگوریتم تضمین میکند که خاتمه پیدا میکند. و علاوه بر این قانونی است (یعنی اگر راه حلی را اعلام کند یا اعلام کند که راه حلی وجود ندارد، این درست است) اما کامل نیست (یعنی ممکن است راه حلی وجود داشته باشد اما پیدا نکند). شکل زیر 4 حالت مختلف از مسأله کلاسیک رنگ آمیزی گراف را نشان میدهد. نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل به شرح زیر است:

شکل 2-2 چهار حالت مختلف از مسأله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4]
(a در ابتدا متغیر x1 دامنه اش را به همسایگانش یعنی x2 و x3 ، با ارسال یک پیام، اطلاع میدهد. با دریافت پیام x2 و x3 مقدار red را از داخل دامنه اشان حذف میکنند. سپس x2 دامنه جدیدش را به x3 ارسال میکند. متعاقبا x3 مقدار blue را از دامنه اش حذف میکند. در این مرحله الگوریتم به دلیل عدم وقوع هیچ حذفی خاتمه مییابد در حالیکه یک راه حل صحیح یافته شده است.
(b الگوریتم به صورت مرحله قبل شروع میشود. اما زمانیکه x2 دامنه جدیدش را به x3 ارسال میکند، دامنه x3 خالی میشود. در این مرحله الگوریتم پایان مییابد در حالیکه به صورت صحیح اعلام میکند که مسأله هیچ راه حلی ندارد.
(c در این مورد ارسال پیام اولیه موجب هیچ حذفی در دامنه ها نمیشود. الگوریتم خاتمه مییابد در حالیکه همه متغیرها چند مقداره هستند. و همچنین الگوریتم نیز قادر نخواهد بود نشان دهد که مسأله راه حل ندارد.
(d در این حالت نیز الگوریتم تصفیه با شکست مواجه میشود در حالیکه مسأله راه حل دارد. بنا به همان دلیلی که در حالت c اتفاق افتاد باز هم الگوریتم قادر نخواهد بود نشان دهد که راه حلی وجود دارد.
به طور کلی الگوریتم تصفیه یک روش ضعیف است و بهتر است به عنوان یک مرحله پردازش برای متدهای پیچیده استفاده شود. این الگوریتم بر اساس قانون استدلال واحد سازماندهی شده است. قانون استدلال واحد به صورت زیر است( Ai عبارتي مانند x1=1 است و همانطور که میدانیم علامت ¬ در یک فرمول جبری به معنی نقیض و علامت ʌ به معنی “و” بکار برده میشود.):

استدلال واحد یک قانون استنباط ضعیف است. بنابراین عجیب نیست که الگوریتم تصفیه نیز ضعیف باشد.
الگوریتم فرا استدلال
در اين الگوريتم همه محدوديتها در قالب” گزارهء نادرست” نمايش داده ميشوند که ترکيب ممنوعي از مقادير متغيرهاست. با استفاده از گزارههاي نادرست موجود قانون فرا استدلال، گزارهء نادرست جديد را توليد ميکند. قانون فرا استدلال، گزارههاي نادرست قبلي و شرطي را که نشاندهنده مقدارگيري متغير از دامنهاش است با هم ترکيب مي کند و گزارهء نادرست جديد را ميسازد. اين قانون به شکل زير تعريف ميشود:

در اين الگوريتم هر عامل محدوديتهايش را در قالب گزارهء نادرست بيان ميكند. سپس عامل با تركيب اطلاعات دامنه خود و گزارههاي نادرست فعلي توسط قانون فرا استدلال، گزارههاي نادرست جديد را توليد کرده و به عاملهای مرتبط اطلاع ميدهد. با دريافت گزارهء نادرست جديد، عامل تلاش ميكند گزارههاي نادرست بيشتري توليد كند. به عبارتی در این الگوریتم هر عامل به صورت مکرر محدودیتهای جدیدی را برای همسایگانش تولید میکند و این محدودیتهای جدید را به همسایگانش اطلاع میدهد و همچنین دامنه خودش را بر اساس محدویتهای پاس شده از گراف همسایگانش هرس میکند. پس از دریافت یک تعداد متناهی پیام، هر عامل ارسال پیام را متوقف خواهد کرد و گزارهءهای نادرست را تولید میکند. این روش کامل است یعنی اگر راه حلی وجود داشته باشد حتما آن را پیدا خواهد کرد. مسأله راه حل خواهد داشت اگر در پایان هیچ عاملی گزارهء نادرست تهی تولید نکند. در واقع الگوریتم فرا استدلال مبتنی بر استخراج دانش است، هر عامل سعی میکند تمام مسأله را حل کند و دانشی را که استخراج میکند با بقیه به اشتراک میگذارد. در این روش هر عامل عاملهای دیگر را نیز در نظر میگیرد. در حالی که روش تصفیه مبتنی بر شکستن مسأله است و هر عامل تنها خودش را میبیند. روند کار این الگوریتم بر روی نمونه مثال c که در روش تصفیه ذکر شد به صورت زیر است:

الگوریتم فرا استدلال برای این مورد به این صورت عمل میکند: در ابتدا x1 ، چهار گزارهء نادرست را به صورت زیر نگه میدارد:
(x1=red , x2=red)
(x1=red , x3=red)
(x1=blue , x2=blue)
(x1=blue , x3=blue)
که این گزارهءهای نادرست به طور مستقیم از محدودیتهای شامل x1 استخراج میشوند. علاوه بر این x1 باید یکی از مقادیر درون دامنه اش را اختیار کند. بنابراین با استفاده از قانون فرا استدلال، x1 میتواند به صورت زیر نتیجه گیری کند:

بنابراین x1 یک گزارهء نادرست جدید به صورت (x2=red , x3=blue) میسازد. به طور مشابه x1، گزارهء نادرست دیگری هم به این فرم میسازد: (x2=blue , x3=red) .سپس x1 هر دو این گزارهءهای نادرست را به همسایگانش یعنی x2 و x3 ارسال میکند. x2 با استفاده از دامنه اش، و همچنین یکی از گزارهءهای نادرست موجود و یکی از گزارهءهای نادرست جدید به استنباط زیر میرسد:

اولین گزارهء نادرست بر اساس استنباط مرحله قبل و دومین گزارهء نادرست را x2 بر اساس اطلاعات مربوط به دامنه خودش میسازد. با استفاده از گزارهءهای نادرست های جدید از x1 و x2، میتوان گزارهءهای نادرستی به صورت (x3=red) را ساخت. این دو گزارهءهای نادرست تکی بهx3 ارسال میشوند و باعث میشوند x3 یک گزارهء نادرست تهی تولید کند و این اثبات میکند که مسأله هیچ راه حلی ندارد. این مثال اثبات میکند که الگوریتم فرا استدلال نسبت به روش تصفیه قویتر است. علاوه بر این همین مثال ضعفهای الگوریتم فرااستدلال را نیز نمایان میسازد. تعداد گزارهءهای نادرست های تولید شده میتواند به صورت غیرقابل مدیریت رشد کند. یا به عبارتی این الگوریتم پیچیدگی محاسباتی بالایی دارد و زمانی که تعداد عاملها زیاد باشد الگوریتم با شکست مواجه میشود چون باید تضمین شود که تمام واقعیتها استخراج میشود. تا به اینجا به این نتیجه رسیدیم که هیچکدام از این دو نوع استدلال پاسخگوی مسائل دنیای واقعی نیستند پس به همین دلیل به سراغ الگوریتمهای اکتشافی میرویم.
الگوریتمهای اکتشافی
همانطور که پیشتر گفته شد روشهای جستجوی عمومی قادرند با پاسخ دادن به سوالاتی از قبیل اینکه: متغیر بعدی که قراگرهت مقدار بگیرد کدام است؟ و یا مثلا مقداردهی متغیر جاری چه پیامدهایی برای سایر متغیرهای انتساب نیافته دارد؟، توابع اکتشافی مناسبی را جهت افزایش کارایی الگوریتمهای حل مسائل CSP پیشنهاد دهند. الگوریتم عقبگرد نامتقارن و الگوریتم الزام ضعیف نامتقارن دو نمونه از الگوریتمهای کلاسیک این دسته است که درآن عاملها در یک فرم توزیع شده به صورت موازی و غیرهمزمان به حل مساله میپردازند. در ادامه توصیفی از نحوه عملکرد این دو الگوریتم را خواهیم داشت.
الگوریتم عقبگرد نامتقارن
این الگوریتم در ابتدا یک ترتیب کلی برای عاملها فرض میکند یا به عبارتی عاملها اولویتبندی میشوند. هر محدودیت باینری توسط دو عامل شناخته میشود و در الگوریتم توسط عامل با اولویت پایینتر بین دو عامل چک میشود. در گراف محدودیت همیشه یک لینک از عامل با اولویت بالاتر به یک عامل با اولویت پایینتر وجود دارد. عاملها متغیرهایشان را مقداردهی میکنند (در ابتدا با یک مقدار تصادفی) و مقدار انتسابیاشان را برای عاملهایی که به آنها متصل هستند به صورت همزمان میفرستند. همه عاملها صبر میکنند تا تمامی پیغامها ارسال شود سپس به پیغامها پاسخ میدهند. حال هر عامل یک مقدار انتساب از عامل یا عاملهای با اولویت بالاتر دریافت کرده است که اینها در مکانی به نام “دیدگاه عامل” ذخیره میکند. سپس بررسی برای رسیدن به یک راه حل آغاز میشود. به طور کلی سه حالت ممکن است اتفاق بیفتد:
حالت اول: اینکه مقادیر دریافتی از همسایه های با اولویت بالاتر یک عامل، با مقدار فعلی آن عامل سازگار است. که در این صورت لازم نیست آن عامل کاری انجام دهد.
حالت دوم: اینکه مقادیر دریافتی از همسایه های با اولویت بالاتر یک عامل، با مقدار فعلی آن عامل سازگار نیست اما آن عامل میتواند مقدار دیگری را از دامنه اش انتخاب کند که با دیدگاه فعلیاش سازگار باشد. در این صورت آن مقدار جدید را انتخاب میکند و این مقدار را به همراه کل دیدگاهش یا به عبارتی کل دانشی را که تا الان کسب کرده به همسایگان با اولویت پایینترش اطلاع میدهد.
حالت سوم: اینکه مقادیر دریافتی از همسایه های با اولویت بالاتر یک عامل، با مقدار فعلی آن عامل سازگار نیست و آن عامل هم نمیتواند مقدار دیگری را از دامنهاش انتخاب کند که با دیدگاه فعلیاش سازگار باشد. در این صورت عامل جاری مقدار فعلیاش را حفظ میکند و بازمیگردد به عامل قبلی با پیغامی مبنی بر اینکه امکان تغییر مقدار انتساب برایش وجود ندارد که این کار با ارسال یک پیام گزارهء نادرست انجام میشود. عامل قبلی در واقع عاملی با پایینترین اولویت در لیست دیدگاه عامل جاری است. حال عامل جاری فرض میکند که آن عامل همسایه که پیغام گزارهءهای نادرست را دریافت کرده مقدارش را تغییر خواهد داد پس مقدار آن عامل را از دیدگاهش حذف میکند و تلاش برای یافتن یک مقدار جدید توسط عامل همسایه از سر گرفته میشود و این روند تا رسیدن به یک راه حل ادامه پیدا میکند.
در ادامه مثالی ساده از پیاده سازی این الگوریتم را بر روی مسأله کلاسیک 4وزیر را داریم:
در سیکل 1 هر عامل یک مقدار میگیرد و مقدارش را به عاملهای با اولویت پایینتر اعلام میکند.

شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسأله 4 وزیر. تمامی عاملها فعالند[4] .

شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسأله 4وزیر. عاملهای A2 ، A3 و A4 فعالند. گزارهء نادرست در این مرحله عبارت است از [4]:
A2 =1 → A3≠1 A1=1 ʌ .در سیکل 2 هر عامل سعی میکند مقداری را بیابد که با مقدار دیدگاهش سازگار باشد. عاملهای A2 و A3 موفق میشوند مقدار سازگار با دیدگاهشان را بیابند اما A4 قادر به پیدا کردن یک مقدار مناسب نیست پس یک پیغام گزارهء نادرست به صورت: A2 =1 → A3≠1 ʌ A1=1 به عامل A3 ارسال میکند. البته این در حالی است که دیدگاه عامل A4 هنوز به صورت: {A1=1, A2=1, A3=1} است و هنوز به روز رسانی های انجام شده بر روی عاملهای با اولویت بالاتر به عاملهای با اولویت پایینتر ارسال نشده است. پس از ارسال این پیغام A4 مقدار عامل A3 را با فرض اینکه A3 مقدارش را تغییر خواهد داد از داخل دیدگاهش حذف خواهد کرد و سپس یک تغییر انتساب مناسب با دیدگاه فعلیاش انجام میدهد.

شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسأله 4 وزیر. تنها عامل A3 فعال است. گزارهء نادرست در این مرحله عبارت است از[4]: A1=1→ A2≠ 3

شکل 2-6 سیکل 4 و 5 از الگوریتم ABT بر روی مسأله 4وزیر. A2 و A3 و A4 فعالند. گزارهء نادرست در این مرحله عبارت است از[4]:
A2 =4 → A3≠4 A1=1 ʌ .
شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسأله 4وزیر. تنها A4 فعال است. گزارهء نادرست در این مرحله عبارت است از[4]: A2 =4 → A3≠2 A1=1 ʌ .

شکل 2-8 سیکل 7 و 8 از الگوریتم ABT بر روی مسأله 4وزیر. A3 در سیکل اول فعال است و A2 در سیکل 2. گزارهء نادرست در این مرحله عبارت است از[4]: