با بهره گرفتن از فرموله سازی مسائل CSP به صورت مسائل جستجو، می­توان از هر یک از الگوریتمهای جستجو برای حل این مسائل استفاده کرد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

از آنجایی که هر راه­حل یک انتساب کامل می­باشد بنابراین اگر مسأله ای دارای n متغیر باشد آنگاه راه حل در عمق n یافت خواهد شد و درخت جستجو نیز دارای عمق n می­باشد. با توجه به این جستجوی عمقی برای CSP ها مناسب­ترند. از آنجایی که مسیری که از طریق آن به هدف می­رسیم چندان اهمیتی ندارد بنابراین می­توانیم از فرموله سازی حالت کامل^[۱۶] استفاده کنیم که در آن هر حالت یک انتساب کامل می­باشد که ممکن است برخی از محدودیتها را ارضا نکند. از الگوریتمهای جستجوی محلی مانند تپه نوردی می­توان برای حل این مسائل استفاده نمود.

بهبود کارآیی الگوریتمهای جستجو توسط توابع اکتشافی
سیستم‌های پیچیده اجتماعی، تعداد زیادی از مسائلِ دارایِ طبیعتِ ترکیباتی را پیش روی ما قرار می‌دهند. مسیر کامیون‌های حمل‌ونقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید جایابی شوند، شبکه‌های ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابط‌های رادیویی می‌بایست دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازه‌های لازم بریده شوند؛ از این دست مسائل بی‌شمارند. تئوری پیچیدگی به ما می‌گوید که زمان حل مسائل ترکیباتی اغلب چندجمله‌ای نیستند. این مسائل در اندازه‌های کاربردی و عملی خود به قدری بزرگ هستند که نمی‌توان جواب بهینۀ آنها را در مدت زمان قابل پذیرش به دست آورد. با این وجود، این مسائل باید حل شوند و بنابراین چاره‌ای نیست که به جواب‌های زیر بهینه بسنده نمود؛ به گونه‌ای که دارای کیفیت قابل پذیرش بوده و در مدت زمان قابل پذیرش به دست آیند. چندین رویکرد برای طراحی جواب‌های با کیفیت قابل پذیرش تحت محدودیت زمانی قابل پذیرش پیشنهاد شده است.
الگوریتم‌هایی وجود دارند که می‌توانند یافتن جواب‌های خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آنها الگوریتم‌های تقریبی می‌گویند. الگوریتم‌های دیگری هستند که تضمین می‌دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به آنها الگوریتم‌های احتمالی گفته می‌شود. جدای از این دو دسته، می‌توان الگوریتم‌هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسأله مورد بررسی را به همراه داشته‌اند؛ به این الگوریتم‌ها، الگوریتم‌های اکتشافی گفته می‌شود.
توابع اکتشافی عبارتند از معیارها، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر. توابع اکتشافی نتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد.
خاصیت توابع اکتشافی خوب این است که ابزار ساده‌ای برای تشخیص خط مشی‌های بهتر ارائه دهند و در حالی که به صورت شرطی لازم، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌کنند اما اغلب به صورت شرط کافی این تضمین را فراهم ‌آورند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. توابع اکتشافی با بهره گرفتن از روش‌هایی که نیازمند ارزیابی‌های کمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارائه می‌نمایند، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود.
الگوریتمهای جستجو اغلب برای افزایش کارایی به دانش مرتبط با جهان مسأله نیاز دارند، اما مسائل CSP می­توانند بدون دانش وابسته به جهان مسأله به صورت کارایی حل شوند. روش های عمومی قادرند با پاسخ به سوالات زیر توابع اکتشافی عمومی مناسبی را جهت افزایش کارایی الگوریتمهای حل مسائل CSP پیشنهاد دهند:
متغیر بعدی که قرار است مقدار بگیرد کدام است؟^[۱۷]
مقدار گیری بر اساس چه ترتیبی انجام شود؟^[۱۸]
مقداردهی متغیر جاری چه پیامدهایی برای سایر متغیرهای انتساب نیافته دارد؟ ^[۱۹]
چگونه می­توان از تکرار مسیرهای منجر به شکست جلوگیری کرد؟^[۲۰]
برخی از این توابع اکتشافی عبارتند از:
تابع اکتشافی حداقل مقادیر باقیمانده(MRV^[21])
این تابع اکتشافی برای انتخاب متغیر بعدی که مقدار نگرفته است متغیری با کمترین مقادیر مجاز را انتخاب می­ کند. نامهای دیگر این تابع اکتشافی محدودترین متغیر^[۲۲] و اولین شکست^[۲۳] می­باشند. علت نامگذاری اولین شکست آن است که اینگونه متغیرها، به احتمال زیاد به زودی به حالت شکست خواهد رسید.
۲- تابع اکتشافی بالاترین درجه (MCO^[24])
اگر تمام دامنه ها دارای یک اندازه باشند، تابع اکتشافی MRV نخواهد توانست در انتخاب اول هیچ کمکی بکند. تابع اکتشافی بالاترین درجه متغیر داری بالاترین درجه محدودیت در مقایسه با سایر متغیرهای مقدار نگرفته را انتخاب می­ کند.
۳- تابع اکتشافی مقدار با حداقل محدودیت (LCV^[25])
پس از انتخاب متغیر، مقدار خاصی برای انتساب باید انتخاب شود. تابع اکتشافی مقدار با حداقل محدودیت، مقداری را برای یک متغیر انتخاب می­ کند که در گراف محدودیت باعث ایجاد کمترین محدودیت در متغیرهای مجاور گردد.
در شکل ۱-۳ عملکرد این توابع اکتشافی برای رنگ آمیزی نقشه ایالات و نواحی استرالیا به نحوی که هیچ دو ناحیه ای رنگ یکسان نداشته باشند نشان داده شده است.
(الف)
تابع اکتشافی LCV
تابع اکتشافی MRV
تابع اکتشافی درجه
(ب)
شکل ۱-۳ (الف) ایالات و نواحی استرالیا. رنگ آمیزی این نقشه می ­تواند به صورت مسأله ارضاء محدودیت نمایش داده شود. هدف انتساب رنگها به هر ناحیه است، چنانچه هیچ دو ناحیه همسایه ای رنگ یکسان نداشته باشند. قسمت (ب) نحوه عملکرد توابع اکتشافی مختلف بر روی این نقشه نشان می­دهد [۲] .

