تحقیق تحلیل مساله کوتاهترین مسیر در گراف جهت دار ۱۰ ص

لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل :  word (..doc) ( قابل ویرایش و آماده پرینت )
تعداد صفحه : ۱۱ صفحه

 قسمتی از متن word (..doc) : 
 

۱
‏تحلیل ‏مساله ‏کوتاهترین مسیر در گراف‏ جهت دار
‏اگر ‏ یک گراف جهت دار باشد فرض کنید هر لبه ‏ با وزن ‏ مشخص می گردد و هزینه رفتن مستقیم از گره i‏ به j‏ را مشخص میسازد بزودی الگوریتم دایجسترا را که برای یافتن کوتاهترین مسیر در گراف با وزن های مثبت کاربرد دارد را بیان میکنیم . در این بخش و بخش بعدی دو مساله مرتبط با گراف را بیان خواهیم کرد .
‏۱ ) گراف G‏ را در نظر بگیرید ( وزن دار ) اگر این گراف دارای سیکل منفی باشد آنگاه یک سیکل جهت دار c‏ مثل :
‏۲) اگر گراف شامل هیچ دوره ( سیکل‏‌‏)‏‌‏ منفی نباشد یافتن مسیری به نام p‏ از گره آغازی s‏ و گره پایانی t‏ با کمترین هزینه :‏ ‏ ‏باید کمترین باشد به ازای هر مسیر از s‏ به t‏ . این مساله به هر دو نام مسیر با کمترین هزینه و کوتاهترین مسیر نامیده می شود .
‏طراحی و آنالیز الگوریتم :
‏اکنون با شروع تعریف مجدد الگوریتم دایجسترا که برای یافتن کوتاهترین مسیر در گراف هایی که وزن منفی ندارند شروع میکنیم .
۲
‏در این گراف یک مسیر از s‏ به t‏ با ملاقات چندین دفعه دوره ( سیکل ) C‏ بدست می آید .
‏کوتاهترین مسیر با شروع از گره آغازین s‏ به هر نود v‏ در یک گراف اصولا یک الگوریتم حریصانه است . ایده اصلی از یک مجموعه S‏ تشکیل شده است که کوتاهترین مسیر از هر نود s‏ به هر نود داخل مجموعه S‏ شناخته شده است . در این شکل این الگوریتم را نشان می دهیم با ‏ شروع میکنیم . ما میدانیم کوتاهترین مسیر از s‏ به s‏ دارای هزینه صفر است زمانیکه هیچ لبه با وزن منفی نداشته باشیم . سپس این عنصر را به طور حریصانه به مجموعه اضافه میکنیم . در طی مرحله اول الگوریتم حریصانه ما کمترین هزینه لبه های گره s‏ را تشکیل خواهیم داد . بعبارت دیگر یعنی : ‏ . یک نکته مهم با توجه به الگوریتم دایجسترا این است که کوتاهتری مسیر از s‏ به v‏ با یک یال ‏ نمایش داده می شود بنابراین بلافاصله نود v‏ را به مجموعه S‏ اضافه میکنیم . پس مسیر ‏ مسلما کوتاهترین مسیر به v‏ است اگر هیچ یالی با هزینه منفی نداشته باشیم . مسیر های دیگر از s‏ به v‏ باید از یک یال خارج شده از s‏ که حداقل هزینه بیشتری نسبت به لبه (s,v)‏ داشته باشند شروع میشوند .
‏این ایده همواره صحیح نیست بویژه زمانی که دارای لبه های با وزن منفی هستیم .
۳
‏یک ایده برنامه نویسی پویا :
‏یک روش برنامه نویسی پویا سعی بر حل این مساله برای یافتن کوتاهترین مسیر از s‏ به t‏ زمانیکه لبه با وزن منفی داشته باشیم اما سیکل ( دوره ) با طول منفی نداشته باشیم . زر مساله i‏ می تواند کوتاهترین مسیر را تنها بوسیله استفاده از i‏ گره اولیه پیدا کند . این ایده بلافاصله جواب نمی دهد بلکه با اعمال اندکی تغییرات جواب دلخواه را به ما میدهد . الگوریتم Bellman-Ford algorithm‏ ا‏ین الگوریتم را بوسیله برنامه نویسی پویا مطرح کرده و حل ‏کرده اند .
۴
‏(۶.۲۲)‏
‏اگر G‏ دورهای منفی نداشته باشد؛‍‍‍ پس کوتاهترین مسیر ساده از S‏ به t‏ وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1‏ یال دارد.
‏اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P‏ از s‏ به t‏ با بیشترین تعداد از یالها هیچ راس v‏ را مرور نمی کند. اگر P‏ ؛ راس v‏ را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v‏ را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد.
‏اجازه دهید OPT(i,v)‏ را برای تفکیک کمترین هزینه یک مسیر v-t‏ با استفاده از بیشترین یال i‏ مورد استفاده قرار دهیم. مطابق مساله (۶.۲۲) اصی ترین مشکل؛ محاسبه OPT(n-1.s)‏ است.(ما می توانیم به جای ساخت الگوریتم؛ زیر مسائل مرتبط با کمینه هزینه مسیر s-v‏ را با استفاده از بیشترین یالi‏ جایگزین کنیم. این یک موازی طبیعی با الگوریتم دایجسترا شکل خواهد داد. اما در پروتوکل های مسیر یابی که بعدا شرح خواهیم داد؛ این یک روش طبیعی نخواهد بود.)
‏اکنون راه ساده ای را برای بیان OPT(i,v)‏ با استفاده از زیرمسائل کوچکتر نیازداریم. ما دیداه طبیعی تری که نکات بسیاری حالات مختلف را در بر می گیرد را مرور خواهیم کرد؛ این مثال دیگری است از اصل