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

اختصاصی از فی بوو مقاله در مورد تحلیل مساله کوتاهترین مسیر در گراف جهت دار دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود *پایین مطلب*

فرمت فایل: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) داشته باشند شروع میشوند .

این ایده همواره صحیح نیست بویژه زمانی که دارای لبه های با وزن منفی هستیم .

یک ایده برنامه نویسی پویا :

یک روش برنامه نویسی پویا سعی بر حل این مساله برای یافتن کوتاهترین مسیر از s به t زمانیکه لبه با وزن منفی داشته باشیم اما سیکل ( دوره ) با طول منفی نداشته باشیم . زر مساله i می تواند کوتاهترین مسیر را تنها بوسیله استفاده از i گره اولیه پیدا کند . این ایده بلافاصله جواب نمی دهد بلکه با اعمال اندکی تغییرات جواب دلخواه را به ما میدهد . الگوریتم Bellman-Ford algorithm این الگوریتم را بوسیله برنامه نویسی پویا مطرح کرده و حل کرده اند .

دانلود مقاله کاربرد گراف درریاضی گسسته

اختصاصی از فی بوو دانلود مقاله کاربرد گراف درریاضی گسسته دانلود با لینک مستقیم و پر سرعت .

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

این مقاله درمورد کاربرد گراف درریاضی گسسته می باشد.

خلاصه آنچه در  مقاله کاربرد گراف درریاضی گسسته می خوانید : 

-3. میزان Reality الگوریتم های تصادفی
در این قسمت می خواهیم در مورد مطلب بسیار مهم میزان اطمینان به این نوع الگوریتم صحبت کنیم. همان طور که در شکل مشاهده می نمایید با افزایش محور افقی می‌توانیم با احتمال نزدیک به 100 درصد نتیجه ی حاصل نزدیک به واقعیت می‌باشد. (برای اطلاعات بیشتر از نحوه ی بدست آوردن این صفحه می‌توانید به لینک آن مراجعه نمایید.)
2-3. یک مثال از الگوریتم تصادفی
به عنوان یک مثال واقعی ، Quick Sort یکی از مهمترین الگوریتم هایتصادفی می‌باشد که بدترین حالت خیلی کم اتفاق می افتد و با تحلیل احتمالی این موضوع را ثابت می کنیم و همچنین نوع Randomize Quick Sort که یک الگوریتم تصادفی می‌باشد و صرفا به ورودی آرایه ای مربوط نمی‌باشد بلکه به یک عدد تصادفی تولید شده نیز مربوط می‌باشد.
به عنوان یک مثال فرض کنید در آرایه ای که شامل اعداد 0 و1 می‌باشد بطوری که نصف آن ها 0 و نیمی دیگر 1 می‌باشند حال می خواهیم با جستجو کردن از ابتدای آرایه اولین عنصر با مقدار 1 را بیابیم در مسئله در بدترین حالت باید N/2 تا خانه را چک کنیم تا 1 را پیدا کنیم ولی این حالت بسیار خاص می‌باشد و در حالت متوسط مشاهده می کنیم تعداد حالت جستجو برای این موضوع بسیار کمتر از این مقدار است.
3-3. موارد استفاده از الگوریتم های تصادفی
1. الگوریتم‌های تصادفی بویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! مواجهیم که از روی عناد ورودی بدی را برای ما فراهم می‌کند(آنالیز رقابتی). به همین دلیل انتخاب تصادفی پایه رمزنگاری را تشکیل می‌دهد. این بدین معنی است که دشمن شما(!) نمی‌تواند با یک ورودی خاص بدترین حالت (Worst Case)شما را پدید بیاورد چون که به اعداد تصادفی تولید شده نیز مربوط می‌باشد.
2. از الگوریتم‌های تصادفی معمولا برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آنها تعداد زیاد باشد.برای مثال واپاشی یک هسته پرتوزا را در نظر می‌گیریم.برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم.یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است.حالا اگر تعداد اتمها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمی‌توان حل کرد.بلکه باید به روش‌های عددی روی آورد.در حقیقت الگوریتم‌های تصادفی، راهی برای حل عددی اینگونه مسائل هستند.

4-3. انواع الگوریتم های تصادفی
در مثال بالا الگوریتم تصادفی همیشه درست جواب می‌دهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. الگوریتمهای از نوع اول را لاس وگاس (Las Vegas algorithms) و نوع اخیر را مونت کارلو (Monte Carlo algorithms) می‌نامند. مشاهده می‌کنیم که هر الگوریتم لاس وگاس با گرفتن جوابی احتمالاً نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل می‌شود.
از الگوریتم‌های تصادفی معمولا برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آنها تعداد زیاد باشد.برای مثال واپاشی یک هسته پرتوزا را در نظر می‌گیریم.برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم.یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است.حالا اگر تعداد اتمها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمی‌توان حل کرد.بلکه باید به روش‌های عددی روی آورد.در حقیقت الگوریتم‌های تصادفی، راهی برای حل عددی اینگونه مسائل هستند.
در آزمایشگاه لوس آلاموس در آمریکا دانشمندانی که بر روی پروژه سری منهتن کار می‌کردند، برای بررسی سیستم‌هایی که درآنها تعداد ذرات بالااست، مجبور به ابداع روش و یا الگوریتمی شدند که بعدها نام «مونت کارلو» بر آن قرار دادند.این الگوریتم برای نمونه گیری آماری از سیستم‌هایی با تعداد فضای فاز بالا به کار می‌رود.همچنین از این الگوریتم برای حل معادلات دیفرانسیل و انتگرال گیری معین استفاده می‌شود. دوالگوریتم مشهور مونت کارلو عبارتند از:
1.    الگوریتم متروپلیس
2.    الگوریتم مونت کارلو جنبشی یا n-fold way
این الگوریتم‌ها بیشتر بر این مبنا کار می‌کنند که:ابتداء یک پیکر بندی از سیستم مورد بررسی انتخاب می‌شود.سپس راه‌های موجود برای اینکه سیستم به آنها گذار کند مشخص احتمال آنها محاسبه می‌شود.آنگاه با تولید یک عدد تصادفی احتمالات موجود مورد سنجش قرار می‌گیرند، و سیستم به یکی از حالات ممکن گذار می‌کند.دوباره قسمت دیگری از سیستم انتخاب شده و مراحل قبلی تکرار می‌شود.

