سلام. عکس آپلود نمیشه. اینجا صورت رو مینویسم:
"در یک گراف جهت دار، بدون دکر و وزن دار میخواهیم طولانی ترین مسیر از یک راس مشخص شده به بقیه راس ها را به دست آوریم. این کار ور چه مرتبه ای انجام می پذیرد؟!
۱-O(EV)
۲-O(E+V)
۳-O(V^3)
۴-این کار در زمان چند جمله ای انجام نمیشود.
جواب مدرسان: گزینه ۳ با کمی تغییر در بلمن فورد.
Sent from my SM-T210R using Tapatalk
(۰۹ بهمن ۱۳۹۲ ۰۵:۴۹ ب.ظ)hoomanab نوشته شده توسط: سلام. عکس آپلود نمیشه. اینجا صورت رو مینویسم:کلا پیمایش bfs با یال سرو کار داره و بحثای فاصله(طول مسیر) هم به همین پیمایش bfs انجام میشه بنابراین اگر با لیست مجاورتی نشون بدیم مرتبش v+e
"در یک گراف جهت دار، بدون دکر و وزن دار میخواهیم طولانی ترین مسیر از یک راس مشخص شده به بقیه راس ها را به دست آوریم. این کار ور چه مرتبه ای انجام می پذیرد؟!
۱-O(EV)
۲-O(E+V)
۳-O(V^3)
۴-این کار در زمان چند جمله ای انجام نمیشود.
جواب مدرسان: گزینه ۳ با کمی تغییر در بلمن فورد.
Sent from my SM-T210R using Tapatalk
مدرسان چی بگیم همش مارو به شک انداخته در عین اینکه کتابای خوبی دارهااااااااااا
(۰۹ بهمن ۱۳۹۲ ۰۵:۴۹ ب.ظ)hoomanab نوشته شده توسط: سلام. عکس آپلود نمیشه. اینجا صورت رو مینویسم:
"در یک گراف جهت دار، بدون دکر و وزن دار میخواهیم طولانی ترین مسیر از یک راس مشخص شده به بقیه راس ها را به دست آوریم. این کار ور چه مرتبه ای انجام می پذیرد؟!
۱-O(EV)
۲-O(E+V)
۳-O(V^3)
۴-این کار در زمان چند جمله ای انجام نمیشود.
جواب مدرسان: گزینه ۳ با کمی تغییر در بلمن فورد.
Sent from my SM-T210R using Tapatalk
به صورت کلی اصل بهینگی برای مسئله پیدا کردن طولانی ترین مسیر برای گراف دور دار صادق نیست و از زمان چندجمله ای قابل حل نیست اما تو این سؤال چون گراف ما بی دور هست میشه الگوریتم فلوید رو تغییر داد، به جا بی نهایت قرار دادن طول مسیر بین دو یال، با صفر مقدار دهی اولیه می کنیم و به جا مینیمم، ماکسیمم رو به کار می بریم، هزینه هم همون گزینه ۳ میشه.
من الگوریتم مقسمی دارم، اونم گزینه ۳ زده
موفق باشید
چرا bfs نمیشه؟!
Sent from my SM-T210R using Tapatalk
(۱۲ بهمن ۱۳۹۲ ۰۹:۳۸ ب.ظ)hoomanab نوشته شده توسط: چرا bfs نمیشه؟!
Sent from my SM-T210R using Tapatalk
چطوری با bfs میشه آخه؟
طولانی ترین مسیر رو میخوایم! راه حلتونو میگید ؟
از هر راس به همسایه هاش که رسیدیم، بیشترین طول مسیر رو ذخیره میکنیم
Sent from my SM-T210R using Tapatalk
(۱۲ بهمن ۱۳۹۲ ۱۰:۳۰ ب.ظ)hoomanab نوشته شده توسط: از هر راس به همسایه هاش که رسیدیم، بیشترین طول مسیر رو ذخیره میکنیم
Sent from my SM-T210R using Tapatalk
من الان دچار دوگانگی شدم راستش، تو دو سال مختلف یه سؤال هر کدوم یه طور مختلف حل شده، شاید راه حل شما هم درست باشه.