جواب اون سوال که می گین dfs تو لوپ می افته چی میشه ؟؟؟؟؟؟؟؟؟؟؟؟؟؟/
(۰۴ اسفند ۱۳۹۰ ۱۱:۱۰ ق.ظ)نسیم۳ نوشته شده توسط: dfs تو لوپ میفته و این سوال تکراری بود و سوال اول طراحی الگوریتم میشد گزینه یک یعنیn-1
دوست عزیز dfs در جستجوی گرافی، اونم با ورن یکسان برای v های مجاور امکان دارد در لوپ بیافتد
من که DFS زدم و به جواب خودم مطمئن بودم ولی جواب سنجش قابل باور نبود
الان چند تا متن لاتین هم سرچ کردم و بازهم همین برداشت رو دارم
توی این متون میگه :
BFSزمان بیشتری رو برای رسیدن به آخرین سطح داره ولی DFS سریعتر به هدف میرسه
صورت سئوال میگه : "دور ترین راس گراف بدون وزن" یعنی هیچ عددی روی یالها نیست و بازهم به این معنی هست که دورترین راس یعنی راسی که تعداد یالهای بیشتری رو باید پیمایش کنیم تا به اون برسیم
و درضمن گفته "کدام روش سریعتر و مناسب تر است؟"
خب مسلما باید : اولا در زمان کمتری پیدا بشه ثانیا توی لوپ نیفته ثالثا یالهای بیشتری طی بشه
ولی "سطحی"اول میاد همه نزدیکترین گرهها رو جستجو میکنه بعد یک سطح میاد پایین تر و همینطور الی آخر . که دراین صورت حداکثر زمان صرف میشه . چون باید تمام رئوس رو طی کنه .
من کتاب روهم که خوندم نوشته:" DFS کوتاهترین مسیرهای تک مبدا را محاسبه میکند"
دایکسترا هم که نمیتونه باشه چون مرتبه زمانش زیاده(( o(v^2 )
dfs مشکل افتادن توی یک مسیر بی نهایت داره
(۰۸ اسفند ۱۳۹۰ ۰۶:۱۶ ب.ظ)fatima1537 نوشته شده توسط: من که DFS زدم و به جواب خودم مطمئن بودم ولی جواب سنجش قابل باور نبود
الان چند تا متن لاتین هم سرچ کردم و بازهم همین برداشت رو دارم
توی این متون میگه :
BFSزمان بیشتری رو برای رسیدن به آخرین سطح داره ولی DFS سریعتر به هدف میرسه
صورت سئوال میگه : "دور ترین راس گراف بدون وزن" یعنی هیچ عددی روی یالها نیست و بازهم به این معنی هست که دورترین راس یعنی راسی که تعداد یالهای بیشتری رو باید پیمایش کنیم تا به اون برسیم
و درضمن گفته "کدام روش سریعتر و مناسب تر است؟"
خب مسلما باید : اولا در زمان کمتری پیدا بشه ثانیا توی لوپ نیفته ثالثا یالهای بیشتری طی بشه
ولی "سطحی"اول میاد همه نزدیکترین گرهها رو جستجو میکنه بعد یک سطح میاد پایین تر و همینطور الی آخر . که دراین صورت حداکثر زمان صرف میشه . چون باید تمام رئوس رو طی کنه .
من کتاب روهم که خوندم نوشته:" DFS کوتاهترین مسیرهای تک مبدا را محاسبه میکند"
دایکسترا هم که نمیتونه باشه چون مرتبه زمانش زیاده(( o(v^2 )
باید این نکات رو هم توی اعتراض به کلید آورد .
سوال ۱۱۲ الگوریتم فلوید
کسی می تونه برام توضیح بده چطور میشه دور منفی رو تشخیص دهیم چون من یک جا خوندم گفته بود اگر یکی از عناصر قطر اصلی منفه بشه انوقت دور منفی داریم با فرض سوال این اتفاق نمیفته
(۰۹ اسفند ۱۳۹۰ ۱۱:۲۰ ب.ظ)tarang نوشته شده توسط: سوال ۱۱۲ الگوریتم فلوید
کسی می تونه برام توضیح بده چطور میشه دور منفی رو تشخیص دهیم چون من یک جا خوندم گفته بود اگر یکی از عناصر قطر اصلی منفه بشه انوقت دور منفی داریم با فرض سوال این اتفاق نمیفته
میدونم، شما از کتاب پارسه خوندید . اما این تست تکراری بوده و از دل تست های سال های قبل در اومده . مطمئن باش که دور منفی رو میتونه تشخیص بده
(۰۹ اسفند ۱۳۹۰ ۱۱:۳۹ ب.ظ)Masoud05 نوشته شده توسط:(09 اسفند ۱۳۹۰ ۱۱:۲۰ ب.ظ)tarang نوشته شده توسط: سوال ۱۱۲ الگوریتم فلوید
کسی می تونه برام توضیح بده چطور میشه دور منفی رو تشخیص دهیم چون من یک جا خوندم گفته بود اگر یکی از عناصر قطر اصلی منفه بشه انوقت دور منفی داریم با فرض سوال این اتفاق نمیفته
میدونم، شما از کتاب پارسه خوندید . اما این تست تکراری بوده و از دل تست های سال های قبل در اومده . مطمئن باش که دور منفی رو میتونه تشخیص بده
tarang راست میگه تو اون تست چیزی از فاصله راس از خودش نگفته بود و گرنه من هم اون تستو خونده بودم. رو همین استدلال دوستمون من زدم ۴ هرچند ۴ هم غلطه ولی فکر کنم نسبت به بقیه درستتر بود (البته با استنباط خودم)
بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست میشه راهنمایی کنید.
بعدشم وقتی میگه فاصله هر راس از خودش صفره یعنی راس هایی هم که هیچ دوری ندارند(چون گراف جهت داره) هم شامل میشه پس اونو چه جوری تشخیص میده
فکر می کنم منظور طراح یه چیز دیگه بوده وبه اشتباه فاصله راس از خودشو مطرح کرده و این یعنی حذف
(۰۹ اسفند ۱۳۹۰ ۱۱:۴۳ ب.ظ)aliebtehaj نوشته شده توسط: بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست میشه راهنمایی کنید.
بعدشم وقتی میگه فاصله هر راس از خودش صفره یعنی راس هایی هم که هیچ دوری ندارند(چون گراف جهت داره) هم شامل میشه پس اونو چه جوری تشخیص میده
اولا اینکه فاصله هر راس با خودش صفره که پیش فرض این الگوریتم هست ثانیاً به نظر استدلال فوق غلطه ( من منظورتون رو از این عبارت " بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست " نمیفهمم اگه میشه واضح تر بگید . متاسفانه همه کتابام رو هم جمع کردم که بخوام ارجاعتون بدم به کتاب
(۱۰ اسفند ۱۳۹۰ ۱۰:۰۶ ق.ظ)Masoud05 نوشته شده توسط:(09 اسفند ۱۳۹۰ ۱۱:۴۳ ب.ظ)aliebtehaj نوشته شده توسط: بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست میشه راهنمایی کنید.
بعدشم وقتی میگه فاصله هر راس از خودش صفره یعنی راس هایی هم که هیچ دوری ندارند(چون گراف جهت داره) هم شامل میشه پس اونو چه جوری تشخیص میده
اولا اینکه فاصله هر راس با خودش صفره که پیش فرض این الگوریتم هست ثانیاً به نظر استدلال فوق غلطه ( من منظورتون رو از این عبارت " بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست " نمیفهمم اگه میشه واضح تر بگید . متاسفانه همه کتابام رو هم جمع کردم که بخوام ارجاعتون بدم به کتاب
نگاه کنید پیش فرض فلوید اینه که طوقه نداشته باشه(یا حداقل صفر باشه) نه اینکه فاصله هر راس تا خودش صفر باشه این یعنی اینکه همه دورها ما طولشان صفر باشه . هیچ کتابی نگفته فاصله هر راس تا خودش صفر باشه . طراح اگه قصدش واقعاً طوقه بود خوب نمیمرد میگفت طوقه تازه تعداد واژه های کمتری هم مصرف می شد ولی مطمئنم خیلی ها استدلال منو از صورت سئوال کردن. وقتی ۱۶ سوال برای یک گرایشی طرح می کنند و درصدا ی هر سوال میرسه به ۶ یا ۷ باید سوالا رو اینقدر قشنگ طرح کنن که جای شک وشبهه نباشه نه اینکه بعد گذشته ۱۰ روز از امتحان هنوز نمی دانیم مفهوم سوال چیه. تازه تو صورت سوال همواره هم آورده ، خود این یعنی همیشه و همه دور هامون صفره.
(۱۰ اسفند ۱۳۹۰ ۱۱:۲۵ ق.ظ)gol نوشته شده توسط: توی کتاب ساختمان داده هادی یوسفی(فصل اخرش) به طور واضح این نکته گفته شده که الگوریتم فلوید قادر به تشخیص دور منفی نمی باشد!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
مشکل من در صورت سواله بصورت غلط جمله فرض رو بیان کرده
(۱۰ اسفند ۱۳۹۰ ۱۰:۰۶ ق.ظ)Masoud05 نوشته شده توسط:(09 اسفند ۱۳۹۰ ۱۱:۴۳ ب.ظ)aliebtehaj نوشته شده توسط: بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست میشه راهنمایی کنید.
بعدشم وقتی میگه فاصله هر راس از خودش صفره یعنی راس هایی هم که هیچ دوری ندارند(چون گراف جهت داره) هم شامل میشه پس اونو چه جوری تشخیص میده
اولا اینکه فاصله هر راس با خودش صفره که پیش فرض این الگوریتم هست ثانیاً به نظر استدلال فوق غلطه ( من منظورتون رو از این عبارت " بعدشم وقتی فاصله هر راس از خودش صفره خوب یعنی همه دورها دارای یال منفیه و دور منفی دیگه در کار نیست. پس ما چه جوری میتونیم دور منفی رو تشخیص دهیم وقتی تو گراف اصلاٌ همپنین دوری نیست " نمیفهمم اگه میشه واضح تر بگید . متاسفانه همه کتابام رو هم جمع کردم که بخوام ارجاعتون بدم به کتاب
این فرمول الگوریتم فلویده تو کتاب clrs صفحه ۶۳۰ که بر اساس این فاصله هر راس با خوش با این فرمول محاسبه میشه پس فاصله هر راس با خودش صفر پیش فرض نیست
دوستانی که علاقه وافر به CLRS دارن ، اینکه فلوید میتونه دور منفی رو تشخیص بده یکی از تمرینهای این کتاب هست . تعجب میکنم میگید نیست . در ضمن توی کتابای تست هم این مورد چند بار اومده و من از کتاب پارسه و پوران و سپاهان این بحث رو دنبال کردم . کلام آخر رو به عهده جناب کرمن میسپرم که نشون میده فلوید دور منفی رو تشخیص میده ( متاسفانه همه کتابام رو جمع کردم که بگم چه صفحه ای رو بخونید ، کم کم دارم پیر میشم از دست کنکور! ) :
Here are two ways to detect negative-weight cycles:
۱/ Check the main-diagonal entries of the result matrix for a negative value. There
is a negative weight cycle if and only if d(n)
ii < 0 for some vertex i :
• d(n)
ii is a path weight from i to itself; so if it is negative, there is a path from i
to itself (i.e., a cycle), with negative weight.
• If there is a negative-weight cycle, consider the one with the fewest vertices.
• If it has just one vertex, then some wii < 0, so dii starts out negative, and
since d values are never increased, it is also negative when the algorithm
terminates.
• If it has at least two vertices, let k be the highest-numbered vertex in the
cycle, and let i be some other vertex in the cycle. d(k−۱)
ik and d(k−۱)
ki have
correct shortest-path weights, because they are not based on negativeweight
cycles. (Neither d(k−۱)
ik nor d(k−۱)
ki can include k as an intermediate
vertex, and i and k are on the negative-weight cycle with the fewest
vertices.) Since i k i is a negative-weight cycle, the sum of
those two weights is negative, so d(k)
ii will be set to a negative value.
Since d values are never increased, it is also negative when the algorithm
terminates.
In fact, it sufÞces to check whether d(n−۱)
ii < 0 for some vertex i . Heres why.
A negative-weight cycle containing vertex i either contains vertex n or it does
not. If it does not, then clearly d(n−۱)
ii < 0. If the negative-weight cycle contains
vertex n, then consider d(n−۱)
nn . This value must be negative, since the cycle,
starting and ending at vertex n, does not include vertex n as an intermediate
vertex.
۲/ Alternatively, one could just run the normal FLOYD-WARSHALL algorithm one
extra iteration to see if any of the d values change. If there are negative cycles,
then some shortest-path cost will be cheaper. If there are no such cycles, then
no d values will change because the algorithm gives the correct shortest paths.
۱/ Check the main-diagonal entries of the result matrix for a negative value. There
is a negative weight cycle if and only if d(n)
ii < 0 for some vertex i :
• d(n)
ii is a path weight from i to itself; so if it is negative, there is a path from i
to itself (i.e., a cycle), with negative weight.
• If there is a negative-weight cycle, consider the one with the fewest vertices.
• If it has just one vertex, then some wii < 0, so dii starts out negative, and
since d values are never increased, it is also negative when the algorithm
terminates.
• If it has at least two vertices, let k be the highest-numbered vertex in the
cycle, and let i be some other vertex in the cycle. d(k−۱)
ik and d(k−۱)
ki have
correct shortest-path weights, because they are not based on negativeweight
cycles. (Neither d(k−۱)
ik nor d(k−۱)
ki can include k as an intermediate
vertex, and i and k are on the negative-weight cycle with the fewest
vertices.) Since i k i is a negative-weight cycle, the sum of
those two weights is negative, so d(k)
ii will be set to a negative value.
Since d values are never increased, it is also negative when the algorithm
terminates.
In fact, it sufÞces to check whether d(n−۱)
ii < 0 for some vertex i . Heres why.
A negative-weight cycle containing vertex i either contains vertex n or it does
not. If it does not, then clearly d(n−۱)
ii < 0. If the negative-weight cycle contains
vertex n, then consider d(n−۱)
nn . This value must be negative, since the cycle,
starting and ending at vertex n, does not include vertex n as an intermediate
vertex.
۲/ Alternatively, one could just run the normal FLOYD-WARSHALL algorithm one
extra iteration to see if any of the d values change. If there are negative cycles,
then some shortest-path cost will be cheaper. If there are no such cycles, then
no d values will change because the algorithm gives the correct shortest paths.
(۱۰ اسفند ۱۳۹۰ ۰۸:۲۸ ب.ظ)Masoud05 نوشته شده توسط: دوستانی که علاقه وافر به CLRS دارن ، اینکه فلوید میتونه دور منفی رو تشخیص بده یکی از تمرینهای این کتاب هست . تعجب میکنم میگید نیست . در ضمن توی کتابای تست هم این مورد چند بار اومده و من از کتاب پارسه و پوران و سپاهان این بحث رو دنبال کردم . کلام آخر رو به عهده جناب کرمن میسپرم که نشون میده فلوید دور منفی رو تشخیص میده ( متاسفانه همه کتابام رو جمع کردم که بگم چه صفحه ای رو بخونید ، کم کم دارم پیر میشم از دست کنکور! ) :
.........
بابا بخدا منم می دونم دور منفی رو تشخیص می ده خیلی خوبم می دونم اون سوال سال ۸۴ ۲۰۰۰ بار خوندم ولی صورت سوال گفته فاصله هر راس از خودش صفره این معنیش این نیست که هزینه طوقه صفره بلکه یعنی تمام دور هامون صفره در غیر این صورت سوال غلط بیان شده. و گرنه این سوال ابتدایی بود من ترم ۵ هم یاد داشتم تمام این فرمول های clrs و پوران و اینا رو خوندم خوب می دونم ولی صحبت من یه چیزه دیگه است.
(۱۰ اسفند ۱۳۹۰ ۰۹:۴۳ ب.ظ)aliebtehaj نوشته شده توسط: بابا بخدا منم می دونم دور منفی رو تشخیص می ده خیلی خوبم می دونم اون سوال سال ۸۴ ۲۰۰۰ بار خوندم ولی صورت سوال گفته فاصله هر راس از خودش صفره این معنیش این نیست که هزینه طوقه صفره بلکه یعنی تمام دور هامون صفره در غیر این صورت سوال غلط بیان شده. و گرنه این سوال ابتدایی بود من ترم ۵ هم یاد داشتم تمام این فرمول های clrs و پوران و اینا رو خوندم خوب می دونم ولی صحبت من یه چیزه دیگه است.
خب ، نمیدونم ، اما چرا باید دورها صفر باشه ؟!!! بنظرم اشکال کار تو همینه . در کل من فقط در حد ارسال بالا بلد بودم . باید سایر دوستان نظر بدن .