محدودیتهای ویژه
برخی از محدودیتها آنقدر زیاد در مسائل اتفاق می­افتند که می­توان آنها را به عنوان حالتهای خاص بررسی کرد.
محدودیت Alldiff : همه متغیرها بایستی مقادیر متفاوت داشته باشند. مسأله ۸-وزیر یا پازل ریاضیات رمزی از این دسته محدودیتها دارد.
به شکلی رسمی­تر می­توان محدودیت Alldiff را به صورت زیر تعریف کرد[۵۶]:
با داشتن یک مجموعه از متغیرهای X={x₁, x₂, . . . , x_n} با دامنه های D₁, . . . , D_n ، مجموعه ای از چندتایی های مجاز به وسیله Alldiff(X) عبارتند از:
{ (d₁, d₂, . . . , d_n) | d_i ϵ D_i , d_i ≠ d_j i ≠ j }
محدودیت Atmost یا Resource: مقدار همه متغیرها بایستی حداکثر یک مقدار مشخص باشد.

کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت
الگوریتمهای جستجوی محلی برای حل بسیاری از مسائل CSPبسیار موثرند. در این حالت از فرموله سازی حالت کامل استفاده می­ شود که در آن در ابتدا به هر متغیر حالت اولیه ای نسبت داده می­ شود و سپس در هر مرحله تابع مابعد مقدار یکی از متغیرها را تغییر می­دهد. به عنوان مثال در مسأله ۸-وزیر در ابتدا هر وزیر به تصادف درون یک ستون قرار می­گیرد و سپس تابع مابعد یک وزیر را انتخاب نموده و آن را به جای دیگری درون همان ستون منتقل می­ کند. در انتخاب یک مقدار جدید برای یک متغیر، تابع اکتشافی حداقل تناقض ها^[۲۶] بهترین اکتشاف می­باشد. این تابع همواره مقداری را انتخاب می­ کند که کمترین برخورد را با سایر متغیرها ایجاد می­ کند.

ساختار مسأله
منظور از ساختار مسأله در مسائل CSP نحوه بیان محدودیتهاست. پیچیدگی حل یک CSP به شدت وابسته به ساختار گراف محدودیت است. گاهی می­توان از ساختار مسأله به منظور شناخت سریع و آسان راه حل استفاده نمود. اصولا مسائل CSP به صورت گراف محدودیت بیان می­شوند که در موارد خاص می­توان این ساختار را تا حدودی ساده تر کرد، همانگونه که تنها راه برخورد با مسائل دشوار دنیای واقعی، تجزیه این مسائل به مسائل کوچکتر است. اولین راه برای این کار شناخت زیر مسأله های مستقل درگراف است. به عنوان مثال در شکل زیر T قسمتی مجزا از سایر متغیرهاست. به عبارتی رنگ آمیزی T و رنگ آمیزی سایر گرهها دو مسأله مستقل هستند پس هر جوابی برای T و هر جوابی برای سایر گرهها، در کنار هم جواب نهایی را تشکیل می­ دهند. متأسفانه این قبیل مسائل بسیار نادر هستند.
شکل ۱-۴ زیرمسأله های مستقل در گراف محدودیت[۲]