سوال ۸۰ کنکور ارشد علوم کامپیوتر ۱۴۰۴
اهمیت
۰/۵
مسئله ضرب زنجیره‌ای ماتریس‌ها (Matrix Chain Multiplication) را در روش شاخه و حد (Branch and Bound) برای پیدا کردن ترتیب بهینه ضرب ماتریس‌ها استفاده می‌شود. کدام‌یک از گزینه‌های زیر به‌درستی مفهوم حد پایین (Bounds) را در این روش توضیح می‌دهد؟
پاسخ صحیح: گزینهٔ A — حد پایین هر شاخه (گره) درخت فضای حالت برابر هزینهٔ ضرب‌های انجام‌شده تا آن گره به‌علاوهٔ یک تخمین کمینهٔ (خوش‌بینانهٔ) هزینهٔ ضرب ماتریس‌های باقی‌مانده است؛ شاخه‌ای هَرَس می‌شود که این حد پایین آن کمتر از بهترین جواب کامل یافت‌شده تاکنون نباشد.
پاسخ تشریحی
What "bound" means in Branch and Bound
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#branch-and-bound#lower-bound#matrix-chain#state-space#pruning