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

دسته بندی: -

قیمت: 2500 تومان

تعداد نمایش: 53 نمایش

ارسال توسط:

تاریخ ارسال: ۱۹ اسفند ۱۳۹۶

به روز رسانی در: ۲۰ اسفند ۱۳۹۶

خرید این محصول:

پس از پرداخت لینک دانلود برای شما نمایش داده می شودو یک نسخه برای شما ایمیل می شود.

2500 تومان – خرید

فرمت فایل : ( ورد )( قابلیت ویرایش و چاپ )قسمتی از متن پروژه …

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

 

اگر  یک گراف جهت دار باشد فرض کنید هر لبه  با وزن  مشخص می گردد و هزینه رفتن مستقیم از گره 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 می  …

« متن کامل را می توانید بعد از پرداخت آنلاین ، آنی دانلود نمائید، چون فقط تکه هایی از متن به صورت نمونه در این صفحه درج شده است »

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

بازدید: 23

خرید این محصول:

پس از پرداخت لینک دانلود برای شما نمایش داده می شودو یک نسخه برای شما ایمیل می شود.

2500 تومان – خرید