با سلام.
میتونین یه گراف مثال بزنین که اعمال این دو الگوریتم روی اون جواب مشترکی نداشته باشه؟؟
روش هر دو الگوریتم بسیار شبیه هستند و من فرقشونو متوجه نمیشم.
سلام دوست من
این دوتا اصن بهم ربطی ندارن که،پریم یه روش پیدا کردن درخت پوشای کمینس(درختی که پوشا باشه و مجموع کل یالاش کمینه باشه) ولی دایجسترا یه راسو انتخاب میکنی بعد کوتاهترین مسیرا از این به سایر روسو بدس میاری
موفق باشید
(۲۲ آذر ۱۳۹۱ ۰۶:۵۲ ب.ظ)آلبالو نوشته شده توسط: با سلام.سلام دوست عزیز
میتونین یه گراف مثال بزنین که اعمال این دو الگوریتم روی اون جواب مشترکی نداشته باشه؟؟
روش هر دو الگوریتم بسیار شبیه هستند و من فرقشونو متوجه نمیشم.
این دو الگوریتم از یه لحاظایی شبیه همن مثلا هر دو از یک نود شروع میکنن و پیش میرن
و یا مثلا هر دو از نظر مرتبه زمانی مثل همن n^2 , هر دو را می توان با هرم پیاده سازی
کرد در [tex]\Theta (e log n)[/tex] پیاده سازی کرد .
سلام
من هم به نوبه خودم یه توضیحی بدم
اول اینکه CLRS راجع به این شباهتشون اینجوری میگه
هر دو الگوریتم در هر مرحله از صف مینیمم اولویت(صف وزن ها)برای یافتن سبکترین راس استفاده می کنند واین راس به مجموعه اضافه میشه (مجموعه s در الگوریتم دیکسترا ، ودرخت درحال رشد در پریم)
پس درکل شباهتشون اینه که سعی دارن مسیر کوتاهی بوجود بیارن و در نهایت هم جفتشون به درخت ختم میشن
به نظر من تفاوت اصلیشون در جواب الگوریتم اونهاست
ما در دیکسترا در هر مرحله تمام مسیرها از گره اصلی به باقی گره ها(که مجاور هستن) را نگه میداریم و در هر مرحله این مسیرها را آپدیت میکنیم و در نهایت یک آرایه Nعضوی داریم که مثلا خونه ۳آرایه ،کوتاهترین مسیر به گره ۳ رو نشون میده
اما در پریم ما در هر مرحله تنها یک مسیر را نگه داری میکنیم و در نهایت هم یک هزینه بدست میاریم مثل اینکه یه آرایه با یک خونه داریم!!
تا اونجایی که من دیدم دیکسترا فقط روی گرافهای جهت دار اجرا میشه!
واینکه چرا درختشون یکی میشه چون اگه گراف دیکسترا رو بدون جهت بگیریم اون مجموعه S دیکسترا و مجموعه Bپریم یکی خواهند بود!!(B,Sکتاب پوران)
نمیدونم منطورمو رسوندم یا بیشتر گیج شدی!!
اما توصیه بنده اینه که به شباهتشون توجه نکن چون گیج کننده است
[quote='maryam.raz' pid='148632' dateline='1355331739']
پس درکل شباهتشون اینه که سعی دارن مسیر کوتاهی بوجود بیارن و در نهایت هم جفتشون به یک درخت ختم میشن
سلام در نهایت جفتشون به یه درخت ممکنه ختم نشن مثال نقض براش زیاد هست !
(۲۳ آذر ۱۳۹۱ ۰۷:۲۱ ب.ظ)masume_ml نوشته شده توسط: [quote='maryam.raz' pid='148632' dateline='1355331739']فکرکنم من جمله رو بد نوشتم منظور من از "یک درخت" یکسان بودنشون نبوده منطورم این بود که نتیجه جفتشون درخت هست.
پس درکل شباهتشون اینه که سعی دارن مسیر کوتاهی بوجود بیارن و در نهایت هم جفتشون به یک درخت ختم میشن
سلام در نهایت جفتشون به یه درخت ممکنه ختم نشن مثال نقض براش زیاد هست !
تصحیحش کردم که بچه ها اشتباه برداشت نکنن
(۲۲ آذر ۱۳۹۱ ۰۶:۵۲ ب.ظ)آلبالو نوشته شده توسط: با سلام.
میتونین یه گراف مثال بزنین که اعمال این دو الگوریتم روی اون جواب مشترکی نداشته باشه؟؟
روش هر دو الگوریتم بسیار شبیه هستند و من فرقشونو متوجه نمیشم.
ببینید دایجسترا دنبال اینه که کوتاهترین مسیر ها از یک گره به سایر گره ها رو حساب کنه که به وضوح مشخصه که ممکنه درخت پوشای حاصل بهینه نباشه. اما پریم فقط دنبال درخت پوشای بهینه است . روش کارشون هم یه خرده متفاوته چون پریم اول از یه یال شروع میکنه و بعد یه مجموعه گره تشکیل میده و بعد کوچکترین یالی که با این مجموعه در ارتباطه و ایجاد حلقه نمیکنه رو انتخاب میکنه! اما دایجسترا اول از یه درخت شروع(کوچکترین یالها بین راس مورد نظر و راس های همسایه که البته بازم واضحه که ممکنه درخت اولیه پوشا نباشه یا حتی فقط با یک راس همسایه باشه! )میکنه و بعد یکی یکی یالها رو اصلاح میکنه!
سلام . با تشکر از توضیح Javadem
می خواستم توضیح ساده ای که کورمن توی سی دی تمریناتش به زبان جاوا واسه ی تفاوت این دو گفته بود رو بنویسم ولی دیدم اگه با یه مثال تفاوت رو بگیم خیلی تاثیر گذارتره و تمام ابهامات رو برطرف میکنه .
ببینید اگه گراف زیر داشته باشیم
[attachment=8444]
میدونیم که با روش پریم زیر درخت پوشا به صورت زیر خواهد بود
[attachment=8445]
حالا اگه بخوایم کم هزینه ترین مسیر بین گره A و D از گراف اصلی رو انتخاب کنیم میتونیم به راحتی با استفاده از الگوریتم دایجسترا مسیری با هزینه ی ۴ پیدا کنیم(یال A-D). اما اگه بخوایم این مسیر رو از روی درخت پوشای پریم پیدا کنیم هزینه اون برابر با ۶ هست که بهینه نیست.
خلاصه ی کلام : با دایجسترا شما میتونید به راحتی با حداقل ترین هزینه از گره ی آغازین به تمام گره ها برید درحالی که در پریم همیشه به این صورت نیست.