تالار گفتمان مانشت
تست آی تی ۸۴ - هرس آلفا بتا - نسخه‌ی قابل چاپ

تست آی تی ۸۴ - هرس آلفا بتا - hejran_ha - 22 آبان ۱۳۹۱ ۰۶:۰۷ ب.ظ

مرسی دوست من
شما اگه کتاب پوران را دارید لطفا به سوال ۱۳ ص ۱۷۳ یک نگاهی بندازید من چه جوری بفهمم که یک گره را باید حذف کنیم یا ملاقات نکنیم ؟؟؟؟
[attachment=9605]

هرس کردن در الفا و بتا - M@A - 22 آبان ۱۳۹۱ ۰۸:۵۶ ب.ظ

سلام دوست عزیز
دو جمله بهت میگم یادت بمونه:
"شاخه ای ک "آلفای" اون بزرگتر یا مساوی "بتای" اجدادش باشه حذف میشه"
"شاخه ای ک "بتای" اون کوچیکتر یا مساوی "آلفای" اجدادش باشه حذف میشه"
در مورد همون سوال سطر اول max سطر دوم min سطر سوم max:
بتا مربوط ب سطر min میشه و آلفا رو برای سطرهای max مینویسی
از سمت چپ شروع میکنی وقتی شاخه ۶ رو ملاقات کردی برای اجدادش اون عدد شش رو بنویس حواست باشه یه ۶ برای بتا و یه ۶ برای آلفای سطر اوله
وقتی شاخه ۷ ملاقات شد عدد ۷ برای همون max مربوطه ش ثبت میشه
میری سراغ شاخه عدد ۸ وقتی عدد ۸ رو کنار پدرش مینویسی(E) جمله اولی ک نوشتم رو بخون:"شاخه ای ک "آلفای" اون بزرگتر یا مساوی "بتای" اجدادش باشه حذف میشه" پس چون این آلفا از بتای جدش بزرگتره پس شاخه بعدش ملاقات نشده حذف میشه برای بقیه هم همین جوره
برا همون سوال یادت باشه وقتی عدد ۶ برایF ثبت شد پدر مربوطه اون c عدد ۶ میشه باتوجه ب زیر درخت چپ برای A عدد ۷ ثبت شده یعنی آلفا برابر ۷/وقتی زیردرخت چپ C بررسی شد و عدد ۶ برای اون ثبت شد میبینی ک بتای اون از آلفای جدش کوچیکتره پس زیر درخت راست C کلا حذف میشه
ببخشید اگه با مطالبم گیج شدید باورکنید این مبحث نمیشی نوشتنی توضیح داد باید حضوری کسی واستون توضیح بده.امیدوارم همین اندازه بدردتون بخوره
سوالی بود درخدمتم

RE: هرس کردن در الفا و بتا - Marcel - 22 آبان ۱۳۹۱ ۰۹:۰۸ ب.ظ

ببین اینجا، سطح اول MAX سطح دوم MIN و سطح سوم MAX فرزندانشونُ انتخاب میکنن،خب...اول میای رو D بین H,I ماکسیمم که ۷ باشه انتخاب میشه و مقدار B و A برابر ۷ میشه،حالا میای رو E اول نگاه میکنی که J مقدارش ۸ و چون گره B مینیمم فرزندانشُ انتخاب میکنه و E ماکزیمم پس میگی اگه گره K از ۸ کوچیکتر باشه که توسط E انتخاب نمیشه (چون E ماکزیمم فرزندانشُ انتخاب میکنه) و اگه از ۸ بزرگتر باشه توسط E انتخاب میشه ولی توسط B انتخاب نمیشه (چون B منیمم فرزندانشُ انتخاب میکنه که ۷) پس اینجا میگیم که K هرس میشه.
حالا میای رو F نگاه میکنی بین L,M ماکزیمم که ۶ باشه انتخاب میشه و مقدار F و C برار ۶ میشه، حالا اینجا باید دقت کنی که چون گره A مقدارش ۷ شده بود و گره A ماکزیمم فرزندانشُ انتخاب میکنه و چون الان گره C مقدارش ۶ شده و گره C مینیمم فرزندانشُ انتخاب میکنه پس فرزند راست C در صورتی انتخاب میشه که کمتر از ۶ باشه و اگه کمتر از ۶ باشه توسط A انتخاب نمیشه، پس اینجوری G,N,O هرس میشن.

