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

اسلاید 2 :

هوش مصنوعی

اسلاید 3 :

موضوع
فصل سوم: حل مساله با جستجو

اسلاید 4 :

مسئله های خوش تعریف و راه حل ها
حالت شروع : که عامل از آنجا شروع میشود
توصیفی از فعالیت های ممکن عامل
مدل گذار یا مدل تغیر حالت
آزمون هدف:تعین میکند آیا حالت خاصی حالت هدف است یا خیر
هزینه ی مسیر: برای هر مسیر یک هزینه عددی در نظر می گیرد

اسلاید 5 :

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

اسلاید 6 :

مساله پیدا کردن مسیر

اسلاید 7 :

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

اسلاید 8 :

مساله های اسباب بازی
حالتها
8 حالت عامل در یکی از دو مکان است که هرکدام ممکن است کثیف باشند یا نباشند.
حالت شروع
هر حالتی می تواند به عنوان حالت اولیه طراحی شود
تابع مدل گذار یا تغیر حالت
حالتهای معتبری را تولید می کند که از 3 عملیات (Left, Right, Suck) ناشی می شود.
آزمون هدف
تمیز بودن تمام مربع ها
هزینه مسیر
هزینه هر مرحله 1 است. هزینه مسیر برابر تعداد مراحل در مسیر است

اسلاید 9 :

مساله های اسباب بازی
معمای 8 یا جورچین
حالتها مکان هر 8 خانه شماره دار
و خانه خالی را در یکی از 9 خانه مشخص می کند
حالت شروع
هر حالتی می تواند به عنوان حالت اولیه طراحی شود
فعالیت ها: ساده ترین فرموله کردن ، فعالیت ها را به صورت حرکت خانه ی خالی به چپ- راست –بالا یا پایین تعریف کند
مدل گذار یا تغیر حالت
حالتهای معتبری را تولید می کند که از چهار عمل به دست می آید (انتقال خانه خالی).
آزمون هدف
رسیدن به حالت هدف
هزینه مسیر
هزینه هر مرحله 1 است. هزینه مسیر برابر تعداد مراحل در مسیر است

اسلاید 10 :

مساله های اسباب بازی
مساله 8 وزیر
8 وزیر در صفحه شطرنج طوری قرار گیرند که هر وزیری وزیر دیگر را گارد ندهد
فرمول بندی: 1- افزایشی 2- حالت کامل
حالتها هر ترتیبی از 0 تا 8 وزیر در صفحه (افزایشی)
حالت شروع: هیچ وزیری در صفحه نیست
فعالیت:اضافه کردن وزیر به مربع خالی
مدل گذار یا تغیر حالت: وزیری را به خانه خالی اضافه می کند
آزمون هدف
8 وزیر در صفحه وجود دارند و هیچکدام به دیگری گارد نمی دهند

اسلاید 11 :

مساله های نمونه
مساله های دنیای واقعی
مساله مسیریابی:
مسیریابی در شبکه های رایانه ای
سیستم ها ی مسیر یابی داخل اتومبیل
سیستمهای برنامه ریزی مسافرت هوایی
مساله های توریستی ٬ مساله فروشنده دوره گرد
مساله طرح VLSI
هدایت روبات
خط تولید خودکار
طراحی پروتئین

اسلاید 12 :

جستجو برای جواب ها (راه حل ها)

اسلاید 13 :

زیر ساخت الگوریتم های جست و جو
.STATE.n حالتی در فضای حالت که گره متناظر با آن است.
PARENT.n.گره ای در درخت جستجو که این گره را تولید کرده است
n.ACTIONفعالیتی که به والد اعمال شد تا این گره تولید شود
n.PATH-COST هزینه مسیری از حالت اولیه به این گره که معمولا با g(n) نمایش داده می شود

اسلاید 14 :

ساختمان داده گره ها در درخت

اسلاید 15 :

ساختمان داده ی مناسب برای الگوریتم جست و جو
عملیات در صف:
EMPTY? (queue)
اگر هیچ عنصری در صف نباشد،مقداررا برمیگرداند
: POP (queue)
اولین عنصر صف را حذف میکندو آن را برمیگرداند
INSERT(element,queue)
عنصری را در صف قرار میدهدو صف جدید را بر میگرداند

اسلاید 16 :

اندازه گیری کارایی الگوریتم حل مساله
روشهای اندازه گیری کارایی الگوریتم حل مساله
کامل بودن: تضمین الگوریتم به پیدا کردن راه حل
بهینگی: ارائه راه حل بهینه
پیچیدگی زمانی: زمان لازم برای پیدا کردن راه حل
پیچیدگی فضا: حافظه مورد نیاز برای جستجو

اسلاید 17 :

اندازه گیری کارایی حل مساله
پیچیدگی بر حسب سه کمیت بیان می شود :
:bضریب انشعاب
:dعمق نزدیکترین گره هدف
:m حداکثر طول هر مسیر در فضای حالت
سنجش زمان بر حسب تعدا گره های تولید شده در حین جستجو
سنجش فضا بر حسب حداکثر گره های ذخیره شده در حافظه

اسلاید 18 :

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

اسلاید 19 :

جستجوی عرضی
ابتدا ریشه بسط داده می شود
سپس تمام جانشین های ریشه بسط داده می شوند و به همین ترتیب
بسط تمام گره های موجود در یک عمق درخت و سپس حرکت در عمق
پیچیدگی زمانی این الگوریتم O(bd+1) می باشد

اسلاید 20 :

جستجو با هزینه ی یکسان
همان جستجوی عرضی است که به جای بسط سطحی ترین گره، گره n را با کمترین هزینه مسیر بسط می دهد
اهمیت در کل هزینه مراحل است نه تعداد مراحل
تضمین کامل بودن: هزینه هر مرحله ≥ ε0< ε
شرط کافی برای بهینگی نیزمی باشد
پیچیدگی زمان و فضا O(b[C*/ε])
c* هزینه راه حل بهینه

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید