پارسه گفته گزینه ی ۳ میشه
اما مدرسان توی آزموناش راهی رو معرفی کرده که کراسکال یا پریم میتونن درخت پوشا با بیشترین وزن رو پیدا کنن
توی این سوال نمیتونیم بگیم دایجسترا هم میتونه؟
فکر کنم پارسه درست گفته
چون تو بدون وزن که حالتی از وزن دار هست سی ال آر اس گفته طول طولانی ترین مسیر رو در زمان خطی نمی شه بدست آورد
پس مدرسان میتونه این حل رو ارایه بده و جایزه ای میلیون دلاری بگیره
Sent from my SM-T210R using Tapatalk
تنها در صورتی میشه طولانی ترین مسیر رو در زمان چند جمله ای بدست آورد که گراف بدون سیکل باشه
چون در اینصورت اصل بهینگی براش صدق میکنه
میشه با جایگزینی max به جای min در فلوید اون رو بدست آورد
(۳۰ دى ۱۳۹۲ ۰۷:۴۱ ب.ظ)tayebe68 نوشته شده توسط: تنها در صورتی میشه طولانی ترین مسیر رو در زمان چند جمله ای بدست آورد که گراف بدون سیکل باشه
چون در اینصورت اصل بهینگی براش صدق میکنه
میشه با جایگزینی max به جای min در فلوید اون رو بدست آورد
اون دیگه درخته، گراف نیست و فقط یک مسیر بین دو راس وجود داره
Sent from my SM-T210R using Tapatalk
مسئله طولانی ترین مسیر در یک گراف NP-Hard هستش و این فکر کنم یعنی الگوریتم نداره(یا الگوریتم داره ولی الگوریتم قطعی تا الان واسش پیدا نشده!)
توی گراف های DAG ما میتونیم طولانی ترین نسیر رو پیدا کنیم
مسئله کوتاه ترین مسیر در یک گراف هم که الگوریتم داره
اینم یه شعر درباره همین مسئله طولانی ترین مسئله در یک گراف
valis.cs.uiuc.edu/~sariel/misc/funny/longestpath.mp3
(۳۰ دى ۱۳۹۲ ۱۰:۴۳ ب.ظ)hoomanab نوشته شده توسط:(30 دى ۱۳۹۲ ۰۷:۴۱ ب.ظ)tayebe68 نوشته شده توسط: تنها در صورتی میشه طولانی ترین مسیر رو در زمان چند جمله ای بدست آورد که گراف بدون سیکل باشه
چون در اینصورت اصل بهینگی براش صدق میکنه
میشه با جایگزینی max به جای min در فلوید اون رو بدست آورد
اون دیگه درخته، گراف نیست و فقط یک مسیر بین دو راس وجود داره
Sent from my SM-T210R using Tapatalk
درخت هم یه گراف بدون دور و همبنده
اگر گراف جهت دار باشه ممکنه دو یا چند مسیر بین رئوس داشته باشیم ولی دور نداشته باشیم
تو بعضی تستا می نویسه گراف DAG یا گراف بدون دور؛ اینجا باید توجه کنیم مساله راه حل چند جمله ای داره
حتی اگر هم درخت جهت دار باشه، حداکثر یک مسیر بین دو گره وجود داره یا اصلا مسیری وجود نداره
Sent from my SM-T210R using Tapatalk
(۰۱ بهمن ۱۳۹۲ ۰۷:۲۷ ب.ظ)hoomanab نوشته شده توسط: حتی اگر هم درخت جهت دار باشه، حداکثر یک مسیر بین دو گره وجود داره یا اصلا مسیری وجود نداره
Sent from my SM-T210R using Tapatalk
توی درخت جهت دار درسته، یک یا هیچ مسیر داریم
ولی ممکنه حالتی مثل شکل ضمیمه پیش بیاد که دور نداریم ولی درخت نیست ؛ اینجا میشه بیش از یک مسیر داشت
درسته اما اینا تبصره هستند. اگه اسمی از شرط نیاره، مسیله np hard هست
Sent from my SM-T210R using Tapatalk