هرس کردن در الفا و بتا - hejran_ha - 22 آبان ۱۳۹۱ ۱۱:۲۳ ب.ظ

ممنون از دوستان گل.
روش اقای/خانم Marcel را ظاهر بهتر فهمیدم، با تشکر و خسته نباشید به اقا امین گل بابت نوشته هاشون.
فقط چند تا سوال .
۱- شما گفتید : {اول میای رو D بین H,I ماکسیمم که ۷ باشه انتخاب میشه و مقدار B و A برابر ۷ میشه} یعنی تا اخر این مقدار ثابت است یا فرق میکنه ، چون ظاهر تو این سوال ثابت است !!!!

۲- این اخری را زیاد نگرفتم :{حالا میای رو F نگاه میکنی بین L,M ماکزیمم که ۶ باشه انتخاب میشه و مقدار F و C برار ۶ میشه، حالا اینجا باید دقت کنی که چون گره A مقدارش ۷ شده بود و گره A ماکزیمم فرزندانشُ انتخاب میکنه و چون الان گره C مقدارش ۶ شده و گره C مینیمم فرزندانشُ انتخاب میکنه پس فرزند راست C در صورتی انتخاب میشه که کمتر از ۶ باشه و اگه کمتر از ۶ باشه توسط A انتخاب نمیشه، پس اینجوری G,N,O هرس میشن.}

میشه اینو یه ذره بازتر کنید ؟؟؟؟

//////////////////////////////
نوبت اقا امین گل رسید.
میشه این ها را بازتر بگید :
"شاخه ای ک "آلفای" اون بزرگتر یا مساوی "بتای" اجدادش باشه حذف میشه"
"شاخه ای ک "بتای" اون کوچیکتر یا مساوی "آلفای" اجدادش باشه حذف میشه"

هرس کردن در الفا و بتا - M@A - 23 آبان ۱۳۹۱ ۱۲:۳۱ ق.ظ

جواب اولی: این مقدار ثابت نمیشه تا زمانی ک شاخه ی بررسی نشده در اون زیر درخت باشه ثابت نیست اما با اتمام اون زیر شاخه موقت ثابت میشه تا زیر درخت بعدی بررسی بشه
اگه اونجور ک گفتم روی A علامت آلفا رو روی B,C علامت بتا و روی D,E,F,G علامت آلفا بزاری وقتی باتوجه به بررسی شاخه اون بهش مقدار میدی میای نگاه میکنی اگر آلفا بود با بتای جدش مقایسه میکنی در صورتی ک بزرگتر بود دیگه سراغ شاخه بعدی نمیری و هرس میشه و درصورتی که بتا بود اونو با آلفای جدش مقایسه میکنی و هرس رو انجام میدی
D علامت آلفا داره و E میشه بتای جدش
B که علامت بتا داره A میشه آلفای جدش(اینجا چون تعداد سطوح زیاد نیست اجداد خیلی دور نیستن و در واقع والد حساب میشن اما برای درختای بزرگتر بیشتر مشخص میشه)

