ساخت توابع هیورستیک


در مطلب قبل که پیشنیاز مطالعه این مطلب میباشد بطور کامل به تشریح مفاهیم باقیمانده از توابع هیورستیک پرداختیم. در این مطلب قصد داریم تا شما را با نحوه ساخت این توابع آشنا سازیم. اما قبل از شروع به این کار لازم است که یک بار دیگر به سراغ مسئله معروف پازل 9 خانه ای برویم.

ساخت توابع هیورستیک

فرض کنید که میخواهیم پازل فوق را حل نماییم. در مطلب قبل توضیح دادیم که دو شخص ممکن است دو تابع هیورستیک متفاوت را برای حل این مسئله ارائه دهند. همچنین توضیح دادیم که معیار انتخاب بین دو تابع هیورستیک از نظر بازدهی چیست. اما سوالی که پاسخ ندادیم این است که این دو نفر چگونه این دو تابع  هیورستیک را ساخته اند؟ براستی برای ساخت توابع هیورستیک چه کار باید کرد؟

  • اگر یادتان باشد گفتیم که نفر اول فرض کرده که حداقل فاصله وضعیت فعلی پازل با وضعیت نهایی برابر است با عدد 8. زیرا نفر اول با خود فرض کرده است از آنجا که هر 8 خانه در جایگاه اشتباهی قرار دارند و هر خانه حداقل باید یک جابجایی بمنظور رسیدن به وضعیت هدف داشته باشد، نتیجتا مقدار تابع هیورستیک را برابر با 8 در نظر گرفته است. h1=8
  • از طرفی نفر دوم مجموع کل حداقل تعداد حرکاتی که محره ها باید در این وضعیت انجام دهند تا به وضعیت هدف برسند را به عنوان مقدار تابع هیورستیک در نظر گرفته است.

h2=3+1+2+2+3+2+2+3=18

سوال : این دو تابع هیورستیک از کجا بدست آمده اند ؟ پاسخ در نحوه ساخت توابع هیورستیک با استفاده از مسئله ساده شده میباشد.

ساخت توابع هیورستیک با استفاده از مسئله ساده شده

همانطور که بارها و بارها گفته ایم تعریف تابع هیورستیک برابر است با تخمین کمترین فاصله ممکن از وضعیت فعلی تا وضعیت هدف. برای دو تابع h1  و h2 که در بالا به شرح آنها پرداختیم نه تنها تعریف هیورستیک نهفته است بلکه این دو تابع در واقع بطور دقیقی برابر با فاصله وضعیت فعلی با وضعیت هدف در مسائل ساده شده میباشند. اما یک مسئله ساده شده به چه معناست؟ با دقت به تعریف توابع فوق توجه کنید. اگر قوانین بازی پازل 9 خانه ای به نحوی تغییر داده میشد که هر مهره میتوانست نه تنها به خانه خالی مجاور خود، بلکه به هر نقطه دلخواه برود (در اینجا مسئله را ساده کرده و محدودیت های بازی را از میان برداشته ایم) آنگاه تابع h1 بدست می آمد. یعنی هر مهره با یک جا بجایی در جایگاه درست قرار میگرفت. از طرفی اگر قوانین بازی را به گونه ای تغییر میدادیم که هر مهره در جهات مختلف به هر خانه حتی خانه های اشغال شده میتوانست حرکت کند آنگاه تابع h2 را  بدست میاوردیم. به مسئله ای که از حذف محدودیت های مسئله اصلی ایجاد میشود مسئله ساده شده میگویند. گراف فضای حالت ناشی از مسئله ساده شده سوپرگراف مسئله اصلی میباشد. (گراف فضای وضعیت مسئله ساده شده بزرگتر از گراف فضای وضعیت  مسئله اصلی میباشد) زیرا طبیعتا حذف محدودیت های مسئله اصلی یال های بیشتری را به گراف فضای حالت اضافه مینماید. (توانایی انجام حرکات بیشتری در پازل را داریم!) پس چون گراف فضای حالت مسئله ساده شده بزرگتر از فضای حالت مسئله اصلی میباشد، هر راه حل بهینه در مسئله اصلی،  یک راه حل در مسئله ساده شده نیز میباشد اما طبیعتا مسئله ساده شده میتواند راه حل های بهینه تری داشته باشد زیرا که یال های اضافه شده به گراف راه های میانبری را به این فضای وضعیت اضافه نمایند. از این رو هزینه یک مسیر بهینه در مسئله ساده شده میتواند یک تابع هیورستیک قابل قبول برای مسئله اصلی باشد. 

ساخت توابع هیورستیک در مثال فوق

ابتدا مسئله اصلی را به زبانی ساده مینویسیم.

  • A tile can move from square A to square B if
    A is horizontally or vertically adjacent to B and B is blank,

