در این تحقیق به مسائل ارضاء محدودیت توزیع شده پرداخته می شود که در آن عاملها در یک مد توزیع شده برای یافتن یک راه حل ممکن برای مسأله تلاش می کنند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
مسأله ارضاء محدودیت
تعریف مسأله ارضاء محدودیت
به عنوان یک تعریف رسمی، یک CSP را میتوان با سه جزء اصلی آن تعریف کرد[۳]:
یک مجموعه متناهی از متغیرها ، {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 = {۱, ۲, ۳}, 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>}
تمام راه حلهای ممکن برای مسأله ای که به صورت بالا توصیف شده است عبارت است از: 〈〈۱,۲,۲ ، 〈〈۱,۲,۳ ، 〈〈۲,۲,۲ ، 〈〈۲,۳,۲ ، 〈〈۳,۲,۲ .
به بیانی سادهتر، یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکان پذیر نیست. شکل ۱-۱ مثالی ساده از یک مسأله CSP را نشان میدهد که دارای سه متغیر x1, x2, x3 و محدودیتهای x1<>x3 و x2<>x3 است.
شکل ۱-۱ مثالی از مسأله CSP [4]
همانطور که گفته شد بسیاری از مسائل دنیای واقعی می تواند برای حل شدن به صورت یک مسأله CSP فرموله شوند. شکل ۱-۲ یک طرح جامع از به کار بردن تکنیک ارضاء محدودیت برای حل مسائل را نشان میدهد. با داشتن یک توصیفی از مسأله یک راه برای تعیین اینکه چگونه این مسأله می تواند توسط تکنیک ارضاء محدودیت حل شود تعریف سه جزء: متغیرها، دامنه متغیرها و محدودیتهاست. اگر بتوان این سه جزء را برای مسأله تعریف کرد این مسأله می تواند توسط تکنیکهای ارضاء محدودیت حل شود [۵۴].
شکل ۱-۲ یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [۵۴]
الگوریتمهای کلاسیک مسائل ارضاء محدودیت
به طور کلی ۴ الگوریتم به عنوان الگویتمهای کلاسیک حل مسائل CSP معرفی شده است [۱]:
الگوریتم بازگشت به عقب (BT[9])، الگوریتم عمیق شونده تکراری (IB[10])، الگوریتم بررسی رو به جلو (FC[11])، الگوریتم پرش رو به عقب (BJ[12]).
این الگوریتمها از ساختار درختی برای نشان دادن حالت فعلی جستجو استفاده می کنند. هریک از گره های درخت می تواند به عنوان یک راه حل جزئی[۱۳] در نظر گرفته شود. به طور همزمان مقادیر برخی از متغیرها از هر گره توسط یک لایه گره تصمیم گیری والد شناسایی می شود، این متغیرها متغیرهای گذشته نامیده میشوند. در مقابل متغیرهای گذشته متغیرهای آینده هستند که مقدار متغیرشان در یک گره انتخاب نشده است و مقدار این متغیرها ممکن است در یک زمان بعد تعیین شود. علاوه بر این متغیرهای جاری نیز داریم که در واقع همان متغیرهایی هستند که در حال حاضر در نظر گرفته شده اند. شاخه های درخت مقادیر ممکن متغیرهاست. بعد از انتخاب یک شاخه در درخت الگوریتم یک مقدار را به متغیر انتساب خواهد داد و توسط راه حل یافته شده تا اینجا مقادیر ناسازگار را از محدوده مقادیر متغیرهای آینده حذف خواهد کرد. چند الگوریتم بالا در نحوه برخورد با متغیر های آینده متفاوت هستند.
الگوریتم BT
هر گره یک مقدار برای آن متغیر که در حال مقایسه با راه حل جزئی جاری است، مشخص خواهد کرد. اگر محدودیتی نقض شد یا برخوردی با مقادیر متغیرهای گذشته داشت آنگاه برای مقدار دیگری برای آن متغیر جستجو می شود. زمانی که تمامی مقادیر در محدوده جاری جستجو شد اگرهیچ مقداری برای آن متغیر یافت نشود که با مقادیر متغیرهای گذشته در تناقض نباشد آنگاه الگوریتم به متغیر قبلی باز خواهد گشت تا مقداری دیگر از محدوده آن متغیر را بیابد. اگر هر متغیر مقداری از محدوده اش را به خود بگیرد در حالیکه هیچ محدودیتی نقض نشده است این الگوریتم خاتمه خواهد یافت.
الگوریتم IB
این الگوریتم اساسا یک الگوریتم جستجوی اول- عمق است با یک مقدار آستانهb . اگر B مجموعه آستانه جاری باشد و یک گره از درخت جستجو یا یک متغیر b بار ملاقات شده باشد آنگاه به زیر-گرههایی که ممکن است نادیده گرفته شوند دسترسی پیدا نخواهد کرد. اگر در این محدوده راه حلی پیدا نشود مقدار آستانه رفته رفته افزایش مییابد. اما اگر یک راه حل یافته شود یا مقدار آستانه b بزرگتر مساوی بزرگترین تعداد شاخه های درخت جستجو باشد این الگوریتم ممکن است خاتمه یابد.
الگوریتم FC
فرایند الگوریتم FC اساسا مشابه الگوریتم بازگشت به عقب است با این تفاوت که در این الگوریتم هر بار که برای یک متغیر عملیات انتساب انجام می شود الگوریتم FC تعدادی از مقادیر ناسازگار با مقدار متغیر جاری را از دامنه مقادیر دیگر متغیرها حذف می کند. اگر دامنه ای خالی شود مقدار انتسابی به متغیر جاری رد خواهد شد؛ در غیر اینصورت، الگوریتم FC این روند را برای دیگر متغیرها ادامه خواهد داد تا زمانی که به همه متغیرها مقداری انتساب یابد. اگر متغیر جاری همه مقادیرش رد شود عملیات بازگشت به عقب به متغیر قبلی انجام می شود. اگر هیچ متغیری برای بازگشت به عقبی وجود نداشته باشد مسأله غیر قابل حل است.
الگوریتمBJ
تنها تفاوت بین الگوریتم BT و BJ فرایند بازگشت به عقب آنهاست، مابقی دو الگوریتم یکسان است. وقتی نیاز به بازگشت به عقب باشد الگوریتم BJ به دنبال متغیرهایی خواهد گشت که باعث شکست شده اند. اگر هر مقدار از دامنه متغیر فعلی با مقدار متغیر های قبلی برخورد داشته باشد الگوریتم به نزدیکترین متغیری که باعث شکست شده است به عقب باز خواهد گشت نه اینکه تنها به متغیر قبلی برگردد. به عبارت دیگر این الگوریتم از روشی هوشمند در زمان بازگشت به عقب استفاده خواهد کرد. در این روش مجموعه ای داریم به نام مجموعه برخورد[۱۴]، مجموعه برخورد متغیر x شامل همه متغیرهایی است که قبلا مقدار گرفته اند و در گراف محدودیت به x متصل شده اند. حال اگر در زمان حل مسأله نیاز به عقب گرد باشد، الگوریتم به آخرین گره از مجموعه برخورد آن متغیری که در آن به شکست رسیده است برمیگردد، یعنی به متغیری از آن مجموعه که نسبت به سایر اعضای مجموعه دیرتر مقداردهی شده است.
CSP به عنوان یک مسأله جستجو
یک مسأله CSP را میتوان توسط فرموله سازی افزایشی[۱۵] به صورت یک مسأله جستجوی استاندارد ارائه کرد [۲]. برای این کار داریم:
حالت اولیه: انتساب تهی، که در آن هیچ متغیری مقدار ندارد.
تابع مابعد: انتساب یک مقدار به یکی از متغیرهای بدون مقدار. این مقداردهی بایستی به صورتی باشد که هیچ یک از محدودیت ها را نقض نکند.
آزمون هدف: آیا انتساب فعلی انتساب کاملی است؟
هزینه مسیر: یک هزینه ثابت برای هر مرحله در نظر گرفته می شود.
