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

تحقیق تحلیل مساله کوتاهترین مسیر در گراف جهت دار 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)‏ با استفاده از زیرمسائل کوچکتر نیازداریم. ما دیداه طبیعی تری که نکات بسیاری حالات مختلف را در بر می گیرد را مرور خواهیم کرد؛ این مثال دیگری است از اصل

 

تحقیق ترکیبات و نظریه‌ی گراف 18 ص

تحقیق ترکیبات و نظریه‌ی گراف 18 ص

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

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

‏1
‏در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .
‏این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری می‌باشند حائز اهمیت فراوان می باشند .
‏1-ترکیبات :
‏شاید در نگاه اول ترکیبات یک بخش معماگونه و سطحی از ریاضیات به نظر برسد که دارای کاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می کند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد .‏
‏ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم .
‏سوال : یک اتاقی مشبک شده به طول 8 و عرض 8 داریم که خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست‌ آن حذف شده است (مانند شکل زیر)
‏3
‏حال ما دو نوع موزاییک داریم . یکی 2*1 ( ) و دیگری 1×2 ( ) سوال این است که آیا می توان این اتاق را با این دو نوع موزائیک فرش کرد .
‏احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید «آری» و سعی می کند با کوشش و
‏خطا اتاق را فرش کند ولی این کار شدنی نیست ؟! و اثبات جالبی نیز دارد .
‏اثبات : جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر :
‏حال با کمی دقت متوجه می شویم که هر موزائیک یک خانه از خانه های سیاه و یک خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد که بتوان با استفاده از این موزائیک ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر 32 و تعداد خانه های سیاه برابر 30 می باشد . در نتیجه این کار امکان امکان پذیر نیست .
‏3
‏این مسأله مربوط به مسائل رنگ آمیزی در ترکیبات بوده که دارای دامنه‌ی وسیعی از مسائل دشوار و پیچیده می باشد در زیر چند نمونه از مسائل آسان و سخت را بیان می کنیم .
‏1-ثابت‌کنید هیچ جدولی را نمی توان به موزائیک هایی به شکل و پوشاند .
‏(راهنمایی: ثابت کنید حتی سطر اول جدول را هم نمی توان پوشاند)
‏2-ثابت کنید یک مهره‌ی اسب نمی تواند از یک خانه‌ی دلخواه صفحه‌ی n‏*4 شروع به حرکت کند و تمام خانه ها را طی کند .
‏3-یک شبکه‌ی n‏*m‏ از نقاط داریم یک مسیر فراگیر مسیری است که از خانه‌ی بالا سمت چپ
‏4
‏شروع به حرکت کرده و از همه‌ی خانه هر کدام دقیقاً یک بار عبور کند و به خانه‌ی سمت راست پایین برود ثابت کنید شرط لازم و کافی برای وجود یک مسیر فراگیر در شبکه‌ی n‏*m‏ آن است که لااقل یکی از m‏ یا n‏ فرد باشد (مرحله‌ی دوم المپیاد کامپیوتر ایران) در شکل زیر یک مسیر فراگیر را برای جدول 5*4 می بینیم .
A
‏
‏ B
‏4-ثابت کنید شرط لازم کافی برای پوشش جدول n‏*m‏ با موزائیک های 2*1 یا 1*2 آن است که یا m‏ یا n‏ زوج باشند .
‏حال می‌خواهیم یک مبحث مهم از ترکیبات به نام استقراء را معرفی کنیم.
‏استقراء بعنی رسیدن ازجزء به کل و هم ارز است با اصل خوشترتیبی زیر مجموعه‌ها( اصل خوشتربینی بیان می‌کند که هر مجموعه متناهی از اعداد عضوی به نام کوچکترین عضو دارد).
‏برای اثبات حکمی به کمک استقراء لازم است: