مسئله طولانی ترین مسیر در یک گراف NP-Hard هستش و این فکر کنم یعنی الگوریتم نداره(یا الگوریتم داره ولی الگوریتم قطعی تا الان واسش پیدا نشده!)

توی گراف های DAG ما میتونیم طولانی ترین نسیر رو پیدا کنیم
مسئله کوتاه ترین مسیر در یک گراف هم که الگوریتم داره

اینم یه شعر درباره همین مسئله طولانی ترین مسئله در یک گراف
valis.cs.uiuc.edu/~sariel/misc/funny/longestpath.mp3

فکر کنم پارسه درست گفته
چون تو بدون وزن که حالتی از وزن دار هست سی ال آر اس گفته طول طولانی ترین مسیر رو در زمان خطی نمی شه بدست آورد

پس مدرسان میتونه این حل رو ارایه بده و جایزه ای میلیون دلاری بگیره

Sent from my SM-T210R using Tapatalk

تنها در صورتی میشه طولانی ترین مسیر رو در زمان چند جمله ای بدست آورد که گراف بدون سیکل باشه
چون در اینصورت اصل بهینگی براش صدق میکنه

میشه با جایگزینی max به جای min در فلوید اون رو بدست آورد

(۳۰ دى ۱۳۹۲ ۰۷:۴۱ ب.ظ)tayebe68 نوشته شده توسط:  تنها در صورتی میشه طولانی ترین مسیر رو در زمان چند جمله ای بدست آورد که گراف بدون سیکل باشه
چون در اینصورت اصل بهینگی براش صدق میکنه

میشه با جایگزینی max به جای min در فلوید اون رو بدست آورد

اون دیگه درخته، گراف نیست و فقط یک مسیر بین دو راس وجود داره

Sent from my SM-T210R using Tapatalk

(۳۰ دى ۱۳۹۲ ۱۰:۴۳ ب.ظ)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