{حالا میای رو F نگاه میکنی بین L,M ماکزیمم که ۶ باشه انتخاب میشه و مقدار F و C برار ۶ میشه، حالا اینجا باید دقت کنی که چون گره A مقدارش ۷ شده بود و گره A ماکزیمم فرزندانشُ انتخاب میکنه و چون الان گره C مقدارش ۶ شده و گره C مینیمم فرزندانشُ انتخاب میکنه پس فرزند راست C در صورتی انتخاب میشه که کمتر از ۶ باشه و اگه کمتر از ۶ باشه توسط A انتخاب نمیشه، پس اینجوری G,N,O هرس میشن.}
با اجازه دوست بزرگوار اصلاحش میکنم:
حالا میای رو F نگاه میکنی بین L,M ماکزیمم که ۶ باشه انتخاب میشه و مقدار F و C برار ۶ میشه، حالا اینجا باید دقت کنی که چون گره A مقدار ماکزیمم رو انتخاب میکنه و برای B عدد ۷ ثبت شده و برای Cمقدار ۶ پس گره A با انتخاب B دیگه زیر شاخه راست C رو گسترش نمیده و تولید نشده اونارو هرس میکنه
...............
بازم شرمنده ....
اما منتظر جواب دوستمون هستم شاید من بد توضیح داده باشم
موفق باشید

RE: هرس کردن در الفا و بتا - Marcel - 23 آبان ۱۳۹۱ ۱۲:۴۳ ق.ظ

(۲۲ آبان ۱۳۹۱ ۱۱:۲۳ ب.ظ)hejran_ha نوشته شده توسط:  ۱- شما گفتید : {اول میای رو D بین H,I ماکسیمم که ۷ باشه انتخاب میشه و مقدار B و A برابر ۷ میشه} یعنی تا اخر این مقدار ثابت است یا فرق میکنه ، چون ظاهر تو این سوال ثابت است !!!!

۲- این اخری را زیاد نگرفتم :{حالا میای رو F نگاه میکنی بین L,M ماکزیمم که ۶ باشه انتخاب میشه و مقدار F و C برار ۶ میشه، حالا اینجا باید دقت کنی که چون گره A مقدارش ۷ شده بود و گره A ماکزیمم فرزندانشُ انتخاب میکنه و چون الان گره C مقدارش ۶ شده و گره C مینیمم فرزندانشُ انتخاب میکنه پس فرزند راست C در صورتی انتخاب میشه که کمتر از ۶ باشه و اگه کمتر از ۶ باشه توسط A انتخاب نمیشه، پس اینجوری G,N,O هرس میشن.}
بنده اقای مارسل هستم،سیبیلا رو نمیبینیBig Grin

۱- نه ثابت نیست، واسه اولین فرزند که مقدارش به دست اومد میای اونو به همه اجدادش میدی، چون هنوز گره دیگه یی بازدید نشده، کل قضیه Min-Max و هرس کردن سر همین مینیمم یا ماکزیمم کردن گره هاست.اگه ثابت بود که دیگه لازم نبود گره دیگه یی بازدید شه.

۲- ببین عزیز من، الان قبل اینکه بیای رو F مقدار A شده ۷، و اینُ میدونیم که گره A از بین فرزندانش گره ماکزیمم رو انتخاب میکنه ینی از بین B,C که فرزندانش هستن بیشترین رو انتخاب میکنه ،خب؟ حالا وقتی ما اومدیم رو F و مقدار ۶ انتخاب شد و F,C هر دو ۶ شدن ،چون A گره C رو در صورتی انتخاب میکنه که مقدارش از ۷ بیشتر باشه (چون خود A الان مقدارش ۷ هست) و این رو هم میدونیم که گره C در صورتی گره G رو انتخاب میکنه که G کمتر از ۶ باشه ، حالا ما میگیم اگه گره C بخاد یه مقدار کمتر از ۶ انتخاب کنه دیگه فایده یی واسه ماکزیمم کردن گره A نداره (چون کمتر مساوی ۶ و کمتر از ۷ هست) پس G هرس میشه.

دیگه ساده تر ازین نمیشه توضیح داد ، اگه بازم متوجه نمیشی، برو از اول فصل ۵ پورانُ بخون.مخصوصا صفحه ۱۶۰/

هرس کردن در الفا و بتا - hejran_ha - 23 آبان ۱۳۹۱ ۰۵:۰۷ ب.ظ

ممنونم از دوستان بزرگوار/انشالله هر دوتاتون صنعتی شریف.