(30 بهمن 1390 02:41 ب.ظ)Masoud05 نوشته شده توسط: [ -> ] (30 بهمن 1390 02:25 ب.ظ)باد نوشته شده توسط: [ -> ]کی گفته مرتب سازی توپولوژیکی با دوباره DFS به دست میاد؟
ا
اون مسئله اجزا همبند قوی هست که ۲ بار dfs میخواد .
یه نکته : قطر گراف توسط bfs محاسبه میشود.
راه حلی که در کتاب کرومن گفته شده اینه که یکبار dfs
میزنیم و دورترین نقطه را پیدا میکنیم سپس از دور ترین نقطه دوباره dfs
میزنیم تا دوباره دورترین نقطه را پیداکنیم این میشه قطر گراف که با مرتبه
(e+v)
ولی اگر بخواهیم با BFS بدست بیاریم باید به تعداد رئوس bfs بزنیم که از مرتبه V*(e+v)O
پس dfs در زمان کمتری جواب رو بدست میاره
این نظر clrs هست
سریعترین روش دو بار bfs زدن برای یافتن طولانی ترین است بدون شک .
عجب بحثی شده این بلند ترین مسیر ! حیف که همه کتابام رو جمع کردم و بسته بندی کردم برای سال دیگه والا یه بحث طولانی با دوستان میکردم . اما بنظرم احتمال bfs بودن زیاده . اما در آخر نظر طراح مهمه نه هیچ کس دیگه
(30 بهمن 1390 07:50 ب.ظ)imi نوشته شده توسط: [ -> ]والله من نظرم عوض نشد. نمی دونم دیگه. باید کلید ها بیاد ببینم نظر اون ها چیه!
-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
چندتا سوال.
۱-مگه فلوید معمولی وقتی دور با وزن منقی داشته باشه متوقف نمیشه؟میشه،درسته؟اگه نشه که اصلا گزینه یکم غلط میشه.
۲-گزینه ۴ میگه حتی دور منفی نداشته باشیمم درست ممکنه کار نکنه؟چرا نباید درست کار کنه؟اگه این فرضو بنا کار قرار بدیم بازم این فرض برای دور منفی کابرد داره برای بقیه موارد که دیگه دور منفی نداریم که اصلا این فرض در مسئله کاربردی نداره،داره؟
من خودم گزینه یکو زدم ولی وقتی این دوستم این نکته رو گفت خیلی راجبش قکر کردم دیدم حق با ایشونه.ولی وقتی این دوتا سوال تو ذهنم اومد به گرینه چهارم شک کردم.به نظر من اگه قرار ۴ درست باشه قسمت اولش درسته،قسمت دوم غلطه.چون وقتی دور نداریم اصلا اون فرض کاربردی نداره،پس دلیلی نداره غلط جواب بده(می دنیم که با وزن منفی درست کار می که فلوید).با فرضی که دوستمون گفته گزینه یکم غلطه.الان...؟من هنوز روی گزینه یک تاکید می کنم.چون درسته صفر میذاریم ولی در طول اجرا الگوریتم شاید بشه تشخیص داد.نمی دوم ولی بنظر چهارم غلطه.
(02 اسفند 1390 02:44 ب.ظ)reynard696969 نوشته شده توسط: [ -> ]-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
چندتا سوال.
۱-مگه فلوید معمولی وقتی دور با وزن منقی داشته باشه متوقف نمیشه؟میشه،درسته؟اگه نشه که اصلا گزینه یکم غلط میشه.
۲-گزینه ۴ میگه حتی دور منفی نداشته باشیمم درست ممکنه کار نکنه؟چرا نباید درست کار کنه؟اگه این فرضو بنا کار قرار بدیم بازم این فرض برای دور منفی کابرد داره برای بقیه موارد که دیگه دور منفی نداریم که اصلا این فرض در مسئله کاربردی نداره،داره؟
من خودم گزینه یکو زدم ولی وقتی این دوستم این نکته رو گفت خیلی راجبش قکر کردم دیدم حق با ایشونه.ولی وقتی این دوتا سوال تو ذهنم اومد به گرینه چهارم شک کردم.به نظر من اگه قرار ۴ درست باشه قسمت اولش درسته،قسمت دوم غلطه.چون وقتی دور نداریم اصلا اون فرض کاربردی نداره،پس دلیلی نداره غلط جواب بده(می دنیم که با وزن منفی درست کار می که فلوید).با فرضی که دوستمون گفته گزینه یکم غلطه.الان...؟من هنوز روی گزینه یک تاکید می کنم.چون درسته صفر میذاریم ولی در طول اجرا الگوریتم شاید بشه تشخیص داد.نمی دوم ولی بنظر چهارم غلطه.
فلوید همواره خاتمه پذیر است و با دور منفی ممکن است جواب صحیح به ما ندهد اما یال منفی موردی نداره
(02 اسفند 1390 07:40 ب.ظ)Masoud05 نوشته شده توسط: [ -> ] (02 اسفند 1390 02:44 ب.ظ)reynard696969 نوشته شده توسط: [ -> ]-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
چندتا سوال.
۱-مگه فلوید معمولی وقتی دور با وزن منقی داشته باشه متوقف نمیشه؟میشه،درسته؟اگه نشه که اصلا گزینه یکم غلط میشه.
۲-گزینه ۴ میگه حتی دور منفی نداشته باشیمم درست ممکنه کار نکنه؟چرا نباید درست کار کنه؟اگه این فرضو بنا کار قرار بدیم بازم این فرض برای دور منفی کابرد داره برای بقیه موارد که دیگه دور منفی نداریم که اصلا این فرض در مسئله کاربردی نداره،داره؟
من خودم گزینه یکو زدم ولی وقتی این دوستم این نکته رو گفت خیلی راجبش قکر کردم دیدم حق با ایشونه.ولی وقتی این دوتا سوال تو ذهنم اومد به گرینه چهارم شک کردم.به نظر من اگه قرار ۴ درست باشه قسمت اولش درسته،قسمت دوم غلطه.چون وقتی دور نداریم اصلا اون فرض کاربردی نداره،پس دلیلی نداره غلط جواب بده(می دنیم که با وزن منفی درست کار می که فلوید).با فرضی که دوستمون گفته گزینه یکم غلطه.الان...؟من هنوز روی گزینه یک تاکید می کنم.چون درسته صفر میذاریم ولی در طول اجرا الگوریتم شاید بشه تشخیص داد.نمی دوم ولی بنظر چهارم غلطه.
فلوید همواره خاتمه پذیر است و با دور منفی ممکن است جواب صحیح به ما ندهد اما یال منفی موردی نداره
-=-=-=-=-=--==-=-=-=--==-=--==-=-=--==-
خوب منم همینو میگم دیگه!با این شرایط گزینه ۴ درست نیست،چون اون شرط ربطی به یال منفی نداره و با این فرض بازم همون فلوید معمولیه پس گزینه ۴ نمی تونه درست باشه
(02 اسفند 1390 09:10 ب.ظ)reynard696969 نوشته شده توسط: [ -> ]خوب منم همینو میگم دیگه!با این شرایط گزینه ۴ درست نیست،چون اون شرط ربطی به یال منفی نداره و با این فرض بازم همون فلوید معمولیه پس گزینه ۴ نمی تونه درست باشه
دور منفی وقتی به وجود میاد که از یک گره به خوش هزینه اش منفی بشه فرض کنید از گره یک به دو هزینه منفی ۳ داشته باشه و از دو به یک هزینه ۱ پس از یک به خودش میشه منفی ۲ با یک بار اجرا کردن، وقتی در هر مرحله صفر بشه چطور تشخیص دهیم
بچه ها من کلید ماهان رو دیدم.طبق دفترچه ی A جوابا اینجور بود:
110 رو فقط یادم نیست :دی
111 شده 3
112 شده 1
113 شده 2
114 شده 4
115 شده 2
امیدوارم همه رو درست زده باشید.من که 3 تا جواب دادم که طبق این کلید درست بودن!
(03 اسفند 1390 01:51 ق.ظ)fardin_ss نوشته شده توسط: [ -> ]بچه ها من کلید ماهان رو دیدم.طبق دفترچه ی A جوابا اینجور بود:
۱۱۰ رو فقط یادم نیست :دی
۱۱۱ شده ۳
۱۱۲ شده ۱
۱۱۳ شده ۲
۱۱۴ شده ۴
۱۱۵ شده ۲
امیدوارم همه رو درست زده باشید.من که ۳ تا جواب دادم که طبق این کلید درست بودن!
منم قبول دارم همه رو ، ۱۱۰ هم فکر کنم ۱ درست باشه(ولی مطمئن نیستم) ، درسته که مدرسان غلط زیاد داره اما اونم 110 رو یک اعلام کرده. کلا رویه سوالای لگوریتم زیاد بحث نیست به جز سوال98 که واقعا موندم مدرسان چطور به nlogk رسیدن
، چون سخت نبود ، بلکه نا آشنا بود و جوابا مشخص (دیگه مثل سوالای نظریه و سیستم عامل جای بحث و نظر دادن یا توضیح اضافی نیست !)
(03 اسفند 1390 01:51 ق.ظ)fardin_ss نوشته شده توسط: [ -> ]بچه ها من کلید ماهان رو دیدم.طبق دفترچه ی A جوابا اینجور بود:
۱۱۰ رو فقط یادم نیست :دی
۱۱۱ شده ۳
۱۱۲ شده ۱
۱۱۳ شده ۲
۱۱۴ شده ۴
۱۱۵ شده ۲
امیدوارم همه رو درست زده باشید.من که ۳ تا جواب دادم که طبق این کلید درست بودن!
در کتاب Design Analisys and Algorithm، قسمت DFS با شکل و توضیح نوشته که:
هر دو الگوریتم BFSو DFS مرتبه یکسانی برای بدست آوردن Longest Path دارند اما الگوریتم DFS دارای تقریب بهتری نسبت به BFS است
باید اون صفحه رو اسکن کنم براتون تا منظورمو بفهمید (: در ضمن موقعی میشه از جستجوی توپولوژیکال استفاده کرد که گراف DAG باشد
من که نفهمیدم آخر کدومش درسته
ولی این یه مقاله هست من که زبانم خوب نیست دوستانی که زبانشون خوبه بخونن نتایج رو بگن .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ولی یه خطش به وضوح گفته :
DFS gives a better approximation of the longest path than BFS
(03 اسفند 1390 02:18 ب.ظ)a i نوشته شده توسط: [ -> ]من که نفهمیدم آخر کدومش درسته
ولی این یه مقاله هست من که زبانم خوب نیست دوستانی که زبانشون خوبه بخونن نتایج رو بگن .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ولی یه خطش به وضوح گفته :
DFS gives a better approximation of the longest path than BFS
دقیقا همین جمله رو از این کتابی که من دارم آورده ،یکی از دلایلش هم وجود یال پشتی Back Edge در الگوریتم DFS هست
سلام به همگی، من فقط میخوام اینو بگم که بعضی از دوستان این سوالو با مساله ی یافتن طولانی ترین مسیر اشتباه گرفتن. در صورتی که سوال کلا یه چیز دیگه ایه! تو صورت سوال گفته :
" دورترین راس از یک راس داده شده ی v ، در یک گراف بدون وزن، راسی است که کوتاهترین فاصله ی آن تا v بیشترین باشد"
یعنی میخوایم دورترین راس از v رو ،" با تعریف بالا "، پیدا کنیم. خوب با یه بار BFS طول "کوتاهترین مسیرها" از v به همه ی راسای دیگه بدست میاد. و اونی که "طول کوتاهترین مسیرش" از همه بیشتره میشه جواب.
DFS و TOPOLOGICAL_SORT هیچ کدوم نمیتونن "کوتاهترین فاصله از یک راس داده شده" رو پیدا کنن .
دایجسترا میتونه پیدا کنه ولی چون گراف بی وزنه باید از BFS استفاده کرد.
DFS gives a better approximation of the longest path than BFS
این جمله میگه dfs زمان تخمینی بهتری نسبت به bfs میده شاید الگوریتم دیکسترا هم بتونه دورترین راس رو پیدا کنه ولی چون مسئله گفته کدام مناسب تر و سریعتر است به نظر من dfs گزینه مناسب تری هست
(03 اسفند 1390 05:00 ب.ظ)payman نوشته شده توسط: [ -> ]DFS و TOPOLOGICAL_SORT هیچ کدوم نمیتونن "کوتاهترین فاصله از یک راس داده شده" رو پیدا کنن .
دایجسترا میتونه پیدا کنه ولی چون گراف بی وزنه باید از BFS استفاده کرد.
از لحاظ زمانی هم سریعتر هست؟
dfs تو لوپ میفته و این سوال تکراری بود و سوال اول طراحی الگوریتم میشد گزینه یک یعنیn-1