حل تشریحی سوال شماره 91 مجموعه دروس تخصصی مشترک

مسئله برج هانوی را در نظر بگیرید که در آن قرار است دیسک‌هایی که در شروع به‌ترتیب بزرگ به کوچک روی ميله شماره ۱ قرار گرفته‌اند در انتها به همین ترتیب روی میله شماره ۳ قرار گرفته باشند کنش‌ها در این محیط می توانند دیسکی را که روی آن چیزی قرار نگرفته یا به عبارت دیگر بالاترین دیسک روی یک میله است را به یک میله خالی با روی یک دیسک بزرگ تر منتقل کند. فرض کنید دیسک با کوچکترین اندازه ۱ واحد دیسک متوسط ۲ واحد و دیسک بزرگ ۳ واحد وزن داشته باشد و هزینه انتقال هر واحد وزن بین دو میله با فاصله ۱ برابر ۱ واحد ولی بین دو میله با فاصله ۲ به واسطه نداشتن استراحت برابر ۳ واحد باشد. اگر هزینه کلی انتقال هر دیسک ضرب تعداد واحد وزن آن در هزینه جابه‌جایی هر واحد وزن باشد کدام گزینه میزان هزینه کلی با مقدار تابع (n)) برای ۳ گره اولی که توسط الگوریتم UCS با فرض جستجوی گرافی گسترش می‌یابند یا به عبارت دیگر از صف برداشته می‌شوند را به درستی نشان می‌دهد و همچنین از بین توابع ابتکاری (heuristic) زیر کدام موارد قابل قبول (admissible) هستند؟ (قاعدتاً در تمام فضای جستجو)

$h_1$: سه برابر جمع وزن دیسکهای روی میله اول

$h_2$: جمع وزن دیسکهای روی میله دوم