تحقیق تحليل مساله كوتاهترين مسير در گراف جهت دار 10 ص

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

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

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