سلام
خیلی ممنون
(۲۵ دى ۱۳۹۴ ۰۴:۵۷ ب.ظ)masoomeh_s نوشته شده توسط: سلام
خیلی ممنون
سلام.
من فقط الان اون سوال هرس الفا بتا رو دیدم و حلش کردم و سعی میکنم خوب توضیحش بدم.
جواب نهایی و کلی من اینه که پاسخ سوال توی گزینه ها نیست.اگر میشه بگید سوال رو از کدوم منبع دیدید(برای این میگم چون ممکنه سوال واقعا کلش غلط باشه)
حالا چرا :
خب بیاین حل ش کنیم.برای حلش میدونید که از سمت چپ گره ها بررسی میشن.(به صورت عمقی). سمت چپ ترین زیر درخت همیشه به صورت کامل دیده میشه.پس گره های L و M بررسی میشن و ماکزیممشون میشه ۱۱/پس الان مقدار گره E یازده هستش.وقتی یکی از زیر درخت های یک گره مقدارش مشخص میشه خود پدر اون مقدار رو به صورت موقت اختیار میکنه.پس الان مقدار B هم میشه ۱۱/ خب بریم سراغ زیر درخت F, گره N دیده میشه و مقدار ۱۲ هست و اون رو به F نسبت میدیم. گره O اگر از ۱۲ بیشتر باشه میتونه برای اف انتخاب بشه ولی توی نقطه بی انتخاب نمیشه.چون مینیمم رو میخواد و اگر هم کمتر از ۱۲ باشه همون جا توی نقطه اف رد میشه چون اف ماکزیمم رو میخواد.پس چون هر مقداری که O داشته باشی تاثیری در مساله نداره حذفش میکنیم. پس مقدار کلی و نهایی و مینیممی که گره B میتونه برای خودش داشته باشه ۱۱ هست.چون گره B یکی از زیر درختان پدرش یعنی A هست و مقدارش کامل شده پس A به صورت موقت میتونه مقدار ۱۱ رو برای خودش داشته باشه.میریم سراغ زیر درخت C و بعدش G .نکته مهمی که باعث میشه اینجا دو تا از گزینه ها رد بشه اینه که گزینه های ۲ و ۴ گفتن باید Q جز حذف شده ها باشه. که این امکان نداره.اساسا گره p و Q باید باهم مقایسه بشن و ماکزیمم رو برای G بفرستیم و بعدش C رو یه مقدار دهی اولیه بکنیم.پس نمیشه Q رو حذف کرد.الان مقدار ماکزیمم برای G برابر ۵ هست و چون مقدار ثابت گرفته پدرش که سی باشه یه مقدار موقت میگیره و اون ۵ هست. تا الان دو تا از گزینه هایی که داریم حذف شدن.درسته ؟؟
میمونه گزینه های ۱ و ۳/ خب. بعد از بررسی زیر درخت G از زیر درختان C باید بریم سراغ دو تا زیر درخت دیگه سی. خب .بیاین ببینین اگر H هر چی باشه فعلا مهم نیست . اگر بزرگتر از ۵ باشه توی انتخاب C مهم نیست چون اون مقدار مینیمم رو میخواد و حدالمقدور کمتر از ۵ .اگر کمتر از ۵ باشه درسته واسه سی انتخاب میشه ولی تاثیری واسه A نداره.چون اون مقدار ۱۱ رو واسه خودش فعلا داره و دوست داره اگر این مقدار قرار تغییری کنه بیشتر از ۱۱ باشه. نه کمتر از ۵/!! پس گره H و زیر درختانش حذف هستن.چون هر چی باشن تاثیری ندارن.واسه I هم همین اتفاق میفته و اون و زیر درختانش حذف میشن. اگر به تا به اینجای توضیحات من رسیدین و با دقت توی شکل بررسی کرده باشین میبینین که درسته و گزینه Hو I و البته زیردرختانش توی حذف شده های گزینه ی ۱ و ۳ نیستن.!!!
پس اونها هم جواب نیستن و سوال مشکل داره.
ولی من بقیه رو هم توضیح میدم.تا اینجای کار مقدار A هنوز مقدار موقت ۱۱ رو برای خودش داره.میریم سراغ زیر درخت D . بای اینجا خوببببببب دقت کنید که گره های v و W و X هر سه باید بررسی بشن تا بتونیم یه مقدار درست و قطعی برای J ارائه بدیم و بعد از اون برای D .مقدار جی میشه ۸ و بعدش برای D میشه ۸/ مقدار ۸ کوچکتر از ۱۱ هستش و تاثیری توی A نداره.مقدار K و زیرگره هاش تاثیری ندارن و اونها هم حذف هستن.
جواب کلی : O-H-R-S-I-T-U-K-Y-Z
-----
اگر زیاد حرف زدم و پست طولانی شد ببخشید.
اگر جوابی که دادم و درست نبود و نظر دوستان چیزی غیر این بود ممنون میشم توضیح بدید.دوست دارم چیز جدید یاد بگیرم.ممنون
سعی کردم سوال جستجوی A* رو هم حل کنم. ولی تا ۹۰ درصد اطمینان دارم درسته .اگر کس دیگری سوال رو بررسی کنه و نظرش رو بده هم من مطمئن میشم که جوابم درسته و هم دوست عزیزی که در ابتدا سوال پرسیدن.پس به دو نفر کمک کردن
----------------------------------------------
خب بریم سراغ حل سوال.در ابتدا گره A بررسی میشه.توی این جستجو تابعی که براساس اون تصمیم میگیریم جمع دو مقدار هست.فاصله ای که تا الان طی کرده و فاصله ای که تا هدف داره. گره A به سه گره دیگه متصل هست و در واقع ۳ تا بچه داره .برای B و C و D مقدار تابع F رو حساب میکنیم و گره B با مقدار ۶۰ کمترین مقدار رو داره و پس اون رو انتخاب میکنیم.اون خودش گره های Cو F و E رو داره که گره E با مقدار ۷۰ کمترین مقدار هزینه رو داره و پس اون رو انتخاب میکنیم.گره e گره های f و H رو داره که باید اف رو به خاطر داشتن هزینه ۷۰ انتخاب کنیم. و بعد از اون گره های I و H رو داریم که گره I مقدار ۸۰ رو داره و نزدیک تر به هدف هست. پس انتخاب ش میکنیم. و بعد از اون به سمت H میریم که جواب مسئله هست. دقت کنید که قبل از این مرحله میتونستیم H رو انتخاب کنیم ولی هزینه کلی مسئله بیشتر میشه.حدود ۱۰۰ میشد ولی الان هزیینه ۹۰ هستش.
گره های مسیر : A-B-E-F-I-H
هزینه تا هدف : ۹۰
----------------------------
خوشحال میشم یه نفر دیگه که این مبحث رو بهتر بلده حلش کنه و بگه تا من هم از جوابم اطمینان پیدا کنم یا مشکلم رو حل کنم.مرسی