نکات تستی کنکور هوش مصنوعی - حل مساله با جستجو

هزینه حل مساله = هزینه جستجوی راه حل + هزینه اجرای راه حل

معیارهای ارزیابی الگوریتمهای جستجو: کامل بودن. بهینه بودن . پیچیدگی زمانی. پیچیدگی فضایی.

راهبردهای ناآگاهانه : جستجوی سطحی BFS. الگوریتم جستجوی هزینه یکنواخت UCS. الگوریتم جستجوی عمقی DFS. جستجوی حداکثر عمق با عمق محدود DLS. جستجوی عمق تکراری IDS. الگوریتم جستجوی طولانی کننده تکراری ILS. دوطرفه.

الگوریتم BFS از یک صف استفاده میکند و تکراری بودن گره های درخت کنترل نمیشود. برای چک کردن تکراری بودن از الگوریتم جستجوی گراف باید استفاده کرد.

ارزیابی BFS: کامل است(اگر فاکتور انشعاب بینهایت نباشد.). بهینه است(همواره کم عمقترین جواب را باز میگرداند و وقتی هزینه عملیات یکسان باشد کم عمق ترین بهینه است.). پیچیدگی زمانی نمایی دارد.(O(b^d+1)) پیچیدگی فضایی نمایی دارد.(O(b^d+1))

الگوریتم جستجوی هزینه یکنواخت UCS هم گره های تکراری تولید میکند و ارزیابی آن میشود: کامل است(اگر صفر و یا منفی نداشته باشیم). بهینه است. پیچیدگی زمانی و فضایی نمایی دارد.

اگر هزینه همه عملیات یکسان باشد UCSهمان BFS میشود.

در UCS از صف اولویت استفاده میکنیم.

در صورت وجود هزینه منفی ممکن است UCS در حلقه بی نهایت بیوفتد.

ارزیابی DFS:کامل نیست.(ممکن است در حلقه بی نهایت بیوفتد). لزوما بهینه نیست. پیچیدگی زمانی نمایی است O(b^m) و پیچیدگی فضایی خطی است O(bm) .

برای DFS از استک استفاده میشود.

درصورتی که تعداد راه حل ها زیاد باشد و با پیمایش هر شاخه ای بتوان به جوابی رسید DFS بهتر از BFS است.

ارزیابی جستجوی حداکثر عمق محدود DLS: کامل نیست. بهینه نیست. پیچیدگی زمانی نمایی دارد. O(b^l) . پیچیدگی فضایی خطی دارد. O(bl).

در حقیقت DFS نوع خاصی از DLS با L بی نهایت است.

در IDS هر گره میانی چندین بار تولید میشود ولی سربار زیادی ایجاد نمیکند.

ارزیابی جستجوی عمقی تکراری IDS:کامل است. بهینه بودنش مانند BFS است.(یعنی اگر هزینه همه یکسان باشد بهینه است.) پیچیدگی زمانی نمایی دارد. O(b^d) و پیچیدگی فضایی خطی دارد O(bd)

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

الگوریتم جستجوی ILS پیمایش عمقی میکند.

ارزیابی الگوریتم جستجوی طولانی کننده تکراری ILS: کامل است. بهینه است. پیچیدگی زمانی نمایی و پیچیدگی فضایی خطی دارد.

ارزیابی جستجوی دو طرفه:اگر backward و  forward هر دو سطحی باشند کامل است در غیر این صورت ممکن است کامل نباشد. بهینه بودن مشابه کامل بودن است.پیچیدگی زمانی و فضایی نمایی و O(b^d/2) است.

در مسایل با تکرار زیاد جستجوی گرافی بهتر از جستجوی درختی عمل می کند و همه الگوریتمهای جستجوی ناآگاهانه را میتوان بصورت جستجوی گراف پیاده سازی کرد ولی دیگر فضای مصرفی DFS و IDS خط نیست.

پیچیدگی زمانی و فضایی جستجوی گرافی متناسب با اندازه فضای حالت است  و ممکن است خیلی کمتر از O(b^d) باشد.

برای حل یک مساله با روش جستجو باید حالت هدف مشخص باشد. حالتهای بعدی هر حالت مشخص باشند و حالت شروع مشخص باشد.

فرموله کردن هدف باید همواره قبل از فرموله کردن مساله انجام گیرد.

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