کمترین هزینه در ارتباط گره های گراف ها - نسخهی قابل چاپ |
کمترین هزینه در ارتباط گره های گراف ها - kamal3401 - 17 خرداد ۱۳۹۵ ۱۱:۱۴ ب.ظ
سلام من از ی سوالی عکس گرفتم میخوام ببینم این به چه شکلی حل میشه ی روشی بود به اسم دایجکسترا ولی تا اونجایی که میدونم اون روش برای گراف های بدون جهت بود این گراف جهت داره میشه راهنمایی کنید |
RE: کمترین هزینه در ارتباط گره های گراف ها - Behnam - ۱۷ خرداد ۱۳۹۵ ۱۱:۳۸ ب.ظ
(۱۷ خرداد ۱۳۹۵ ۱۱:۱۴ ب.ظ)kamal3401 نوشته شده توسط: سلام من از ی سوالی عکس گرفتم میخوام ببینم این به چه شکلی حل میشه در فایل ضمیمه شده الگوریتم دیکاسترا به همراه مثال گراف جهتدار به صورت مرحله به مرحله نشان داده شده است [attachment=20019] |
RE: کمترین هزینه در ارتباط گره های گراف ها - kamal3401 - 17 خرداد ۱۳۹۵ ۱۱:۴۳ ب.ظ
(۱۷ خرداد ۱۳۹۵ ۱۱:۳۸ ب.ظ)behnam5670 نوشته شده توسط:ممنون(17 خرداد ۱۳۹۵ ۱۱:۱۴ ب.ظ)kamal3401 نوشته شده توسط: سلام من از ی سوالی عکس گرفتم میخوام ببینم این به چه شکلی حل میشه تنها راهش همینه؟ نمیشه مثلا از روش های پریم یا کروسکال تبدیل به درختش کنی و بعد پیدا کنی؟ |
RE: کمترین هزینه در ارتباط گره های گراف ها - Behnam - ۱۷ خرداد ۱۳۹۵ ۱۱:۵۷ ب.ظ
(۱۷ خرداد ۱۳۹۵ ۱۱:۴۳ ب.ظ)kamal3401 نوشته شده توسط:آها ببینید چون شما گفتید که الگوریتم دیکاسترای جهتدار، واسه همین من اون فایل فارسی رو دادم. الگوریتم دیکاسترا از یک مبدا شروع میکنه و مینیمم مسیر رو به ازای رأسهای مختلف بدست میاره. در حالی که چیزی که شما میخواید به نظرم مسألهی فروشندهی دوره گرد هست! از یک رأس شروع کنیم و تمامی رأسها رو با مینیمم مسافت طی کنیم (به همهی شهرها بریم) و برگردیم به نقطهی اول.(17 خرداد ۱۳۹۵ ۱۱:۳۸ ب.ظ)behnam5670 نوشته شده توسط:ممنون(17 خرداد ۱۳۹۵ ۱۱:۱۴ ب.ظ)kamal3401 نوشته شده توسط: سلام من از ی سوالی عکس گرفتم میخوام ببینم این به چه شکلی حل میشه واسه این مسأله راهحلهای زیادی ارائه شده منتهی NP-hard هست یعنی جواب در مرتبهی چند جملهای نداره. مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. روشهای مختلف رو به صورت ویژوآل اینجا میتونی ببینی مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. اما اگه منظور مسأله این هست که از هر گره نسبت به بقیهی گرهها مینیمم مسیر رو پیدا کنه، اون موقع باید دیکاسترا بزنید اگه منظور این هست که از یک گره شروع کنید و تمامی رأسها رو بپیمایید (بدون بازگشت به محل اول) اون موقع میشه چیزی که شما گفتید و از اون دو الگوریتم باید استفاده کنید و فرقی نداره از چه گرهی شروع کنید. به نظرم منظور سؤال همین هست (و نیازی به بازگشت به نقطهی اول نیست) |