پاورپوینت  جستجو و کاوش آگاهانه

بخشی از پاورپوینت

اسلاید 1 :

فصل ۴ جستجو و کاوش آگاهانه

اسلاید 2 :

مقدمهای بر جستجوهای آگاهانه
جستجوهای اگاهانه یا مکاشفهای یا به قول  کتاب آروینی با تخمین فاصله هر گره تا گره هدف سعی میکند گرهی را بست دهد که احتمالا به گره هدف نزدیک تر است. اینکه میگوییم احتمالا به این دلیل است که دقیقا نمیدانیم فاصله واقعی هر گره تا گره هدف چقدر است بلکه یک تقریبی از این فاصله داریم که توسط تابعای به نام هیوریستیک یا تابع آروین بدست میاید:h(n) هر چه این تابع دقیقتر باشد روند جستجو سریعتر و بهینه تر است.

جستجوهای آگاهانه را جستجوهای اول بهترین نیز مینامند، چرا که سعی میکنند اول بهترین را گسترش دهند نه لزوماً بهترین را.

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

اسلاید 3 :

نقش رومانی به همراه تابع هوریستیک اش

اسلاید 4 :

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

اسلاید 5 :

بررسی الگوریتم حریصانه

اسلاید 6 :

چطور میتونم یک تابع هیوریستیک خوب و دقیقتر انتخاب کنم؟
اولا تابع هیوریستیک باید پذیرفتنی(قابل قبول) باشد یعنی برای هر گره تخمینی کمتر از فاصله واقعی آن گره تا هدف بزند
دوما بهترین تابع هیوریستیک آن است که تخمین دقیقتری داشته باشد، به عبارت دیگر تابع هوریستیک قابل قبولی که مقدار تخمینی آن نسبت به تمام توابع هیوریستیک دیگر بزرگتر باشد
در مثال نقشه رمانی آیا هیوریستیک پذیرفتنی است؟ بله چون تمامی هیوریستیکها کمتر از فاصله واقعی آنها تا هدف هستند، به عنوان  مثال به آراد توجه کنید!

اسلاید 7 :

چطور میتونم یک تابع هیوریستیک خوب و دقیقتر انتخاب کنم؟
انتخاب یک تابع هیوریستیک خوب برای هر مساله با مساله دیگر متفاوت است. به عنوان مثال برای مساله معمای ۸ دو تابع هیوریستیک بیان میکنیم!
1) تعداد مربع هایی که در جای خود قرار ندارند بدون در نظر گرفتن مربع خالی = H1() برای مثل زیر این مقدار برابر ۷ میشود
ادعا ی ما این است که حد اقل بعد از ۷ حرکت به جواب میرسیم

اسلاید 8 :

چطور میتونم یک تابع هیوریستیک خوب و دقیقتر انتخاب کنم؟
دومین تابع هیریستیک جمع تعداد حرکت افقی و عمودی هر مربع است برای اینکه به جای اصلی خود منتقل شود، (این فاصله را فاصله منهتن نیز میگویند)H2 () =
این مقدار برای شکل قبل برابر با ۱۴ میشود
H2 =3+3+2+0+1+2+2+1 =14
از انجایی که هزینهٔ واقعی مسیر حتما از ۲۰ مرحله بیشتر است (میدانیم جواب عموما در عمق ۲۰ است معمولا هزینه واقعای ۲۶ است) پس هر ۲ هیوریستیک پذیرفتنی هستند اما چون h2 > h1 پس تخمین دقیقتری میزند و جواب بهینه تری میدهد.
طبق این روش حد اقل بعد از ۱۴ حرکت به جواب میرسیم؛ کدام تخمین (هوریستیک) دقیق تر هست؟

اسلاید 9 :

جستجو A*
یک پیادهسازی دیگر از روش اولین بهترین است که برای هر گره تابع ارزیابی را به صورت f(n)بیان میکند:
f(n) = g(n) + h(n)
هزینه  رسیدن به گره n از آغازین =g(n)
تخمین فاصله nتا هدف =h(n)
در هر مرحله آن گره که کمترین مقدارf را دارد بست داده میشود.

