(۰۶ بهمن ۱۳۹۲ ۰۳:۰۶ ب.ظ)hoomanab نوشته شده توسط:  این با چه الگوریتمی میشه n به توان۲؟ جوتب سنجش گزینه ۲ هست


Sent from my SM-T210R using Tapatalk

این سوال برنامه نویسی پویا هست، فرض کنید شما تا یه جایی مسیر بیشترین رو میدونید، و الان توی سطح i هستید، حالا باید همه ی عناصر این سطح رو چک کنید که کدومش بیشتر میشه و ادامه بدید!

میگم این برنامه نویسی پویا هست و فرض شده که مسئله برای i حل شده(یعنی بیشترین تا اینجا رو میدونیم)

میدونم پویا هست. اما از الگوریتم بلمن فورد استفاده کنیم میشه n به توان ۳/ با چه الگوریتمی میشه n به توان ۲!

Sent from my SM-T210R using Tapatalk

(۰۶ بهمن ۱۳۹۲ ۰۸:۱۶ ب.ظ)hoomanab نوشته شده توسط:  میدونم پویا هست. اما از الگوریتم بلمن فورد استفاده کنیم میشه n به توان ۳/ با چه الگوریتمی میشه n به توان ۲!

Sent from my SM-T210R using Tapatalk

اصلا ربطی به گراف نداره،
من این چیزی که به ذهنم میرسه اینه که برای هر عنصر ماتریس شما یه متغییری در نظر بگیر که بیشترین sum رو داره تا اونجا، مثلا واسه ۷ میشه خودش واسه ۳ ردیف دوم میشه ۱۰ و واسه ۸ میشه ۱۵ و .... این جوری که پیش بری برای هر عنصر مثلا توی سطر i شما کافی هست به ۲ مقدار نگاه کنی در واقع اون دوتای بالاییش و ببینی که کدوم ماکسیمم هست . این کار رو فکر کنم بشه توی N^2 انجام داد چون برای هر عنصر غیر از اون مرزی ها و عنصر اول کافی هست دو عنصر بالاییش رو با هم مقایسه کنیم! که جواب هم باید توی سطح آخر دنبالش بگردیم.

خوب همین که شما میگی به n به توان ۳ تا نیاز داره. این همون بلمن فورده که ماترس آپدیت میشه توش

Sent from my SM-T210R using Tapatalk

(۰۶ بهمن ۱۳۹۲ ۱۱:۲۲ ب.ظ)hoomanab نوشته شده توسط:  خوب همین که شما میگی به n به توان ۳ تا نیاز داره. این همون بلمن فورده که ماترس آپدیت میشه توش

Sent from my SM-T210R using Tapatalk

نه دیگه، داری همه چیزو قاطی میکنی! اولا بلمن فورد داینامیک نیست! اون فلوید وارشال هست! بعدش به این لینک یه سر بزن حلش رو میبینی!


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

مهم نیت آدمه

Sent from my SM-T210R using Tapatalk

---

مرسی عالی بود.

Sent from my SM-T210R using Tapatalk