مسائل ارضای محدودیت


در این مطلب قصد داریم تا گونه ای مسائل را با نام مسائل ارضای محدودیت  بررسی نماییم. تفاوت اینگونه مسائل با مسائلی که تا کنون بررسی نموده ایم این است که در این مسائل مجموعه ای از محدودیت ها برای پاسخ Agent در نظر گرفته میشوند که باید توسط فانکشن تست هدف مورد تایید قرار گیرند. مثلا فرض بفرمایید که در یک نقشه فرضی قرار است از شهر A به شهر G  برویم. اگر مطالبی را که تا کنون ذکر کرده ایم مطالعه نموده باشید، سریعا با یکی از روش های جستجو خواهید توانست برنامه ای را بنویسید که با ترسیم یک درخت جستجو و پیمایش آن شما را از شهر A به شهر G  هدایت نماید. حال اگر برای پاسخ شما محدودیت هایی در نظر گرفته شود چه؟! آیا باز هم خواهید توانست با روش های قبلی این مسئله را به راحتی حل نمایید؟ مثلا فرض بفرمایید به شما بگوییم برای رسیدن به شهر G حق عبور از شهر های B و Q را ندارید! در اینجا  عملا پاسخ های منتهی به مقصد را محدود نموده ایم.

یکی از مثال های بسیار زیبا که برای اینگونه از مسائل وجود دارد مسئله معروف هشت وزیر میباشد. در مسئله هشت وزیر قصد داریم تا هشت مهره وزیر را در یک صفحه استاندارد شطرنج طوری بچینیم که هیچ یک از وزیر ها روی صفحه دیگری را مورد اصابت قرار ندهد. اگر بخواهیم به دید ساده به مسئله نگاه کنیم میتوانیم بگوییم “8 مهره وزیر را در یک صفحه شطرنج بچینید”. همانطور که واضح است تا این مرحله از مسئله میتوان به کمک یک درخت جستجو مهره ها را در صفحه شطرنج قرار داد! حال قسمت دوم را به قسمت اول اضافه میکنیم. “هیچ یک از وزیر ها هم دیگر را مورد اصابت قرار ندهند.” اضافه شدن قسمت دوم به مسئله فوق، ما را از حل ساده مسئله با استفاده از درخت جستجو محدود مینماید.

حل مسئله 8 وزیر با استفاد ه از مسائل ارضای محدودیت
حل مسئله 8 وزیر با استفاد ه از مسائل ارضای محدودیت

اما چگونه میتوان مسائل ارضای محدودیت را حل نمود؟

اولین قدیمی که برای حل اینگونه مسائل باید بردارید این است که وضعیت ها را به صروت فیلتر شده وارد فضای وضعیت خود نمایید! یعنی هنگامی که یک وضعیت جدید را از یک وضعیت موجود ایجاد مینماییم آن را مورد بررسی قرار دهیم که محدودیت های مورد نظر را نقض ننماید. این کار را میتوانید یک مرحله قبل از افزودن وضعیت های جدید به فضای وضعیت انجام دهید.

مثال : اگر من در وضعیت صفر فضای وضعیت، مهره وزیر را در سطر یکم و ستون یکم از صفحه شطرنج قرار دهم، نباید وضعیت هایی را که در انها مهره دوم در سطر یکم،  ستون یکم و یا در قطر منتهی به خانه یک و یک وجود دارند به فضای اضافه شوند.  زیرا با این کار محدودیت مسئله را نقض نموده ام و عملا وضعیتی که در آن وزیرها یک دیگر را هدف میگیرند را وارد فضای وضعیت نموده ام. پس، از درج این وضعیت اشتباه در فضای حالت جلوگیری مینمایم. اگر بخواهم کمی سیستماتیک تر این مسئله را توضیح دهم باید بگویم پس از قرار دادن مهره اول بر روی صفحه باید وضعیت های غیر قابل استفاده را مشخص نموده و از آنها به عنوان وضعیت های جدید استفاده نمینماییم. این عملیات آنقدر صورت خواهد گرفت تا به هدف اولیه مسئله یعنی چیدن تمامی 8 وزیر در صفحه شطرنج برسیم. با رعایت توضحیات بالا اگر تعداد وزیرها در صفحه شطرنج به  عدد 8 رسید عملا با حفظ محدودیت به هدف خود رسیده ایم.

One Comment

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.