![]() |
درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - نسخهی قابل چاپ |
درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ
میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟ جواب elogv هست میشه بگین چرا؟ |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - masoud67 - 22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ
(۲۲ بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط: میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها. زمانش هم چون از هیپ دو جمله ای استفاده کرده میشه elogv |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۱۲:۳۷ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)masoud67 نوشته شده توسط:مرسی اینجا چون فقط زمان هیپ هست این رو انتخاب کردیم اگر پیاده سازی ماتریس و هرم فیبونانچی بود تو صورت چیزی نگفته بود در مورد شلوغی و اینا اولویت با کدوم بود ؟(22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط: میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها. بازم ممنون که تو این روزا جواب سوالا رو میدین |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - masoud67 - 22 بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۱۲:۳۷ ب.ظ)zahra2012 نوشته شده توسط:اولویت با کمترین مقداره(22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)masoud67 نوشته شده توسط:مرسی اینجا چون فقط زمان هیپ هست این رو انتخاب کردیم اگر پیاده سازی ماتریس و هرم فیبونانچی بود تو صورت چیزی نگفته بود در مورد شلوغی و اینا اولویت با کدوم بود ؟(22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط: میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها. ماتریس میشه N به توان ۲ هیپ دو جمله ای همیشه elogv و هیپ فیبوناچی میشه e+nlogn توی حالت همه چی نامعلوم اصلا معلوم نیست کدوم کمتره |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۰۱:۰۰ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ)masoud67 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۱۲:۳۷ ب.ظ)zahra2012 نوشته شده توسط:اولویت با کمترین مقداره(22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)masoud67 نوشته شده توسط:مرسی اینجا چون فقط زمان هیپ هست این رو انتخاب کردیم اگر پیاده سازی ماتریس و هرم فیبونانچی بود تو صورت چیزی نگفته بود در مورد شلوغی و اینا اولویت با کدوم بود ؟(22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط: میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها. ممنون ![]() |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - mohammad.ardeshiri - 22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ
bainery heap ===========>((V+E)logv));l میشه |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: bainery heap ===========>((V+E)logv));l بله فرمول دقیقش این هست ولی چون اصولن یالها بیشتر از گره ها هستن اون رو به کار می برن |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - mohammad.ardeshiri - 22 بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: bainery heap ===========>((V+E)logv));l توسوالای که حرفی زده نشده مثل بالا حتما باید این فرمول به کار بره |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: bainery heap ===========>((V+E)logv));l این سوال بود یا جواب؟ ![]() |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - mohammad.ardeshiri - 22 بهمن ۱۳۹۲ ۰۳:۵۷ ب.ظ
(۲۲ بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)zahra2012 نوشته شده توسط:نظره شخصیمه ولی با کراسکال نمیشه اینکارو کرد با پریم میشه اینکارو کرد اونم بهترین مرتبش اینه(22 بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: bainery heap ===========>((V+E)logv));l |
RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 23 بهمن ۱۳۹۲ ۱۱:۱۸ ق.ظ
(۲۲ بهمن ۱۳۹۲ ۰۳:۵۷ ب.ظ)mohammad.ardeshiri نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)zahra2012 نوشته شده توسط:نظره شخصیمه ولی با کراسکال نمیشه اینکارو کرد با پریم میشه اینکارو کرد اونم بهترین مرتبش اینه(22 بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: bainery heap ===========>((V+E)logv));l ممنون |