سپس برای رسیدن به مسئله های ساده تر شروع به حذف محدودیت های مسئله مینماییم.

  • A tile can move from square A to square B if A is adjacent to B. → h2
  • A tile can move from square A to square B. → h1

 

ساخت توابع هیورستیک با استفاده از زیر مسئله یا  پایگاه داده الگو

یکی از راه های ساخت توابع هیورستیک، استفاده از زیر مسئله های یک مسئله میباشد. به شکل زیر دقت نمایید. هدف از این زیر مسئله مرتب کردن خانه های یک، دو، سه ، چهار و خانه خالی است و همانطور که میبینید چهار خانه باقیمانده با مقدار Don’t care  پر شده اند و هر کدام از آنها میتوانند یکی از خانه های  پنج، شش، هفت و هشت را پر نمایند.  اما ارتباط این زیر مسئله با ساخت توابع هیورستیک چیست و چه کمکی میکند؟

ساخت توابع هیورستیک و پایگاه داده الگو
ساخت توابع هیورستیک و پایگاه داده الگو

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

دقت بفرمایید که انتخاب اعداد یک دو سه چهار کاملا به صورت اتفاقی بوده است و شما میتوانید الگوهای متفاوت دیگری را در نظر بگیرید. مثلا شما میتوانید الگوی پنج شش هفت هشت و یا هر الگوی دیگر را در نظر بگیرید. با هر کدام از این الگو ها میتوان یک تایع هیوریستیک قابل قبول را بدست آورد و حتی میتوان با روشی که از قبل توضح داده شده آنها را با یکدیگر ترکیب نموده (منظور از ترکیب این است که بین یک مجموعه از هیورستیک ها ماکزیمم آنها را استفاده نمود).

طبق گفته های کتاب راسل اینطور بنظر میرسد که استفاده از این مکانیزم برای بدست آوردن مقدار هیورستیک بسیار دقیق تر از روش قبل که در همین پست توضیح داده شده است میباشد. راسل در واقع در کتاب خود ادعا مینماید که در پازل 15 خانه ای رَندمی که با این روش حل شده تعداد وضعیت های ایجاد شده در فضای حالت کاهش چشمگیری داشته است. این مسئله نشان میدهد که هیورستیک در این روش از روش قبل بسیار دقیقتر محاسبه شده.

ممکن است این سوال پیش بیاید که چون الگو های یک-دو-سه-چهار و پنج-شش-هفت-هشت  با یکدیگر همپوشانی ندارند آیا میتوان مقادیر هیورستیک آنها را بایکدیگر جمع نمود و به یک هیورستیک قابل قبول (تعریف قابل قبول بودن یک تابع هیورستیک در مطالب گذشته توضیح داده شده است) رسید؟ جواب این سوال منفی میباشد. دلیل هم آن است که راه حل هایی که برای این دو اولگو ارائه میشنود قطعا یکسری حرکات مشترک با یکدیگر خواهند داشت. قطعا برای رساندن یک دو سه چهار به محل دقیق خود باید خانه پنج شش هفت و هشت جابجا شوند (و برعکس) هر چند این جابجایی در ظاهر از چشم ما پنهان است. پس نتیجتا با جمع این دو مقدار هیورستیک نمیتوان به یک هیورستیک قابل قبول رسید. اما ← در صورتی که برای هزینه یک الگو تنها حرکات مرتبط با خانه های همان الگو را محاسبه کنیم اوضوع متفاوت خواهد بود. مثلا فرض بفرمایید در روش عقب گرد تنها هزینه جابجایی خانه های یک دو سه چهار را در هزینه مجموع محاسبه نموده و از هزینه حرکت دیگر خانه ها صرفنظر نماییم. اگر برای الگوی پنج شش هفت هشت نیز همین اصل را رعت نماییم آنگاه میتوانیم هیورستیک های بدست آمده از این دو الگو را بایکدیگر جمع نماییم که قطعا نتیجه آن یک هیورستیک بسیار دقیق تر و قابل قبول خواهد بود. به چنین روشی اصطلاحا disjoint pattern database و یا پایگاه داده الگوی مجزا میگویند. در کتاب راسل ادعا شده که  استفاده از چنین روشی میتواند تابع 15 خانه ای را در کمتر از چند میلی ثانیه حل نماید. نکته بسیار مهمی که باید به آن توجه نمود این است که از روش  پایگاه داده الگوی مجزا تنها در مسائلی میتوان استفاده نمود که هر حرکت در مسیر حل مسئله تنها بر روی یک زیر مسئله تاثیر گذار است. این در حالیست که در مسئله ای مثل مکعب روبیک چنین چیزی امکان پذیر نیست.

 

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.