1
حل مساله با جستجو در هوش مصنوعی
2
مسئله های خوش تعریف و راه حل ها
حالت شروع : که عامل از آنجا شروع میشود
توصیفی از فعالیت های ممکن عامل
مدل گذار یا مدل تغیر حالت
آزمون هدف:تعین میکند آیا حالت خاصی حالت هدف است یا خیر
هزینه ی مسیر: برای هر مسیر یک هزینه عددی در نظر می گیرد
3
فضای حالت: مجموعه ای از حالت هاست که از حالت اولیه می توان به آنها رسید. به صورت گراف نمایش داده می شود
حالتها: گره های گراف
فعالیتها: یال هال گراف
مسیر فضای حالت: دنباله ای از حالتها که توسط دنباله ای از فعالیتها به هم متصل می شوند.
4
مساله پیدا کردن مسیر
5
مساله های نمونه
مساله های اسباب بازی
تشریح و تمرین کردن بر روی روشهای مختلف حل مساله جهت مقایسه کارایی الگوریتمها
6
مساله های اسباب بازی
حالتها
8 حالت عامل در یکی از دو مکان است که هرکدام ممکن است کثیف باشند یا نباشند.
حالت شروع
هر حالتی می تواند به عنوان حالت اولیه طراحی شود
تابع مدل گذار یا تغیر حالت
حالتهای معتبری را تولید می کند که از 3 عملیات (Left, Right, Suck) ناشی می شود.
آزمون هدف
تمیز بودن تمام مربع ها
هزینه مسیر
هزینه هر مرحله 1 است. هزینه مسیر برابر تعداد مراحل در مسیر است
7
مساله های اسباب بازی
8
معمای 8 یا جورچین
حالتها مکان هر 8 خانه شماره دار
و خانه خالی را در یکی از 9 خانه مشخص می کند
حالت شروع
هر حالتی می تواند به عنوان حالت اولیه طراحی شود
فعالیت ها: ساده ترین فرموله کردن ، فعالیت ها را به صورت حرکت خانه ی خالی به چپ- راست –بالا یا پایین تعریف کند
مدل گذار یا تغیر حالت
حالتهای معتبری را تولید می کند که از چهار عمل به دست می آید (انتقال خانه خالی).
آزمون هدف
رسیدن به حالت هدف
هزینه مسیر
هزینه هر مرحله 1 است. هزینه مسیر برابر تعداد مراحل در مسیر است
مساله های اسباب بازی
مساله 8 وزیر
8 وزیر در صفحه شطرنج طوری قرار گیرند که هر وزیری وزیر دیگر را گارد ندهد
فرمول بندی: 1- افزایشی 2- حالت کامل
حالتها هر ترتیبی از 0 تا 8 وزیر در صفحه (افزایشی)
حالت شروع: هیچ وزیری در صفحه نیست
فعالیت:اضافه کردن وزیر به مربع خالی
مدل گذار یا تغیر حالت: وزیری را به خانه خالی اضافه می کند
آزمون هدف
8 وزیر در صفحه وجود دارند و هیچکدام به دیگری گارد نمی دهند
9
مساله های نمونه
مساله های دنیای واقعی
مساله مسیریابی:
مسیریابی در شبکه های رایانه ای
سیستم ها ی مسیر یابی داخل اتومبیل
سیستمهای برنامه ریزی مسافرت هوایی
مساله های توریستی ٬ مساله فروشنده دوره گرد
مساله طرح VLSI
هدایت روبات
خط تولید خودکار
طراحی پروتئین
10
جستجو برای جواب ها (راه حل ها)
11
زیر ساخت الگوریتم های جست و جو
.STATE.n حالتی در فضای حالت که گره متناظر با آن است.
PARENT.n.گره ای در درخت جستجو که این گره را تولید کرده است
n.ACTIONفعالیتی که به والد اعمال شد تا این گره تولید شود
n.PATH-COST هزینه مسیری از حالت اولیه به این گره که معمولا با g(n) نمایش داده می شود
12
13
ساختمان داده گره ها در درخت
ساختمان داده ی مناسب برای الگوریتم جست و جو
عملیات در صف:
EMPTY? (queue)
اگر هیچ عنصری در صف نباشد،مقداررا برمیگرداند
: POP (queue)
اولین عنصر صف را حذف میکندو آن را برمیگرداند
INSERT(element,queue)
عنصری را در صف قرار میدهدو صف جدید را بر میگرداند
14
اندازه گیری کارایی الگوریتم حل مساله
روشهای اندازه گیری کارایی الگوریتم حل مساله
کامل بودن: تضمین الگوریتم به پیدا کردن راه حل
بهینگی: ارائه راه حل بهینه
پیچیدگی زمانی: زمان لازم برای پیدا کردن راه حل
پیچیدگی فضا: حافظه مورد نیاز برای جستجو
15
اندازه گیری کارایی حل مساله
پیچیدگی بر حسب سه کمیت بیان می شود :
:bضریب انشعاب
:dعمق نزدیکترین گره هدف
:m حداکثر طول هر مسیر در فضای حالت
سنجش زمان بر حسب تعدا گره های تولید شده در حین جستجو
سنجش فضا بر حسب حداکثر گره های ذخیره شده در حافظه
16
راهبردهای جستجوی نا آگاهانه
جستجوی نا آگاهانه (جستجوی کور)
هیچ اطلاعاتی غیر از تعریف مساله در اختیار الگوریتم نیست.
تولید جانشین
تشخیص حالت هدف و غیر هدف
جستجوی آگاهانه (جستجوی اکتشافی)
توانایی مقایسه امیدبخش بودن حالت غیر هدف نسبت به حالت غیر هدف دیگر
17
جستجوی عرضی
ابتدا ریشه بسط داده می شود
سپس تمام جانشین های ریشه بسط داده می شوند و به همین ترتیب
بسط تمام گره های موجود در یک عمق درخت و سپس حرکت در عمق
پیچیدگی زمانی این الگوریتم O(bd+1) می باشد
18
جستجو با هزینه ی یکسان
همان جستجوی عرضی است که به جای بسط سطحی ترین گره، گره n را با کمترین هزینه مسیر بسط می دهد
اهمیت در کل هزینه مراحل است نه تعداد مراحل
تضمین کامل بودن: هزینه هر مرحله ≥ ε 0< ε
شرط کافی برای بهینگی نیزمی باشد
پیچیدگی زمان و فضا O(b[C*/ε])
c* هزینه راه حل بهینه
19
جستجوی عمقی
بسط عمیقترین گره در حاشیه فعلی درخت جستجو، تاجاییکه گره ها فاقد جانشین باشند
حذف این گره ها از حاشیه درخت
استفاده از صف LIFO (پشته)
کامل نیست
بهینه نیست
پیچیدگی زمان و فضا O (mb)
جستجوی عقبگرد (Backtracking)
پیچیدگی زمان و فضا O (m)
20
جستجوی عمقی
21
جستجوی عمقی محدود
حل مساله درختها نامحدود توسط جستجوی عمقی با عمق محدود l
اگر l<d باشد کامل نیست
اگر l>d باشد بهینه نیست
پیچیدگی زمانی O (bl)
پیچیدگی فضا O (bl)
22
جستجوی عمیق کننده تکراری
بهترین عمق محدود را می بابد
همانند جستجوی عرضی وقتی کامل است که ضریب انشعاب محدود
باشد
وقتی بهینه است که هزینه مسیر تابعی غیر نزولی از عمق گره باشد
پیچیدگی زمانی O (bd)
همانند جستجوی عمقی پیچیدگی فضا O (bd)
23
جستجوی عمیق کننده تکراری
24
25
جستجوی دوطرفه
جست و جوی دو طرفه وقتی موفق میشود که انشعابی از ”گره شروع“ به انشعابی از گره هدف برخورد کند
26
جستجوی دوطرفه
گره را قبل از بسط در حاشیه درخت دیگر جستجو می کند
پیچیدگی زمانی O (b d/2)
همانند جستجوی عمقی پیچیدگی فضا O (b d/2)
27
مقایسه راهبردهای جست و جوی نا آگاهانه
جست و جوی آگاهانه(ابتکاری)
جواب ها را نسبت به استراتژی ناآگاهانه با کارایی بیشتری پیدا می کند
جست و جوی“ اول – بهترین“ حریصانه:
این جست و جو گره ها را گره ها را فقط با استفاده از تابع ابتکاری f(n) = h(n) ارزیابی می کند
h(n) =هزینه ی تخمینی ارزان ترین مسیر با شروع از حالتی در گره n
در فضای حالت متناهی نیز کامل نیست که خیلی شبیه به جست و جو عمقی است.
28
مینیم کردن کل هزینه ی جواب: A* جست و جوی
این روش گره ها را با ترکیب زیر ارزیابی میکند
f(n) = g(n) + h(n)
هزینه ی رسیدن به گره g(n)
هزینه ی رسیدن از این گره به گره هدف h(n)
f(n) = n هزینه ی برآورد شده ی ارزان ترین جواب از طریق
29
شرایط بهینگی
قابل قبول بودن:
اولین شرط این است که h(n)یک ابتکار قابل قبول باشد یعنی هزینه ی رسیدن به هدف را هرگز زیاد برآورد نکند.
سازگاری :
تابع ابتکاری h(n) در صورتی سازگار است که برای هر گره nو هر پسین گره n´هزینه ی تخمینی رسیدن به گره هدف از گره n بیش از هزینه ی مرحله رسیدن به n´ به اضافه ی هزینه ی تخمینی رسیدن به هدف از گره n´ نباشد
h(n)≤c(n,a, n´)+ h(n´)
30
جست و جوی ابتکاری با حافظه محدود
برای کاهش حافظه مورد نیاز A* پذیرفتن ایده ی ”تعمیق تکراری ”در زمینه ی جست و جوی ابتکاری است که منجر به الگوریتم A* تعمیق تکراریIDA*) )میشود.
تفاوت عمده بین IDA* و تعمیق تکراری استاندارد این است که مقدار برش مورد استفاده به جای اینکه برابر با عمق باشد برابر با هزینه ی f با مقدار g+h) ) است .
31
جست و جوی بازگشتی اول – بهترین
یک الگوریتم ساده ی بازگشتی است که عملکرد ”جست و جوی اول – بهترین استاندارد“ را تقلید میکند ، ولی فقط از فضای خطی استفاده می کند.
32
یاد گیری برای جست و جو بهتر
روش انجام این کار مبتنی بر مفهومی به نام فضای حالت فرا سطحی است.
هر حالت در فضای حالت فراسطحی . حالت داخلی مربوط به یک برنامه را در
اختیار میگیرد که در یک“ فضای حالت سطح شئ“ جست و جو می شود
هدف این نوع یادگیری کاهش هزینه ی کل حل مسئله است که بین هزینه ی
محاسباتی و هزینه مسیر تعادل برقرار می کند
33
اثر دقت توابع ابتکاری روی کارآیی
یک روش مشخص کردن کیفیت توابع ابتکاری استفاده از ضریب انشعاب موثر به نام b*است .
اگر تعداد کل گره های تولید شده توسطA* برای یک مسئله ی خاص برابر با Nباشد و عمق جواب برابر باd باشد، آنگاه b*ضریب انشعابی است که یک درخت یکنواخت به عمقd باید داشته باشد تا گره های آن N+1باشد.
N+1=1+b*+(b*)2+…+(b*)d
34
تولید توابع ابتکاری قابل قبول ازمسئله های تعدیل شده
چون مسئله ی تعدیل شده یال هایی را به فضای حالت اضافه میکند هر جواب بهینه در مسئله ی اصلی جوابی برای مسئله ی تعدیل شده است ،اما اگر یال های اضافه شده میانبر هایی را ایجاد کند ممکن است مسئله ی تعدیل شده جواب های بهتری داشته باشد.
بنابراین هزینه ی جواب بهینه برای مسئله ی تعدیل شده ، برای مسئله ی اصلی یک ابتکار قابل قبول است
35
تولید توابع ابتکاری قابل قبول از زیر مسئله ها
توابع ابتکاری قابل قبول را میتوان از هزینه ی جواب مربوط به زیر مسئله های یک مسئله نیز بدست آورد.
هزینه ی مربوط به جواب بهینه ی این زیر مسئله ، کران پایین هزینه ی مسئله ی اصلی است.
هدف پایگاه داده ی الگو این است که برای هر نمونه از زیرمسئله ها ، هزینه این جواب های دقیق را ذخیره کند
36
یاد گیری تجربی توابع ابتکاری
روش های یادگیری قیاسی وقتی بهتر کار میکنند ، که به جای اینکه فقط با توصیف خام حالت سروکار داشته باشد ،مجهز به ویژگی هایی باشند که به پیشگویی مقدار حالت مربوط می شود.
37
نمونه سوالات
روش جست و جوی A* تحت چه شرایطی یافتن پاسخ بهینه را تضمین می کند؟
الف) اصولا روش های ابتکاری از جمله A* قادربه یافتن پاسخ بهینه نیستند.
ب) شرایط لازم برای اینکه روش A* یافتن پاسخ بهینه را تضمین کند به دامنه مسئله بستگی دارد.
ج) درصورتیکه تابع ابتکاری مورداستفاده فاصله وضعیت های مختلف تا وضعیت هدف را هرگز بیشتراز مقدارواقعی تخمین نزند.
د) درصورتی که تابع ابتکاری مورداستفاده فاصله وضعیت های مختلف تا وضعیت هدف را حداکثربه اندازه مقدارکوچک دلتا و بیشتر از مقدار واقعی تخمین بزند.
پاسخ
گزینه ج
38
نمونه سوالات
39
نمونه سوالات
نقطه ضعف روش *IDA در چیست ؟
الف)کامل بودن ب)دوباره کاری
ج)کارایی پایین د)مصرفه حافظه زیاد
پاسخ: گزینه(ب)
40
نمونه سوالات
الگوریتم A* درگراف مقابل کدام یک از مسیرهای زیر را بعنوان پاسخ می یابد؟(اعداد روی یال ها هزینه واقعی هر یال و اعداد داخل هر گره هزینه تخمینی آن گره تا گره ی هدف است.) A گره شروع Hگره هدف می باشد.
الف) A C G H ب)A C D J H
ج) A B F G H د) A B E C D J H
پاسخ: گزینه(د)
41
نمونه سوالات
42
نمونه سوالات
43
نمونه سوالات
در شکل داده شده فرض کنید هزینه هر یال بر روی آن و هزینه تخمینی هر گره تا هدف داخل دایره مربوط به گره نوشته شده است.ترتیب بسط گره ها تا رسیدن به هدف(ترتیب ورود به لیست open) توسط الگوریتم A*کدام است؟ (از چپ به راست)
الف ) A B C F G
ب ) A B C F G H
ج ) A B D E G
د ) A B C D E F G
پاسخ: گزینه(ب)
44
نمونه سوالات
مسیر یافت شده توسط الگوریتم جستجوی A*برای گراف مقابل چیست ؟
الف ) A B C F G
ب ) A C G
ج ) A B C G
د ) A B E G
پاسخ: گزینه(الف)
45
نمونه سوالات
46
نمونه سوالات
حاصل جستجوی SMA*در درخت مقابل یافتن کدام یک از مسیرهای زیر است ؟ فرض کنید برای این جستجو حداکثر 3 حافظه در اختیار دارید.هزینه هر عملکرد روی یال های مربوط و هزینه تخمینی تاهدف داخل دایره گره نوشته شده است .گره های I, D ,H هدف هستند.
الف) ABD
ب) ACH
ج)ABEI
د) SMA* قادر به حل این مسئله نیست.
پاسخ: گزینه (ب)
47
نمونه سوالات
48
نمونه سوالات
حاصل جستجو SMA*با حداکثر 3 خانه حافظه بر روی گراف مقابل چیست ؟(A هر گره شروع و F گره هدف است .اعداد روی یال ها هزینه مسیر و اعداد داخل گره ها هزینه تخمینی گره تا هدف است .ترتیب ملاقات فرزندان به ترتیب حروف الفبا است.)
الف) ACF
ب)ABF
ج) ACGF
د) SMA* قادر به حل این مسئله نیست.
پاسخ: گزینه(الف)
49
نمونه سوالات
کدام یک از جملات زیر صحیح نیست ؟
الف )اگر h(n) = g(n)باشد آنگاه جستجوی حریصانه معادل جستجو باهزینه یکنواخت میگردد.
ب ) نقطه ضعف عمده روش IDA*دوباره کاری آن است .
ج )روش های مکاشفه ای قادر به یافتن پاسخ بهینه نیستند.
د ) SMA*به شرط داشتن حافظه کافی کامل و بهینه است .
پاسخ: گزینه (ج)
50
نمونه سوالات
کدام یک ازعبارات زیر صحیح است ؟
الف )A*در بدترین حالت معادل اول بهترین می باشد .
ب )مشکل کمبود حافظه را می توان باروش BFSمرتفع نمود .
ج )اگر هیورستیک قابل قبول وسازگارباشدآنگاه A*بهینه است .
د )DFSهرگز رسیدن به جواب بهینه را تضمین نمیکند .
پاسخ: گزینه (ج)
51
نمونه سوالات
طول مسیر یافت شده توسط الگوریتم A*برای گراف زیر چیست ؟(اعداد داخل دایره ها مقادیر هیورستیک می باشند)
الف) 7
ب) 6
ج) 8
د) 5
پاسخ: گزینه(د)
52
نمونه سوالات
کدام یک ازعبارات زیر صحیح است ؟
الف )هیچ الگوریتم بهینه دیگری تضمین نمیکند که نودهای کمتری نسبت به A* گسترش می دهد.
ب ) شرط رشد نمایی تعداد نودها در روش A*عبارت است از :
h(n) –h*(n) <O(log h*(n))
ج )الگوریتم های جستجوی محلی علاوه بر یافتن هدف برای پیدا کردن راه حل بهینه نیز مناسب هستند .
د )تپه نوردی برخلاف جستجوی حریصانه دارای آینده نگری است .
پاسخ: گزینه(الف)
53
نمونه سوالات
کدام یک از روش های زیر جزوروش های ضعیف به شمار می رود ؟
الف)A* ب)SMA* ج)BFS د) DFS
پاسخ: گزینه (ج)
54
با تشکر از توجه شما