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

↓↓ لینک دانلود و خرید پایین توضیحات ↓↓

فرمت فایل: word 

 (قابل ویرایش و آماده پرینت)

تعداد صفحات:11

قسمتی از متن فایل دانلودی:

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

اگر  يك گراف جهت دار باشد فرض كنيد هر لبه  با وزن  مشخص مي گردد و هزينه رفتن مستقيم از گره i به j را مشخص ميسازد بزودي الگوريتم دايجسترا را كه براي يافتن كوتاهترين مسير در گراف با وزن هاي مثبت كاربرد دارد را بيان ميكنيم . در این بخش و بخش بعدي دو مساله مرتبط با گراف را بيان خواهيم كرد .

1 ) گراف G را در نظر بگيريد ( وزن دار ) اگر این گراف داراي سيكل منفي باشد آنگاه يك سيكل جهت دار c مثل :

2) اگر گراف شامل هيچ دوره ( سيكل‌)‌ منفي نباشد يافتن مسيري به نام 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) داشته باشند شروع ميشوند .

این ايده همواره صحيح نيست

و.....