PDA

View Full Version : راشال و پریم



mulanhary
یک شنبه 31 اردیبهشت 1385, 00:06 صبح
دوستان عزیز اگه تونستید این سوال رو جواب بدید:
درخت پوشایی که به روش پریم است بهینه تر است یا با روش راشال ؟

raha_hakhamanesh
دوشنبه 01 خرداد 1385, 14:18 عصر
با سلام خدمت دوستان
اگر اشتباه نکنم الگوریتم راشال همون کروسکال هست اگه اشتباه بود مقایسه زیر جواب شما نیست. بنابراین در اینجا من دو الگوریتم کروسکال و پریم رو مقایسه می کنم.
الگوریتم کروسکال در اکثر موارد دارای بهینه زمانی است اما توجه داشته باشید که همیشه اینطور نیست اما چه موقع زمان کروسکال از پریم بدتر می شود مربوط به تعداد نودهای گراف می شود یعنی اگر در حالتی که تعداد گره های گراف کم باشد زمان اجرایی کروسکال E logV خواهد بود در حالیکه پریم (V pow(2 می باشد اما اگر تعداد نودهای گراف زیاد شود به عبارتی V به سمت بینهایت میل کند زمان کروسکال برابر E pow(2) Log V می شود ولی پریم همواره همان مرتبه 2 خواهد بود .
جهت اطلاعات بیشتر به Algorithmics Theory and Practice نوشته Brassard مراجعه کنید .
موفق باشید .

اَرژنگ
دوشنبه 01 خرداد 1385, 14:47 عصر
دوستان عزیز اگه تونستید این سوال رو جواب بدید:
درخت پوشایی که به روش پریم است بهینه تر است یا با روش راشال ؟
بر طبقه http://www.cs.sunysb.edu/~algorith/lectures-good/node18.html
Floyd-Warshall
بهینه تره.

mohandese_hiclass
سه شنبه 02 خرداد 1385, 10:44 صبح
البته اگه از لحاظ بهینگی بحث کنیم یعنی از لحاظ ایجاد درخت پوشای مینیمال هر دو یکی هستن ولی از جهات دیگه پاسخ رها کامله