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