صفحه‌ها: ۱ ۲
سلام دوستان
میشه لطفا یکی اینو برای من توضیح بده. پوران گزینه ۳ رو زده ولی توضیح نداده
ممنون
[attachment=15121]
من فکر میکنم گزینه ۲ بشه. چون گراف بدون دوره، میشه با 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
ممنون بابت پاسخ کاملتون
اگه گراف DAG باشه و وزن داشته باشه شما کافی هست وزن ها رو در یه منفی ضرب کنید و بایک بار فراخوانی DFS و به اصلاح Relax کردن میتونید کوتاه ترین مسیر رو در کراف منفی که میشه طولانی ترین در مثبت رو پیدا کنید.البته فکر کنم.
میشه با dfs پیمایش کرد و به هر گره ای که رسیدیم هزینه مسیر رو روی گره بنویسیم و اگر از مسیر دیگه هم رسیدیم مقایسه میکنیم هزینه کدوم بیشتره اگه بیشتر بود جایگزین میکنیم. گزینه ۲ درست
ممنون دوستان.
منم فکر میکنم با DFS میشه ولی یه مشکلی هست. آیا تضمینی وجود داره که این مسیری که انتخاب میکنیم حتما طولانی ترین مسیر باشه؟
البته وقتی گفته میشه گراف بدون دور، یعنی میتونیم یه درخت جهت دار در نظر بگیریم دیگه نه؟ بنابراین میشه گفت برای رسیدن به هر گره فقط یک مسیر وجود داره پس همون مسیر طولانی ترین مسیر هست؟
اول شرط relax رو به جای کوچکتر بزرگتر کن
بعد مرتب سازی توپولوژیک انجام می دی
بعد از همون راس به ترتیب relax می کنی موقعی به یه نود می رسی با ماکس مقایسه کن
ولی فکر کنم با bfs هم بشه. سرعتشون که یکسانه. به هر نود که رسید، مقدار ماکس رو آپدیت میکنه.
Sent from my SM-T210R using Tapatalk
اساتید این سؤال هم همینه آیا ؟!!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگه یکیه، چرا تو یه کتاب واسه هر کدوم جوابا مختلف واسش هست؟!
(۱۲ بهمن ۱۳۹۲ ۰۸:۴۵ ب.ظ)minami نوشته شده توسط: اساتید این سؤال هم همینه آیا ؟!!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگه یکیه، چرا تو یه کتاب واسه هر کدوم جوابا مختلف واسش هست؟!
اینجا dag داریم قضیه اش فرق داره
(۱۲ بهمن ۱۳۹۲ ۰۹:۲۷ ب.ظ)izadan11 نوشته شده توسط:(12 بهمن ۱۳۹۲ ۰۸:۴۵ ب.ظ)minami نوشته شده توسط: اساتید این سؤال هم همینه آیا ؟!!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگه یکیه، چرا تو یه کتاب واسه هر کدوم جوابا مختلف واسش هست؟!
اینجا dag داریم قضیه اش فرق داره
مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟
(۱۲ بهمن ۱۳۹۲ ۰۹:۴۹ ب.ظ)minami نوشته شده توسط: مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟
سوال اونجا رو بد دیدم
(دنبال کلمه ی دور بودم اشتباه نوشته بود ندیدمش)
حق با شماست
کلا فکر کنم چون دور نداریم از BFS یا DFS استفاده کنیم فرقی نداره هر دوش یه جواب میده. چون برای رسیدن به هر نود فقط یه راه داریم!
درست میگم دیگه؟