3-    مسئله فروشنده دوره گرد
مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem ، به‌اختصار: TSP ) مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه‌حل‌ها برابر است با  برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
1-4. مسئله های مرتبط
•    مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
•    مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP ) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
•    تأمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌ از یک شهر عبور کند. این مسئله به « مسئله سیاستمدار مسافر» نیز شهرت دارد.
2-4. الگوریتم ها
مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
•    طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
•    استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
•    پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
3-4. الگوریتم های دقیق
سرراست ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی  حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.

بخشی از فهرست مطالب مقاله کاربرد گراف درریاضی گسسته

مقدمه
مسئله کوتاهترین مسیر
مسئله پستچی چینی
قضیه شور
مسئله جدول
1-الگوریتم کروسکال
که مرحله ۲ دیگر قابل اجرا نیست توقف کن.
اثبات
1-    مسئله پل های کونیگسبرگ
-2. تاریخچه
1-1-2. حل مسئله
1-2-2. پل ها
-3-2. اهمیت مسئله در تاریخ ریاضیات
راه حل اویلر
3-2. الگوریتم فلزی
1-3-2. شبه کد
2-    الگوریتم های تصادفی
1-3. میزان Reality الگوریتم های تصادفی
2-3. یک مثال از الگوریتم تصادفی
3-3. موارد استفاده از الگوریتم های تصادفی
4-3. انواع الگوریتم های تصادفی
عبارتند از:
1.    الگوریتم متروپلیس
1-4. مسئله های مرتبط
2-4. الگوریتم ها
3-4. الگوریتم های دقیق
4-4. الگوریتم های مکاشفه ای
3-    تصویر نقشه های رنگی
-5. تنظیم گستردگی تصویر
نتیجه گیری

مجموعه ای از فونت های زیبا

اختصاصی از فی بوو مجموعه ای از فونت های زیبا دانلود با لینک مستقیم و پر سرعت .

مجموعه ای از فونت های زیبا و جذاب که می توانید با این فونت ها متن های زیبیا طراحی کنید

دانلود مقاله شبکه ها و تطابق در گراف

اختصاصی از فی بوو دانلود مقاله شبکه ها و تطابق در گراف دانلود با لینک مستقیم و پر سرعت .

دانلود مقاله رشته ریاضی کاربردی با موضوع شبکه ها و تطابق در گراف

نوع فایل : Word 

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

رشته ریاضی کاربردی
شبکه ها و تطابق در گراف

فهرست مطالب

• مقدمه 
• فصل 1 
• شبکه ها 
• 1-1 شارش ها 
• 1-2 برش ها 
• 1-3 قضیه شارش ماکزیمم – برش مینیمم 
• 1-4 قضیه منجر 
• فصل 2 
• تطابق ها 
• 2-1 انطباق ها 
• 2-2 تطابق ها و پوشش ها در گراف های دو بخش 
• 2-3 تطابق کامل 
• 2-4 مسأله تخصبص شغل 
• منابع

شبکه ها
1-1 شارش ها
شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.
تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:
(الف) رأس یکتایی مانند وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.
(ب) رأس یکتایی مانند به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.
(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد که به هر کمان یک ظرفیت، که با نشان داده می‌شود، نسبت می‌دهد.
برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم...

مقاله در مورد شبکه ها و تطابق در گراف

اختصاصی از فی بوو مقاله در مورد شبکه ها و تطابق در گراف دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود *پایین مطلب*

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

تعداد صفحه50

فهرست مطالب

عنوان

صفحه

مقدمه

فصل 1

شبکه ها

1-1 شارش ها

1-2 برش ها

1-3 قضیه شارش ماکزیمم – برش مینیمم

1-4 قضیه منجر

فصل 2

تطابق ها

2-1 انطباق ها

2-2 تطابق ها و پوشش ها در گراف های دو بخش

2-3 تطابق کامل

2-4 مسأله تخصیص شغل

منابع

شبکه ها

• شارش ها

شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.

تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:

(الف) رأس یکتایی مانند  وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند  به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.

(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد که به هر کمان  یک ظرفیت، که با  نشان داده می‌شود، نسبت می‌دهد.

برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.

مثال 1-1 گراف شکل 1-1 یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و ظرفیتها، کنار هر کمان نشان داده شده‌اند. چون ، مقدار کالای حمل شده از a به z نمی‌تواند از 12 بیشتر شود. با توجه به  بازهم این مقدار محدودتر می‌شود و نمی‌تواند از 11 تجاوز کند. برای تعیین مقدار ماکسیممی که می‌توان از a به z حمل کرد  باید ظرفیتهای همة کمانهای بشکه را درنظر بگیریم.

تعریف 1-2 فرض کنیم  یک شبکة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه

الف) به ازای هر کمان  و

ب) به ازای هر ، غیر از مبدأ a یا مقصد  z ،  (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم

مقدار تابع f برای کمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف را قید ظرفیت می‌نامند.