تشریح توابع هیورستیک


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

مقایسه توابع هیورستیک برای یک پازل

همگی با پازل معروف 9 خانه ای آشنا هستیم. همانطور که میدانید این پازل دارای 9 خانه میباشد که یکی از آنها خالی و قابل جابجای است. برای حل پازل باید با مرتب کردن خانه ها آن را به شکل صحیح تبدیل نمود. در اینجا مجموعه Action های ما برابر با ‘بالا ، پایین ، چپ و راست میباشد’. حال اگر بخواهیم طبق تعاریفی که در مورد الگوریتم جستجوی حریصانه و یا A* داشته ایم پازل زیر را حل نماییم، اولین قدم استفاده از یک تابع هیورستیک مناسب میباشد. ممکن است دو نفر که به حل این مسئله مشغولند دو تابع هیورستیک متفاوت را برای حل مسئله پیشنهاد دهند. مثلا فرض بفرمایید.

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

h1=8

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

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

سوالی که باید به آن پاسخ دهیم این است که با توجه به این که هر دو تابع صحیح بوده و مقادیر درستی را باز میگرداند، کدامیک برای حل مسئله مناسب تر خواهد بو؟

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

 

تاثیر دقت توابع هیورستیک بر روی بازدهی الگوریتم جستجو

یکی از راه های بررسی کارامد بودن یک تابع هیورستیک ، فاکتور موثر انشعاب آن میباشد(b*). اگر تعداد کل وضعیت هایی که برای جستجوی یک پاسخ توسط الگوریتم A* تولید میشود برابر با N  و عمق پاسخ برابر با با d باشد، آنگاه b* فاکتور انشعابی میباشد که یک درخت یکنواخت (فاکتور انشعاب های یکسان) با عمق d میبایست داشته باشد که بتواند شامل N+1 وضعیت باشد.

N+1=1+b*+(b*^2)+….+(b*^d)

بر اساس همین تعریف اگر در درختی پاسخ در عمق 5 موجود باشد درحالی که تعداد وضعیت های ایجاد شده برابر با 52 باشد در این صورت فاکتور انشعاب موثر برابر با 1.92 خواهد بود. عدد فاکتور انشعاب موثر برای مسائل مختلف میتواند شامل مقادیر متفاوتی باشد با این حال مقدار آن برای مسائل سخت بطور منصفانه ای پایدار (تغییر شگرف نخواهد داشت ) است. پس بنابراین اندازه گیری آزمایشی و نمونه ای این عدد بر روی مجموعه ی کوچکی از مسائل میتواند راهنمای خوبی برای بررسی کلیت مفید بودن توابع هیورسیتک باشد. بر اساس این اندازه گیری ها  توابع هیورستیک اگر خوب طراحی شده باشند باید مقدار فاکتور انشعاب موثرشان نزدیک به عدد 1 باشد. چنین توابع هیورستیکی بطور منصفانه ای به الگوریتم جستجو این فرصت را میدهند که با هزینه محاسباتی قابل قبولی مسئله را حل نمایند. 

بطور کلی در کتاب راسل اثبات میشود که اگر دو تابع هیورستیک با نام های h1 و h2  موجود باشند، در صورتی که مقدار h2 از h1  بزرگتر باشد، h2 از h1  موثر تر است. (اثبات حذف شده)

if h2(n)>h1(n) then h2 dominates h1

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

بررسی و نمونه گیری از توابع هیورستیک و مقایسه آنها با روش های غیر آگاهانه
بررسی و نمونه گیری از توابع هیورستیک و مقایسه آنها با روش های غیر آگاهانه
2 Comments

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.