صفحه‌ها: ۱ ۲
سلام.
آیا فلوید با دور منفی کار میکنه؟
آیا فلوید برای گراف جهت دار و بی جهت یکسانه؟ آیا بهینگی برای هر دو برقراره؟(تست IT سراسری ٨٤)
آیا از فلوید برای طولانی ترین مسیر میشه استفاده کرد؟
اینها سوالاتین که من دارم و کتاب کنکورا خیلی گیجم کردن. یکی اینا رو به وضوح توضیح بده لطفا.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
سلام .
(۱۴ دى ۱۳۹۱ ۰۴:۴۷ ب.ظ)Amir V نوشته شده توسط: آیا فلوید با دور منفی کار میکنه؟
طبق اثباتی که توی کتاب CLRS آورده شده اگه دور منفی در گراف وجود داشته باشه اونوقت کوتاه ترین مسیر بین دو راس [tex]-\infty[/tex] میشه پس فلوید نمیتونه با دور منفی کار کنه .
دو تا نکته قابل اثبات در همین بحث وجود داره که بهتره حواسمون بهش باشه البته به راحتی هم قابل اثبات هستن :
۱/ با الگوریتم فلوید میتوان وجود دور منفی در گراف را تشخیص داد
۲/ الگوریتم فلوید میتواند با وجود یال منفی(نه دور منفی) کوتاه ترین مسیر بین دو راس رو پیدا کند
(۱۴ دى ۱۳۹۱ ۰۴:۴۷ ب.ظ)Amir V نوشته شده توسط: ۱/آیا فلوید برای گراف جهت دار و بی جهت یکسانه؟
۲/آیا بهینگی برای هر دو برقراره؟(تست IT سراسری ٨٤) ||||| آیا از فلوید برای طولانی ترین مسیر میشه استفاده کرد؟
۱/من تا حالا گراف بدون جهت در صورت تست فلوید ندیدم . ولی جهت دار بودن یا نبودن گراف برای الگوریتم فلوید مهم نیست چون به نظر من مهم فقط وزن یال هاست مثلا میتونیم وجود یک یال بدون جهت بین دو راس رو همون یال دو جهته در نظر بگیریم . در کل میگم من ندیدم گراف بدون جهت رو واسه فلوید بدن اگه تو دیدی بزار تا روش بحث کنیم .
۲/ این تست IT84 ، میخواد تعداد گام طولانی ترین مسیر رو بین دو راس در یک گراف بدون وزن پیدا کنه پس معلومه که در این مورد اصلا الگوریتم فلوید به درد نمیخوره چون این الگوریتم با وزن یال های کار میکنه و کوتاه ترین مسیر وزنی رو پیدا میکنه نه بر اساس طول مسیر. پس در حیطه ی الگوریتم های پویا نمیگنجه چون نمیتونیم مسیر بهینه رو پیدا کنیم و در مورد این تست باید به دیگر الگوریتم ها مثل BFS و امثالهم رجوع کرد
ممنون واسه جواب.
میشه همین مسئله رو برای بلمن فورد هم بگید؟
(۱۴ دى ۱۳۹۱ ۰۵:۵۲ ب.ظ)Amir V نوشته شده توسط: ممنون واسه جواب.
میشه همین مسئله رو برای بلمن فورد هم بگید؟
جدای تفاوت زمانی و این چیزا تفاوت اصلی فلوید و بلمن فورد این است که بلمن فورد بر عکس فلوید میتونه با وجود دور منفی باز کوتاه ترین مسیر رو بین دو راس پیدا کنه بقیه موارد هم که دیگه تابلو هستش.
(۱۴ دى ۱۳۹۱ ۰۵:۵۵ ب.ظ)mp1368 نوشته شده توسط: بلمن فورد بر عکس فلوید میتونه با وجود دور منفی باز کوتاه ترین مسیر رو بین دو راس پیدا کنه بقیه موارد هم که دیگه تابلو هستش.مطمئنید در مورد این حرفتون؟! به نظر من نمی تونه!هیچ کدوم با دور منفی نمی تونن!
اره منم موافقم.
بلمن فورد میتونه دور منفی رو تشخیص بده! اما نمیتونه در این شرایط مسیر مینیموم رو پیدا کنه و ارور میده.
اینو الان تو پوران دیدم:
![[تصویر: 152089_1_1379086681.jpg]](https://img.manesht.ir/152089_1_1379086681.jpg)
اما فلوید رو فکر کنم درست گفتن. نمیدونم...
Sent from my Google Galaxy Nexus using Tapatalk 2.4
(۱۴ دى ۱۳۹۱ ۰۸:۴۶ ب.ظ)Amir V نوشته شده توسط: اره منم موافقم.
بلمن فورد میتونه دور منفی رو تشخیص بده! اما نمیتونه در این شرایط مسیر مینیموم رو پیدا کنه و ارور میده.
سلام . ببخشید من کد برنامه رو یه کم فراموش کرده بودم الان دوباره چک کردم
الگوریتم بلمن فورد در صورت وجود دور منفی در کوتاه ترین مسیر بین دو راس مقدار False رو بر میگردونه مبنی بر عدم موفقیت الگوریتم.
پس تفاوت بلمن فورد و فلوید چیه؟
جز اینکه فلوید از مرتبه [tex]O(n^3)[/tex] و بلمن-فورد از [tex]O(n.e)[/tex] هست، دیگه چه فرقی دارن؟
(۱۴ دى ۱۳۹۱ ۰۹:۳۹ ب.ظ)Amir V نوشته شده توسط: پس تفاوت بلمن فورد و فلوید چیه؟
جز اینکه فلوید از مرتبه [tex]O(n^3)[/tex] و بلمن-فورد از [tex]O(n.e)[/tex] هست، دیگه چه فرقی دارن؟
دیگه تفاوتی بیشتر از زمان اجرا که البته تفاوت مهمی است که این الگوریتم بلمن فورد رو مطرح کردن و نکته ای که خودت عکسش رو گذاشتی من ندیدم .
بچه ها ممنون میشم بحث رو یه جمع بندی کلی بکنیم!
هر دو الگوریتم می تونن وجود دور منفی رو در گراف تشخیص بدن.
الگوریتم بلمن فورد بر عکس فلوید در صورت وجود سیکل منفی باز هم می تونه بدون هیچ مشکلی کوتاهترین مسیر رو تشخیص بده اما فلوید در صورت وجود سیکل منفی نمیتونه کوتاهترین مسیر رو برگردونه و فقط سیکل منفی رو تشخیص میده! درسته؟؟!
و تفاوت دیگه هم مرتبه اجرایی دو تا الگوریتمه دیگه همین؟
یه سوال دیگه هم داشتم ممنون میشم جواب بدید.
وقتی گراف شلوغ باشه و دور منفی نداشته باشیم از بین الگوریتم های فلوید و بلمن فورد بهترین و بدترین انتخاب برای پیدا کردن کوتاهترین مسیر کدومه؟
(برای هیپ از باینری هیپ استفاده شده)
سوال آزمون آزمایشی بود.
پاسخ رو فلوید-بلمن فورد انتخاب کرده، میشه دلیلشو یکی بگه؟
ممون. موفق باشید دوستای خوبم.
(۱۹ دى ۱۳۹۱ ۰۲:۴۳ ب.ظ)Eng_Sara نوشته شده توسط: هر دو الگوریتم می تونن وجود دور منفی رو در گراف تشخیص بدن.ببین دو تاشون سیکل منفی رو تشخیص میدن. اما هیچ کدوم مسئله رو حل نمیکنن. توی الگوریتمی که عکسش رو گذاشتم میبینی که نوشته اررور بر میگردونه.
الگوریتم بلمن فورد بر عکس فلوید در صورت وجود سیکل منفی باز هم می تونه بدون هیچ مشکلی کوتاهترین مسیر رو تشخیص بده اما فلوید در صورت وجود سیکل منفی نمیتونه کوتاهترین مسیر رو برگردونه و فقط سیکل منفی رو تشخیص میده! درسته؟؟!
نقل قول: و تفاوت دیگه هم مرتبه اجرایی دو تا الگوریتمه دیگه همین؟آره.
نقل قول: یه سوال دیگه هم داشتم ممنون میشم جواب بدید.نمیدونم...
(۱۹ دى ۱۳۹۱ ۰۲:۴۳ ب.ظ)Eng_Sara نوشته شده توسط: بچه ها ممنون میشم بحث رو یه جمع بندی کلی بکنیم!سلام
هر دو الگوریتم می تونن وجود دور منفی رو در گراف تشخیص بدن.
الگوریتم بلمن فورد بر عکس فلوید در صورت وجود سیکل منفی باز هم می تونه بدون هیچ مشکلی کوتاهترین مسیر رو تشخیص بده اما فلوید در صورت وجود سیکل منفی نمیتونه کوتاهترین مسیر رو برگردونه و فقط سیکل منفی رو تشخیص میده! درسته؟؟!
و تفاوت دیگه هم مرتبه اجرایی دو تا الگوریتمه دیگه همین؟
یه سوال دیگه هم داشتم ممنون میشم جواب بدید.
وقتی گراف شلوغ باشه و دور منفی نداشته باشیم از بین الگوریتم های فلوید و بلمن فورد بهترین و بدترین انتخاب برای پیدا کردن کوتاهترین مسیر کدومه؟
(برای هیپ از باینری هیپ استفاده شده)
سوال آزمون آزمایشی بود.
پاسخ رو فلوید-بلمن فورد انتخاب کرده، میشه دلیلشو یکی بگه؟
ممون. موفق باشید دوستای خوبم.
اون همه زحمت کشیده شده برای پاسخ نامه توش کامل توضیح دادبه شده من نمیفهمم چرا هنوز ابهام وجود داره:پی
الگوریتم فلوید یک الگوریتم برنامه نویسی پویا می باشد که مرتبه آن V به توان ۳ می باشد. الگوریتم فلوید تمام کوتاه ترین مسیرها را به تمام راس ها گیر می آورد.
از طرفی دیگر مرتبه الگوریتم بلمن فورد برابر با O(VE) می باشد. که در گراف شلوغ به دلیل این که یالها از مرتبه V به توان ۲ می باشند بنابراین مرتبه اش می شود V به توان ۳/ اما الگوریتم بلمن فورد برای یافتن کوتاه ترین مسیرها از یک راس به باقی راس ها میباشد. درحالیکه تو صورت سوال کوتاه ترین مسیر بین هر دو جفت راس را خواسته است. بنابراین باید بر روی تمامی V راس آن را اجرا کنیم که مرتبه اش می شود از مرتبه V به توان ۴/
اینجا امکانات تایپیش محدوده نتونستم فرمولها رو درست تایپ کنم شرمنده
من چرا تو تایپیکای درسی دکمه لایک ندارم؟!
امیر ممنونم.
ولی فکر کنم تفاوت دیگه ای هم داشته باشناااااا....
________________________________________________
آقای جهانی ممنونم از توضیحاتتون.بله پاسخنامه جواب سوال رو کامل نوشته ولی کلاً من تو این دوتا الگوریتم فکر میکردم یکم لنگ میزنم!
اونم که حل شد فکر کنم!
پس با این تفاسیر هیچ الگوریتمی دور منفی (نه یال منفی) را نمی تواند حل کند؟
(۱۴ دى ۱۳۹۱ ۰۵:۳۴ ب.ظ)mp1368 نوشته شده توسط: ۲/ الگوریتم فلوید میتواند با وجود یال منفی(نه دور منفی) کوتاه ترین مسیر بین دو راس رو پیدا کند
مطمئنید؟ الان من یه تست تو مقسمی دیدم این جمله رو نقض می کرد صورت تست:
اگه یالهای منفی داشته باشیم کدوم گزینه بهترین توصیف برای فلویده؟(مهندسی ۸۴)
۱- می شه باهاش وجود یا عدم وجود دور منفی رو تشخیص داد
۲- الگوریتم برای یالهای منفی ولی بدون دور منفی ممکن است در دور بیفتد.
۳- الگوریتم برای یالهای منفی ولی بدون دور منفی متوقف می شود ولی درست کار نمی کند.
۴- الگوریتم برای یالهای منفی ولی بدون دور منفی متوقف می شود ولی جوابش همیشه غلطه!
جواب:۱
توضیح بدین ممنون می شم
