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

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

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

فرمت فایل: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 این الگوریتم را بوسیله برنامه نویسی پویا مطرح کرده و حل کرده اند .

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

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

نوع فایل: word

قابل ویرایش 67 صفحه

چکیده:

هدف از انجام این پروژه آن است که در لایه ی شبکه سیستم های کامپیوتری با استفادهازالگوریتم های ژنتیک بتوان یک مسیر را از یک نقطه به نقطه ی دیگر انتخاب کرد تا زمان و ترافیک شبکه حداقل شود .روی شبکه ای که از هزاران هزار کامپیوتر تشکیل یاقته است ارسال و دریافت اطلاعات بین دو کامپیوتر می تواند از مسیرهای مختلف و متفاوتی صورت گیرد.این مسیرها دارای طول و میزان ترافیک های متفاوتی خواهند بود.اما ما با بهره گیری از الگوریتم های ژنتیک به دنبال روش هستیم که مسیر بهینه را از لحاظ طول و ترافیک به دست آوریم.به طوریکه زمان ارسال ودریافت اطلاعات کاهش یابد.در انجام این پروژه با تحقیق روی الگوریتم های ژنتیک روشی را برای مسیریابی بر مبنای آن به دست می آوریم که نتیجتاً مسیری بهینه و موفق خواهد بود هر چند که در همسایگی پاسخ بهینه نیز باشد.

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

مقدمه:

 در شبکه های کامپیوتری لایه ی شبکه بسته ها را از مبدا به مقصد می رساند برای رسیدن به مقصد باید در بین راه از چندین منبع بگذرد. کار لایه ی شبکه با لایه ی پیوند داده ها متفاوت است. لایه ی شبکه پایین ترین لایه ای است که با انتقال انتها به انتها سروکار دارد این لایه برای رسیدن به اهدافش باید توپولوژی زیر شبکه ی ارتباطات را بداند و مسیرهای مناسبی را انتخاب نماید.نباید مسیرهایی انتخاب کند که بعضی از خطوط ارتباطی و مسیریابها بار اضافی را تحمل کند و بعضی دیگر بی کار باشند. زمانی که منبع و مقصد در دو شبکه مختلف باشد لایه ی شبکه باید از عهده ی اختلافهای بین آنها برآید و مشکلات ناشی از آنها را حل کند.اکنون به چگونگی عملکرد لایه ی شبکه می پردازیم.دو مسئله ی مختلف برای سازماندهی زیر شبکه وجود دارد.یکی از آنها از اتصالها استفاده می کند و دیگری بی اتصال کار می کند.در زمینه ی عملکرد داخلی زیر شبکه اتصال را مدار مجازی می نامند.بسته های مستقل سازمان بی اتصال،داده گرام نامیده می شود.هدف مدارهای مجازی پرهیز از انتخاب مسیر جدید برای هر بسته یا سلول است.هربسته که از زیر شبکه عبور میکند به مسیریاب میرسد،مسیریاب میداند که از کدام خط رسیده و شماره ی مدار مجازی را نیز میداند و بر مبنای این اطلاعات بسته باید به خط خروجی صحیحی انتقال داده شود. وقتی اتصال شبکه برقرار شد شماره ی مدار مجازی که اکنون در آن ماشین در حال استفاده نیست،به عنوان شناسه ی اتصال انتخاب می شود و این شماره ها فقط دارای ارزش محلی هستند.اگر به طورعمومی در کل شبکه معنی داشته باشند امکان دارد دو مدار مجازی که دارای شماره ی مدار یکسانی هستند از مسیرهایی عبور کنند که منجر به ابهام میشوند.با توجه یه اینکه در این پروژه هدف ما پیدا کردن کوتاهترین مسیر بین دو مسیریاب برای انتقال بسته از مسیریاب مبدا به مسیریاب مقصد میباشد لذا اولین مورد برای شروع کار چگونگی نمایش صورت مسئله می باشد که شرح و بیان مسئله در فصل دوم توضیح داده میشود.به طوری که قابل پیاده سازی باشد.در واقع ما شبکه را به صورت گرافی متشکل از گرهها و یالها نمایش خواهیم داد.برایپیاده سازی این مسئله در فصل سوم به بررسی الگوریتمهای قطعی می پردازیم و به ایننتیجه خواهیم رسید که الگوریتمهای قطعی پیدا کردن جواب بهینه را تضمین می کند ولی هزینه ی زمانی برای n>=40 غیر قابل قبول است در واقع چنین الگوریتمهایی دارای هزینه ی زمانی نمایی خواهند بود که سودمند نخواهند بود.به همین خاطر ما به دنبال روشی خواهیم بود که این هزینه ی زمانی را کاهش دهد و لذا الگوریتمهای ژنتیک روش مناسبی پیشنهاد میشود.که در فصل چهارم به بررسی الگوریتمهای تکاملی و مفاهیم موجود در آن می پردازیم در ادامه فصل مثالی از رنگ آمیزی گراف برای آشنای با کارکرد این الگوریتم ارائه می شود و سپس در فصل پنجم به رائه ی روشی بر اساس الگوریتمهای ژنتیک برای مسئله ی مسیریابی می پردازیم. و براساس این طراحی در فصل 6 به پیاده سازی و شرح کد مربوطه خواهیم پرداخت.و در نهایت ارزیابی و ارائه ی نتایج بدست آمده را در فصل 7 ارائه می دهیم و نتیجه خواهیم گرفت که الگوریتمهایژنتیک جوابهای نزدیک به بهینه را ارائه میدهند.

فهرست مطالب:

چکیده

فصل اول

مقدمه

فصل دوم

بیان و شرح مسئله

فصل سوم

انواع الگوریتم های مسیر یابی

معرفی نمونه ای از الگوریتم قطعی

فصل چهارم

تاریخچه

مفاهیم ژنتیکی

الگوریتم GA

کاربردهای الگوریتم ژنتیک

کد رنگ آمیزی گراف با GA

فصل پنجم

طرح کلی مسئله

فصل ششم

ورودی و خروجی مسئله

پیدا کردن شایسگی هر ژن

عملگر انتخاب

عملگر ترکیب و جهش

نحوه ی اجرا و شرط خاتمه الگوریتم

کد مسیر یابی در شبکه

فصل هفتم

ارزیابی و نتایج

منابع و ماخذ

منابع و مأخذ:

[1] میبدی، محمد رضا وبیگی، حمید."حل مسئله تناظر گراف توسط آتوماتاهای یادگیر". دانشکده ی مهندسی کامپیوتر. دانشگاه صنعتی امیر کبیر. تهران. ایران. 1379.

[2] مبیدی، محمد رضا و رضا پور میر صالح، مهدی. "یک روش ترکیبی (GA+LA) برای حل مسئله تناظر گراف ". دانشکده مهندسی کامپیوتر . دانشگاه صنعتی امیر کبیر. تهران. ایران . 1382.

[3] پرژه پایانی آقای مهندس ناصر لطفی

[4] K.Bryant,’Genetic Algrithms and the travelling salesman problem’, Thesis, Harvey mudd college , Dept.of Mathematics,2000.