سلام

ببینید این الگوریتم عمقی پیش میره
این الگوریتم تمام گره هایی که مقدار کوچکتر مساوی آستانه رو داشته باشن رو بررسی و توسعه میده

و طبق گفته سوال به ترتیب حروف الفبا بررسی میکنیم

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

پس میشه همون گزینه ۳ دیگه

تویه لینک زیر همین سوال با شکل توضیح داده شده

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۰۱ اسفند ۱۳۹۵ ۱۰:۵۲ ق.ظ)delete4all نوشته شده توسط:  سلام
این سوال قبلا اینجا کامل حل شده و توضیح داده شده اگه شما تا انتهای پست رو بخونید متوجه میشید که اشتباه نیست

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

نگاه کنید اگه بازم مشکل داشتین بگین

هزینه هرکدوم از گره ها به این ترتیب میشه:
A:6 - B:2 - C:7- G:7- E:15- D:4- F:8
چون در محاسبه g و h کمترین هزینه مسیر رو در نظر میگیریم.

حالا اگه این الگوریتم عمقی پیش میره در جستجوی عمقی سمت چپ ترین فرزند رو برای بسط دادن انتخاب میکنیم یعنی C که در این حالت گزینه ۴ باید درست باشه. اگر بگیم هزینه c، ۷ هست و مقدار استانه ماهم ۷ پس نمیتونیم انتخابش کنیم میریم سراغ B.فقط با توجه به درست بودن گزینه ۳ من نمیفهمم چرا بعد از دیدن B و D دوباره برگشته C رو دیده؟ تو عمقی مگه برمیگردیم؟

(۰۱ اسفند ۱۳۹۵ ۰۶:۱۷ ب.ظ)sepideh entezari نوشته شده توسط:  

(01 اسفند ۱۳۹۵ ۱۰:۵۲ ق.ظ)delete4all نوشته شده توسط:  سلام
این سوال قبلا اینجا کامل حل شده و توضیح داده شده اگه شما تا انتهای پست رو بخونید متوجه میشید که اشتباه نیست

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

نگاه کنید اگه بازم مشکل داشتین بگین

هزینه هرکدوم از گره ها به این ترتیب میشه:
A:6 - B:2 - C:7- G:7- E:15- D:4- F:8
چون در محاسبه g و h کمترین هزینه مسیر رو در نظر میگیریم.

حالا اگه این الگوریتم عمقی پیش میره در جستجوی عمقی سمت چپ ترین فرزند رو برای بسط دادن انتخاب میکنیم یعنی C که در این حالت گزینه ۴ باید درست باشه. اگر بگیم هزینه c، ۷ هست و مقدار استانه ماهم ۷ پس نمیتونیم انتخابش کنیم میریم سراغ B.فقط با توجه به درست بودن گزینه ۳ من نمیفهمم چرا بعد از دیدن B و D دوباره برگشته C رو دیده؟ تو عمقی مگه برمیگردیم؟

پست بالایی رو ویرایش کردم اون رو ببینید توضیح دادم براتون

(۰۱ اسفند ۱۳۹۵ ۰۶:۵۰ ب.ظ)delete4all نوشته شده توسط:  

(01 اسفند ۱۳۹۵ ۰۶:۱۷ ب.ظ)sepideh entezari نوشته شده توسط:  

(01 اسفند ۱۳۹۵ ۱۰:۵۲ ق.ظ)delete4all نوشته شده توسط:  سلام
این سوال قبلا اینجا کامل حل شده و توضیح داده شده اگه شما تا انتهای پست رو بخونید متوجه میشید که اشتباه نیست

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

نگاه کنید اگه بازم مشکل داشتین بگین

هزینه هرکدوم از گره ها به این ترتیب میشه:
A:6 - B:2 - C:7- G:7- E:15- D:4- F:8
چون در محاسبه g و h کمترین هزینه مسیر رو در نظر میگیریم.

حالا اگه این الگوریتم عمقی پیش میره در جستجوی عمقی سمت چپ ترین فرزند رو برای بسط دادن انتخاب میکنیم یعنی C که در این حالت گزینه ۴ باید درست باشه. اگر بگیم هزینه c، ۷ هست و مقدار استانه ماهم ۷ پس نمیتونیم انتخابش کنیم میریم سراغ B.فقط با توجه به درست بودن گزینه ۳ من نمیفهمم چرا بعد از دیدن B و D دوباره برگشته C رو دیده؟ تو عمقی مگه برمیگردیم؟

پست بالایی رو ویرایش کردم اون رو ببینید توضیح دادم براتون

ممنون. من فقط تصور داشتم سمت چپ ترین فرزند C هست نه B

بعد نوشتین:
از بین فرزندان D هیچکدومشون کمتر مساوی آستانه نیست پس برمیگرده میره سراغ فرزند دوم A

خب G فرزند D هست هزینه اش هم ۷ هه.

نقل قول: ممنون. من فقط تصور داشتم سمت چپ ترین فرزند C هست نه B

بعد نوشتین:
از بین فرزندان D هیچکدومشون کمتر مساوی آستانه نیست پس برمیگرده میره سراغ فرزند دوم A

خب G فرزند D هست هزینه اش هم ۷ هه.

گره D (که زیر مجموعه گره B هست) هیچکدوم از فرزندانش کوچکتر مساوی آستانه نیستن
ولی گره D ( که زیر مجموعه گره C هست) گره G فرزندش هست که به عنوان هدف انتخاب شده

اگه اون لینک که گزاشتم رو ببینید تویه عکسی که از حل این سوال گزاشته شده متوجه میشید کامل

سلام دوستان
میشه توضیح بدید چرا گره تکراری که قبلا بسط داده شده دوباره انتخاب شد؟؟
مگه گره هایی که یک بار بسط داده شدن رو تو لیست بسته نگه نمیداریم که دیگه بسطشون ندیم؟؟
منظور گره D هست