اسلاید 10 :

جستجو A*

اسلاید 11 :

خودتان مقایسه کنید کدام بهینه است؟

اسلاید 12 :

دقت!
در شکل صفحه قبل دیدیم که fagaras هم گسترش پیدا کرد، (اگر تابع هیوریستیک دقیقتری داشتیم، هیچوقت fagaras بسط پیدا نمیکرد) 
  بنابرین اگر هیوریستیک قابل قبول باشد جستجوی درختی توسطA* حتما جواب بهینه را میدهد اما اینکه چه تعداد گره را بسط دهد بستگی دارد که چقدر تخمین دقیقی میزند (چقدرh(n) دقیق است)

اسلاید 13 :

قابل قبول بودن یا پذیرفتنی بودن
اگر تابع هیوریستیک دارای شرایط لازم باشد، آنگاهA* بهینه است )هیچ گاه مسیر بهینه را گم نمیکند(. A*که از   Tree Search استفاده میکند به شرطی بهینه است کهh (n) قابل قبول باشد. A* که از Graph Searchاستفاده میکند در صورتی بهینه است که h(n)سازگار یا یکنواخت باشد.

اسلاید 14 :

یکنوا یا سازگار بودن

اسلاید 15 :

A*یک تحلیل برای اثبات بهینه بودن
در الگوریتمA* وجودg(n) به ما کمک میکند که اگر حتا تخمینِ من[h(n)] خیلی دور از واقعیت بود، متوجه شوم که مسیرِ من اشتباه است.
14+0
11+1
15+1

اسلاید 16 :

یک نکته مهم
اگر ۲ تابع هوریستیک داشته باشم که هر ۲ قابل قبول باشند ولی دومی به اولی برتری داشته باشد، آیا میتوان گفت که دومی گره کمتری نسبت به اولی بسط میدهد؟ بله
آیا با استفاده از تابع هوریستیک دوم زمان اجرای الگوریتم کمتر میشود؟ لزوماً خیر!!! چون ممکن است محاسبه تابع هوریستیک دوم که دقیقتر از اولی است بسیار زمان بر باشد

اسلاید 17 :

کامل است اگر فاکتور انشعاب متناهی باشد حتی اگر
بهینه است اگر قابل قبول / سازگار باشد
حافظه زیادی مصرف میکند
نود زیاد میشمارد
h*(n)

اسلاید 18 :

مثال ۱
الگوریتمA* در گراف مقابل چه مسیری را تولید میکند؟ (اعداد روی  یالها هزینه واقعی هر یال و عدد داخل هر گره هزینه تخمینی آن گره تا گره هدف است)A گره شروع و Hگره هدف است فناوری اطلاعات ۸۳
1) ACGH 2)ACDJH 3)ABFGH 4)ABECDJH

اسلاید 19 :

تحلیل مساله
در مثال قبل آیا همهٔ h(n)ها قابل قبول بودند؟ بله؛ پس A* حتما جواب بهینه را به من میدهد یعنی گزینهٔ ۱ و ۲ و ۳ جواب نیستند چون راه حل بهینه را نمیدهند. اگر بخواهیم  مسیر صحیح را پیدا کنیم میتونیم درخت پیمایش را بکشیم

اسلاید 20 :

مثال ۲
۳ تابع هیوریستیک  h1,h2,h3 که هر ۳ قابل قبول هستند  برای حل مسالهای به روشA* پیشنهاد شده اند اگر هیچ کدام بر دیگری برتری نداشته باشند، بهترین انتخاب کدام هیوریستیک است؟ مکاترونیک ۸۳

h(n) = h1(n) × h2(n)× h3(n) (1
Max(h1(n) , h2(n), h3(n) ) (2
(3انتخاب تصادفی یکی از ۳ هوریستیک
h(n) = c1h1(n) + c2h2(n) + c3h3(n) , 0