سوال ۷۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

برای حل یک مسئلهٔ جستجو، از روش‌های محلی تپه‌نوردی استفاده کرده‌ایم. فرض کنید احتمال موفقیت در جستجویی که از یک حالت تصادفی شروع می‌شود، برابر با ۲۵ درصد است. زمانی که جستجو موفقیت‌آمیز باشد، به‌صورت متوسط نیاز به طی کردن ۷ گام دارد و در صورتی که به یک کمینهٔ محلی غیربهینه همگرا شود، به‌صورت متوسط ۹ گام طی می‌شود. به‌منظور حصول اطمینان از به جواب رسیدن روش، در صورت همگرایی به کمینهٔ محلی غیر بهینه، از حالت تصادفی اولیهٔ دیگری جستجو را آغاز می‌کنیم. به‌صورت متوسط چند گام برای رسیدن به پاسخ بهینهٔ سراسری باید طی شود؟