سلام
سوال ازمون ۸ مدرسان هست گفته اگرشروع کننده بازی maxباشدوامتیازات هم بین ۱تا۱۰باشد چندتابرگ هرس میشود؟
۳-۴-۵-۶
جواب گفته سه تا برگ نارنجی های توشکل ممنون(اعدادازچپ ب راست توی شکل۵-۶-۷-۸-۹-۱-۸-۴-۸-۷-۷-۸-۵-۳)
(۱۸ فروردین ۱۳۹۶ ۱۰:۳۶ ب.ظ)mzha نوشته شده توسط: سلام
سوال ازمون ۸ مدرسان هست گفته اگرشروع کننده بازی maxباشدوامتیازات هم بین ۱تا۱۰باشد چندتابرگ هرس میشود؟
۳-۴-۵-۶
جواب گفته سه تا برگ نارنجی های توشکل ممنون(اعدادازچپ ب راست توی شکل۵-۶-۷-۸-۹-۱-۸-۴-۸-۷-۷-۸-۵-۳)
خب طرز محاسبه اینجوریه که برای گره min که زیرش عنصر شانس داره , مقدار هر فرزند زیر عنصر شانس رو در عنصر شانس ضرب میکنی و هر کدوم کمتر شد رو انتخاب میکنی , در آخر مقدارهای انتخاب شده توسط همه عناصر شانس رو باهم جمع میکنی که میشه مقدار گره min .
برای سمت چپ ترین گره min داریم که از یه طرف : ۵*(۱/۲) که مساوی ۲/۵ میشه و از طرف دیگه : ۸*(۱/۲) که مساوی۴ میشه. چون گره min پس ۲/۵ رو برمیداره
حالا برای گره min وسط , اولین فرزند مساوی یکه که کمترین مقدار ممکنه (طبق صورت مساله) به همین خاطر گره min اون رو بر میداره و بقیه رو بررسی نمیکنه ( اولین هرس ) . حالا در شاخه ی دیگه ۴ میاد بالا و وقتی در ۱/۲ ضرب بشه و با مقدار شاخه دیگه ( ۱ ضرب در ۱/۲ که مساوی نیمه ) جمع بشه مقدارش برابر با ۲/۵ میشه . هر مقدار دیگه که بتونه بیاد بالا دو تا حالت پیش میاره : اول اینکه بیشتر از ۴ باشه که این مقدار ۲/۵ رو بیشتر میکنه و در نتیجه گره min اون رو انتخاب نمیکنه . دوم اینکه کمتر میکنه و گره min انتخابش میکنه ولی چون گره min سمت چپ مقدار نهاییش شده ۲/۵ , اگه مقدار نهایی گره min وسطی کمتر از ۲/۵ بشه گره max ما مقدار گره min سمت چپ رو برمیداره ! پس در هر صورت محاسبه ی بقیه حالاتش بی فایده است پس هر دوشاخه باقی مانده هرس میشه
میدونم ی ذره پیچیده شد ولی چه میشه کرد
این سوال مشابه تخصصی ۸۸ هست چپ ترین گره که مقدار ۳ داره باید حذف بشه مه پاسخنامه مدرسان ابنجا رو اشتباه کرده
چون وقتی هفت و پنج و هشت رو بررسی میکنیم متوجه میشم که حداکثر مقدار این زریردرخت شش هست که در هرحال از ۶۰۵ ای که قبلا بدست اومده کمتذه پس نیازی به بررسی رایت ترین گره نیسن
(۱۹ فروردین ۱۳۹۶ ۰۹:۱۲ ق.ظ)d_felfelak نوشته شده توسط: این سوال مشابه تخصصی ۸۸ هست چپ ترین گره که مقدار ۳ داره باید حذف بشه مه پاسخنامه مدرسان ابنجا رو اشتباه کرده
چون وقتی هفت و پنج و هشت رو بررسی میکنیم متوجه میشم که حداکثر مقدار این زریردرخت شش هست که در هرحال از ۶۰۵ ای که قبلا بدست اومده کمتذه پس نیازی به بررسی رایت ترین گره نیسن
میشه بیشتر توضیح بدید ؟ نمیدونم کجای کار اشتباهه چون به نظر من جواب درسته
گره هایی که حذف میشن به ترتیب از چپ به راست اینا هستن: ۸۴۸۷۳
زیرمجموعه چپ ترین گره شانس تو این سوال کلا بررسی میشه و هیچی ازش هرس نمیشه، چون باید گره MAX یه مقدار اولیه بگیره تا بتونیم بقیه رو نسبت بهش بسنجیم و هرس انجام بدیم. الان اینجا از چپ به راست گره های ۵۶۷۸۹ مطمئنیم که هیچ هرسی براشون در کار نیست و گره MAX مقدار ۶/۵ می گیره.
حالا گره شانس دوم:
وقتی گره MIN اول مقدار ۱ رو می گیره می دونیم که این حداقل مقدار سودمندیه، پس این گره هیچ وقت مقدار بیشتر یا کمتر از این رو نمی گیره، پس شاخه ۸ هرس میشه. حالا شاخه MIN کناریش حتی اگه مقدار ۱۰ هم داشته باشه داریم: [tex]1\times0.5\: +\: 10\times0.5=5.5[/tex]
پس حتی با داشتن مقدار ۱۰ که حداکثر سودمندیه بازم گره MAX این مقدارو انتخاب نمی کنه چون از ۶/۵ کمتره. کلا اون شاخه ها هم هرس میشن. یعنی شاخه های ۴۸۷
حالا می ریم سراغ گره شانس سوم:
تو سمت چپ هر دو شاخه رو بررسی می کنیم و گره MIN مقدار ۷ رو می گیره. بعد تو شاخه MIN سمت راستش اول مقدار ۵ رو می گیره. حالا ما می دونیم گره MIN دیگه بیشتر از این مقدارو قبول نمی کنه و الان داریم [tex]7\times0.5+5\times0.5=6[/tex]
پس بازم از گره MAX کمتره و گره MAX هیچ وقت این رو انتخاب نمی کنه. پس شاخه ۳ هم حذف میشه.
پس در کل ۵ تا شاخه حذف میشه
جواب پرهوده درسته....۵ تا حذف میشه.....
ممنون از تمام دوستان که وقت گذاشتید منم با حل دوستمون پرهوده موافقم