سال انتشار: ۱۳۸۶

محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۸

نویسنده(ها):

سمانه حسینی سمنانی – دانشجوی دکتری گروه کامپیوتر، دانشگاه اصفهان، اصفهان، ایران
کامران زمانی فر – استادیار گروه کامپیوتر، دانشگاه اصفهان، اصفهان، ایران

چکیده:

مسائل ارضاء محدودیت توزیع شده (DCSPs) گروه وسیعی از مسائل مطرح در دنیای واقعی را پوشش می دهند . این مسئله،DCSPرا به زمینة مهمی از تحقیقات تبدیل میکند. با در نظر گرفتن
کلیة تلاشهائی که اخیراً برای حل این دسته از مسائل انجام شده استمیتوان الگوریتمرا Asynchronous Partial Overlay (APO)به عنوان یکی از موفقترین این تلاشها برشمرد. این الگوریتم برای حل یک مسئلة ارضاء محدودیت ابتدا آن را به بخشهای کوچکتری تقسیم میکند و سپس با انتخاب عاملهائی به عنوان عامل واسط سعی در حل متمرکز زیر مسئلههای تولید شده دارد. این مقاله روش جدید و مؤثری را برای انتخاب این عاملهای واسط معرفی میکند. به علاوه دو نسخة گسترش یافته از الگوریتم،APO به نام های MaxCAPO و MaxCIAPOکه از این استراتژی استفاده میکنند ارائه خواهند شد .
ایدة اصلی مطر ح در این استراتژی این است که تعداد تناقضات (محدودیتهای نقض شده) مرتبط با عاملهای واسط تأثیر مستقیم بر کارآئی آن دارد. نتایج تجربی نشان میدهد که انتخاب عاملهای واسط
از میان عاملهائی که بیشترین تعداد تناقضات را دارند نه تنها منجر به کاهش قابل توجهی در پیچیدگی الگوریتمAPO میشود، بلکه میتواند منجر به کاهش پیچیدگی الگوریتم های مشتق شده از،APO نظیر IAPOنیز بشود.