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

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

اسلاید 1 :

هوش مصنوعی Artificial Intelligence

اسلاید 2 :

فصل چهارم: جستجوی آگاهانه و اکتشاف
راهبرد جستجوی آگاهانه از دانش مربوط به مساله استفاده می کند

اسلاید 3 :

اين راهبرد به اين صورت بيان ميشود که در يک درخت، زماني که گرهها مرتب ميشوند، گرهاي که بهترين ارزيابي را براساس یک تابع ارزیابی f(n) داشته باشد، قبل از ديگر گرهها بسط داده ميشود.

هدف: يافتن راهحلهاي کمهزينه است، اين الگوريتمها عموماً از تعدادي معيار تخمين براي هزينه راهحلها استفاده ميکنند و سعي بر حداقل کردن آنها دارند.
راهبرد جستجوي بهترين

اسلاید 4 :

جستجوي حريصانه
به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف.
بسط نزديکترین گره به هدف

تابع کشفکننده: هزينه رسيدن به هدف از يک حالت ويژه ميتواند تخمين زده شود اما دقيقاً تعيين نميشود. تابعي که چنين هزينههايي را محاسبه ميکند تابع کشفکننده h ناميده ميشود.
F(n) = h(n)
جستجوي حريصانه: جستجوي بهترين که h را به منظور انتخاب گره بعدي براي بسط استفاده ميکند، جستجوي حريصانه (greedy search) ناميده ميشود.

اسلاید 5 :

جستجوي حريصانه
روش اکتشافی فاصله خط مستقیمhSLD

اسلاید 6 :

جستجوي حريصانه

اسلاید 7 :

ويژگيهاي جستجوي حريصانه
جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف، مانند جستجوي عرضی است، اما زماني که به بنبست ميرسد، برميگردد.
اين جستجو بهينه نيست و ناکامل است.
پيچيدگي زماني در بدترين حالت براي جستجوي حريصانه O(bm)، که m حداکثر عمق فضاي جستجو است.
جستجوي حريصانه تمام گرهها را در حافظه نگه ميدارد، بنابراين پيچيدگي فضاي آن مشابه پيچيدگي زماني آن است.
ميزان کاهش پيچيدگي به مسئله و کيفيت تابع h بستگي دارد.

اسلاید 8 :

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

اسلاید 9 :

جستجوي A*

اسلاید 10 :

جستجوي A*

اسلاید 11 :

جستجوي A*
کشفکنندگي قابل قبول:
تابع hاي را که هزينهاي بيش از تخمين براي رسيدن به هدف نداشته باشد، يک کشفکنندگي قابل قبول (admissible heuristic) گويند.

جستجوي A*:
جستجوي بهترين که f به عنوان تابع ارزياب و يک تابع h قابل قبول استفاده ميکند، به عنوان جستجوي A* شناخته ميشود.

اسلاید 12 :

جستجوي A*
رفتار جستجوي A*

نگاهي گذرا به اثبات کامل و بهينه بودن A*:
مشاهده مقدماتي:
تقريباً تمام کشفکنندگيهاي مجاز داراي اين ويژگي هستند که در طول هر مسيري از ريشه، هزينه f هرگز کاهش پيدا نميکند.
اين خاصيت براي کشفکنندگي، خاصيت يکنوايي (monotonicity) گفته ميشود.
اگر يکنوا نباشد، با ايجاد يک اصلاح جزئي آن را يکنوا ميکنيم.

اسلاید 13 :

جستجوي A*
بنابراين هر گره جديدي که توليد ميشود، بايد کنترل کنيم که آيا هزينة f اين گره از هزينه f پدرش کمتر است يا خير. اگر کمتر باشد، هزينة f پدر به جاي فرزند مينشيند:

بنابراين:
f هميشه در طول هر مسيري از ريشه غيرکاهشي خواهد بود، مشروط بر اينکه h امکانپذير باشد.

A* معمولاً قبل از اينکه دچار کمبود زمان شود، دچار کمبود فضا ميشود. زيرا اين جستجو تمام گرههاي توليد شده را در حافظه ذخيره ميکند.

اسلاید 14 :

توابع اکتشافی
معماي 8 يکي از مسائل اوليه اکتشاف بود.
هدف: لغزاندن چهارخانهها به طور افقي يا عمودي به طرف فضاي خالي است تا زماني که ساختار کلي مطابق با هدف (goal) باشد. فاکتور انشعاب در حدود 3 است.
Start State
Goal State

اسلاید 15 :

توابع اکتشافی مربع 8
h1 = تعداد چهارخانههايي که در مکانهاي نادرست هستند. h1 قابل قبول است، زيرا واضح است که هر چهارخانهاي که خارج از مکان درست باشد حداقل يکبار بايد جابجا شود.

h2 = مجموع فواصل چهارخانهها از مکانهاي هدف صحيحشان است. مجموع فواصل عمودي و افقي است که بعضي وقتها city block distance و يا Manhattan distance ناميده ميشود h2 قابل قبول است، زيرا هر جابجایی که می تواند انجام پذیرد یک مرحله به هدف نزدیک می شود

اسلاید 16 :

توابع اکتشافی
Start State
Goal State
h1 = 8
h2 = 18
(3+1+2+2+2+3+3+2)

اسلاید 17 :

اثر دقت اکتشاف بر کارايي
يک راه براي تشخيص کيفيت اکتشاف فاکتور انشعاب مؤثر b* است. اگر مجموع تعداد گرههاي بسط داده شده توسط A* براي يک مسئله ويژه N باشد و عمق راه حل d، سپسb* فاکتور انشعابي است که يک درخت يکنواخت با عمق d خواهد داشت تا حاوی N+1 گره باشد. بنابراين:
N+1 = 1+ b*+( b*)2…+( b*)d

معمولاً فاکتور انشعاب مؤثر که توسط اکتشاف نمايش داده ميشود، مقدار ثابتي دارد.
/ طراحي شده، b* در حدود 1 دارد.

اسلاید 18 :

مقایسه هزینه جستجو و فاکتور انشعاب موثر

اسلاید 19 :

ابداع توابع اکتشافی قابل قبول
مساله راحت (Relaxed problem): مساله ای که فعالیتهایش محدودیتهای کمتری داشته باشد.
هزینه حل بهینه مساله راحت، اکتشاف قابل قبولی برای مساله است.
فعالیتهای معمای 8
کاشی می تواند از مربع A به مربع B حرکت کند
اگر A همجوار افقی یا عمودی B باشد و B خالی باشد.

مساله های راحت:
الف: کاشی می تواند از مربع A به مربع B منتقل شود اگر A همجوار B باشد
ب: کاشی می تواند از مربع A به مربع B منتقل شود اگر B خالی باشد
پ: کاشی می تواند از مربع A به مربع B منتقل شود

اسلاید 20 :

بهترين راه براي فهم الگوريتمهاي اصلاح تکراري درنظر داشتن تمام حالاتي است که روي سطح يک دورنمايي در معرض ديد قرار داده شده است. ارتفاع هر نقطه در دورنما مطابق با تابع ارزياب حالت آن نقطه است. ايده اصلاح تکراري، حرکت کردن در اطراف دورنما و سعي بر يافتن قلههاي مرتفع است، که همانا راهحلهاي بهينه هستند.
الگوريتمهاي اصلاح تکراري معمولاً اثر حالت جاري را فقط حفظ ميکنند، و توجهي فراتر از همسايگي آن حالت ندارند.
الگوريتمهاي اصلاح تکراري