سلام
در شکل زیر هدف پیدا کردن کوتاه ترین مسیر (با استفاده از الگوریتم دیکسترا) از گره A به گره D است که ۶ مرحله اول رو طبق شکل نشون داده.
من متوجه نشدم وقتی از E اومد به G ، (شکل d) ، چطوری بعدش دوباره رفت به گره F (در شکل e)؟ علتش رو میدونم چون اگه از F بره هزینه مسیر تا رسیدن به H کمتر میشه و به جای ۹، ۸ میشه. اما متوجه نشدم الگوریتم به چه روشی اینو انجام داد..
![[تصویر: 321646_35jw7wl.jpg]](https://img.manesht.ir/321646_35jw7wl.jpg)
(۲۲ آذر ۱۳۹۳ ۰۹:۱۱ ب.ظ)alwaysPeace نوشته شده توسط: سلامببین کلا روشش همینه دیگه.
در شکل زیر هدف پیدا کردن کوتاه ترین مسیر (با استفاده از الگوریتم دیکسترا) از گره A به گره D است که ۶ مرحله اول رو طبق شکل نشون داده.
من متوجه نشدم وقتی از E اومد به G ، (شکل d) ، چطوری بعدش دوباره رفت به گره F (در شکل e)؟ علتش رو میدونم چون اگه از F بره هزینه مسیر تا رسیدن به H کمتر میشه و به جای ۹، ۸ میشه. اما متوجه نشدم الگوریتم به چه روشی اینو انجام داد..
شما اون راسهای سیاه رو همیشه باید درنظر بگیری
یعنی همیشه باید مسیری رو انتخاب کنی که هزینه طی شده + هزینه که قراره طی کنیم ، کمتر باشه
واسه همینم شما باید در هر مرحله اجرای الگوریتم یالهای متصل به راسهای ملاقات شده رو با هم در نظر بگیری و کمترین هزینه طی شده + هزینه که قراره طی بشه رو انتخاب کنی
(۲۲ آذر ۱۳۹۳ ۰۹:۴۲ ب.ظ)explorer نوشته شده توسط:(22 آذر ۱۳۹۳ ۰۹:۱۱ ب.ظ)alwaysPeace نوشته شده توسط: سلامببین کلا روشش همینه دیگه.
در شکل زیر هدف پیدا کردن کوتاه ترین مسیر (با استفاده از الگوریتم دیکسترا) از گره A به گره D است که ۶ مرحله اول رو طبق شکل نشون داده.
من متوجه نشدم وقتی از E اومد به G ، (شکل d) ، چطوری بعدش دوباره رفت به گره F (در شکل e)؟ علتش رو میدونم چون اگه از F بره هزینه مسیر تا رسیدن به H کمتر میشه و به جای ۹، ۸ میشه. اما متوجه نشدم الگوریتم به چه روشی اینو انجام داد..
شما اون راسهای سیاه رو همیشه باید درنظر بگیری
یعنی همیشه باید مسیری رو انتخاب کنی که هزینه طی شده + هزینه که قراره طی کنیم ، کمتر باشه
واسه همینم شما باید در هر مرحله اجرای الگوریتم یالهای متصل به راسهای ملاقات شده رو با هم در نظر بگیری و کمترین هزینه طی شده + هزینه که قراره طی بشه رو انتخاب کنی
خب ببینید الان فرض کنید ما تو راس G اومدیم، مرحله بعدی تنها راسی که میتونیم بریم راس H هست. میایم هزینشو حساب می کنیم میبینیم برابره با ۹. خب اینجا دو باره بر میگردیم عقب (تو راس E) و بعد حساب می کنیم که اگه از E بخوایم بریم به H هزینش چه قدر میشه و اگه کمتر بود اونو جایگزین کنیم و باید برای هر گره این کارو انجام بدیم. ولی این کار تو دستور کار الگوریتم دیکسترا گفته نشده و تو مراحلش نیست..!
(۲۲ آذر ۱۳۹۳ ۱۰:۲۸ ب.ظ)alwaysPeace نوشته شده توسط: خب ببینید الان فرض کنید ما تو راس G اومدیم، مرحله بعدی تنها راسی که میتونیم بریم راس H هست. میایم هزینشو حساب می کنیم میبینیم برابره با ۹. خب اینجا دو باره بر میگردیم عقب (تو راس E) و بعد حساب می کنیم که اگه از E بخوایم بریم به H هزینش چه قدر میشه و اگه کمتر بود اونو جایگزین کنیم و باید برای هر گره این کارو انجام بدیم. ولی این کار تو دستور کار الگوریتم دیکسترا گفته نشده و تو مراحلش نیست..!شما باید برای ادامه تمام یالهای متصل به راسهای سیاه شده در نظر بگیری نه فقط آخرین یال.
یعنی شما وقتی به G رسیدی تنها یال GH مد نظر نیست بلکه علاوه بر اون باید یالهای EF و CB رو هم در نظر بگیری چون که اینها متصل به راسهای ملاقات شده هستند
(۲۲ آذر ۱۳۹۳ ۱۰:۳۹ ب.ظ)explorer نوشته شده توسط:(22 آذر ۱۳۹۳ ۱۰:۲۸ ب.ظ)alwaysPeace نوشته شده توسط: خب ببینید الان فرض کنید ما تو راس G اومدیم، مرحله بعدی تنها راسی که میتونیم بریم راس H هست. میایم هزینشو حساب می کنیم میبینیم برابره با ۹. خب اینجا دو باره بر میگردیم عقب (تو راس E) و بعد حساب می کنیم که اگه از E بخوایم بریم به H هزینش چه قدر میشه و اگه کمتر بود اونو جایگزین کنیم و باید برای هر گره این کارو انجام بدیم. ولی این کار تو دستور کار الگوریتم دیکسترا گفته نشده و تو مراحلش نیست..!شما باید برای ادامه تمام یالهای متصل به راسهای سیاه شده در نظر بگیری نه فقط آخرین یال.
یعنی شما وقتی به G رسیدی تنها یال GH مد نظر نیست بلکه علاوه بر اون باید یالهای EF و CB رو هم در نظر بگیری چون که اینها متصل به راسهای ملاقات شده هستند
بله درسته، خیلی ممنوون