08 دى 1396, 07:56 ب.ظ
10 دى 1396, 02:49 ق.ظ
سلام
وقتی صحبت از کوتاه ترین مسیر بین هر زوج از راس ها به میان میاد یاد الگوریتم فلوید می افتیم که پیاده سازی برنامه نویسی پویای ان همان گزینه ی ۲ است که در انجا k نقش راس های میانی از i تا j را بازی می کند یعنی وقتی k=0 یعنی هیچ راس میانی وجود ندارد پس همان وزن یال بین iوj می شود همان شرط پایه یا توقف رابطه ی بازگشی در گزینه ی ۲ ولی وقتی k بزرگتر از ۰ می شود یعنی راس های میانی داریم و این راس های میانی از ۱ تا k در نظر گرفته می شود و رابطه ی بازگشتی دو بخش دارد یا راس k عضو راس های میانی است یا نیست اگر باشد ([tex]d[i,k,k-1]+d[k,j,k-1][/tex]) یعنی از i به k می رویم و بعد از k بهj البته با واسطه گری راس های ۱ تا k-1 و اگر راس k عضو راس های میانی نباشد ([tex]d[i,j,k-1][/tex]) یعنی از i به j با واسطه گری راس های ۱ تا k-1 است. برای توضیح درباره ی گزینه های دیگر به این جمله از کتاب کورمن توجه کنید:
که تمام زیر مسیر های کوتاه ترین مسیر نیز کوتاه ترین مسیر هستند
مثلا کوتاه ترین مسیر از i به j شامل کوتاه ترین مسیر از i به r و بعلاوه ی وزن یالی از r به j یعنی [tex]\delta(i,j)=\delta(i,r)+w_{rj}[/tex]
حالا به گزینه ی یک دقت کنید در اینجا دیگه نقش k عوض شده(نسبت به گزینه ی ۲) که تعداد یال در مسیر را نشان میدهد مثلا اگر k=1 یعنی مسیری با یک یال از i به j وجود دارد که همان شرط توقف است . در رابطه بازگشتی هم r نقش همان انتهای زیر مسیری با یک یال کمتر که در بالا گفتیم را دارد که میتواند هر راسی باشد و ما در نهایت مسیر min را انتخاب میکنیم. این نوع پیاده سازی یافتن کوتاه ترین مسیر درو اقع مبنای یافتن کوتاه ترین مسیر با استفاده از ضرب ماتریس ها است (با قوانینی کمی متفاوت)ولی نسبت به فلوید مرتبه ی بدی دارد . گزینه ی ۳ هم درواقع همین روش است ولی کمی بهبود یافته برای مثال به جای اینکه ماتریس گام ۴ رابه صورت [tex]L^4=L^3.L[/tex] بدست بیاورم به صورت [tex]L^4=L^2.L^2[/tex] حساب میکنیم (یاد اوری شیوه ی از برنامه نویسی پویا که از پایین به بالا محاسبه کرده و نتایج را ذخیره میکنیم).
پس هر سه رابطه جواب این تست است هر چند با مرتبه های متفاوت.(با در نظر گرفتن پیاده سازی های معمول)
گزینه ی ۱ مرتبه اش [tex]O(n^4)[/tex]
گزینه ی ۲ مرتبه اش [tex]O(n^3)[/tex]
گزینه ی ۳ مرتبه اش [tex]O(n^3\lg n)[/tex]
پس جواب تست همان گزینه ی ۴ است. برای مطالعه بیشتر به کتاب کورمن بخش کوتاه ترین مسیر ها از هر راس به راس دیگر رجوع کنید
وقتی صحبت از کوتاه ترین مسیر بین هر زوج از راس ها به میان میاد یاد الگوریتم فلوید می افتیم که پیاده سازی برنامه نویسی پویای ان همان گزینه ی ۲ است که در انجا k نقش راس های میانی از i تا j را بازی می کند یعنی وقتی k=0 یعنی هیچ راس میانی وجود ندارد پس همان وزن یال بین iوj می شود همان شرط پایه یا توقف رابطه ی بازگشی در گزینه ی ۲ ولی وقتی k بزرگتر از ۰ می شود یعنی راس های میانی داریم و این راس های میانی از ۱ تا k در نظر گرفته می شود و رابطه ی بازگشتی دو بخش دارد یا راس k عضو راس های میانی است یا نیست اگر باشد ([tex]d[i,k,k-1]+d[k,j,k-1][/tex]) یعنی از i به k می رویم و بعد از k بهj البته با واسطه گری راس های ۱ تا k-1 و اگر راس k عضو راس های میانی نباشد ([tex]d[i,j,k-1][/tex]) یعنی از i به j با واسطه گری راس های ۱ تا k-1 است. برای توضیح درباره ی گزینه های دیگر به این جمله از کتاب کورمن توجه کنید:
که تمام زیر مسیر های کوتاه ترین مسیر نیز کوتاه ترین مسیر هستند
مثلا کوتاه ترین مسیر از i به j شامل کوتاه ترین مسیر از i به r و بعلاوه ی وزن یالی از r به j یعنی [tex]\delta(i,j)=\delta(i,r)+w_{rj}[/tex]
حالا به گزینه ی یک دقت کنید در اینجا دیگه نقش k عوض شده(نسبت به گزینه ی ۲) که تعداد یال در مسیر را نشان میدهد مثلا اگر k=1 یعنی مسیری با یک یال از i به j وجود دارد که همان شرط توقف است . در رابطه بازگشتی هم r نقش همان انتهای زیر مسیری با یک یال کمتر که در بالا گفتیم را دارد که میتواند هر راسی باشد و ما در نهایت مسیر min را انتخاب میکنیم. این نوع پیاده سازی یافتن کوتاه ترین مسیر درو اقع مبنای یافتن کوتاه ترین مسیر با استفاده از ضرب ماتریس ها است (با قوانینی کمی متفاوت)ولی نسبت به فلوید مرتبه ی بدی دارد . گزینه ی ۳ هم درواقع همین روش است ولی کمی بهبود یافته برای مثال به جای اینکه ماتریس گام ۴ رابه صورت [tex]L^4=L^3.L[/tex] بدست بیاورم به صورت [tex]L^4=L^2.L^2[/tex] حساب میکنیم (یاد اوری شیوه ی از برنامه نویسی پویا که از پایین به بالا محاسبه کرده و نتایج را ذخیره میکنیم).
پس هر سه رابطه جواب این تست است هر چند با مرتبه های متفاوت.(با در نظر گرفتن پیاده سازی های معمول)
گزینه ی ۱ مرتبه اش [tex]O(n^4)[/tex]
گزینه ی ۲ مرتبه اش [tex]O(n^3)[/tex]
گزینه ی ۳ مرتبه اش [tex]O(n^3\lg n)[/tex]
پس جواب تست همان گزینه ی ۴ است. برای مطالعه بیشتر به کتاب کورمن بخش کوتاه ترین مسیر ها از هر راس به راس دیگر رجوع کنید