پیاده سازی الگوریتم فلوید با سی شارپ

تاریخ انتشار
۲ خرداد ۱۳۹۸
دسته بندی
تعداد بازدید
612 بازدید
۵۵,۰۰۰ تومان
الگوریتم فلوید یکی از روش هایی هستش که برای مسیریابی بین گره ها استفاده می شود که از نوع روش های برنامه سازی پویا در طراحی الگوریتم می باشد. عنوان انگلیسی این پروژه implement floyd with csharp می باشد.

الگوریتم فلوید

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

عنوان انگلیسی این پروژه implement floyd with csharp می باشد.

این الگوریتم با مرتبه زمانی O(N۳) شاید یکی از بدترین انتخاب ها برای حل مسئله به علت کندی بیش از حد باشد. اما وقتی تعداد نود به اندازه کوچکتر از ۲۰۰ باشد تفاوت قابل توجه ای با الگوریتم های خوب جایگزین ندارد و به علت پیاده سازی ساده و سریع این الگوریتم همیشه اگر در محدودیت های مساله قابل استفاده باشد جایگزین بقیه کاندید ها می شود ولی در غیر این صورت نه.
رابرت فلوید و استفان وارشال همزمان باهم در مقالات مختلف در سال ۱۹۶۲ این الگوریتم را منتشر کردند، و به افتخارشان الگوریتم فلوید-وارشال نام گرفت که به اختصار به آن فلوید نیز گفته می شود، رابرت فلوید دارای یک الگوریتم خوب دیگر برای پیدا کردن دور در لیست پیوندی یا روابط بازگشتی بر اساس مقدار قبلی می باشد که باز با اسم الگوریتم فلوید مشهور است اما به اندازه این الگوریتم اعمال تعدی معروف نیست.
دلیل من برای انتخاب این الگوریتم برای بخش درسنامه الگوریتم ها، روزمره و ساده بودن الگوریتم فلوید بود که با توجه به بازدید های وبلاگ بنظر می رسد دانشجو های زیادی در طول ترم نیاز به مطالعه و استفاده از این الگوریتم دارند.

ماهیت الگوریتم فلوید وارشال

الگوریتم فلوید دارای ماهیت برنامه نویسی پویا می باشد، ابتدا ماتریس مجاورت را به ازای هیچ نود واسطه داریم سپس ماتریس مجاورت را به ازای یک نود واسطه، یعنی فرض کنید رابطه a-c و b-a برقرار باشد به ازای نود واسطه a می توانیم رابطه b-c را نیز برقرار کنیم و یک مرحله الگوریتم را جلو ببریم.
اگر floyd(i,j,k) به ما مقدار کوتاه ترین مسیر نود از i به j با استفاده از k نود اول را برگرداند الگوریتم فلوید بر اساس یک اصل راحت به صورت زیر کار می کند.

floyd(i,j,k)=min(floyd(i,j,k-1),floyd(i,k,k-1)+floyd(k,j,k-1)) 

الگوریتم بالا فلوید را به صورت یک تابع بازگشتی نشان می دهد که به ازای k=0 برابر با ماتریس اولیه می شود. البته این تکه کد تنها وقتی اضافه میشود که بخواهیم از فلوید برای کوتاه ترین مسیر استفاده کنیم، همانطور که در ادامه می بینید میتوان الگوریتم را با تغییر های کوچک روی مسائل دیگری نیز اعمال کرد. این یک خط بین حالات  استفاده از k به عنوان واسطه و استفاده نکردن از k به عنوان واسطه کمینه را انتخاب می کند. این کار بدیهی هست چون هیچوقت به دنبال طولانی تر کردن یک مسیر با استفاده از یک نود میانی نیستیم بین این دو حالت مینیمم را انتخاب می کنیم. در عمل فلوید را نه به صورت بازگشتی و نه کاملا به صورت پویا پیاده سازی می کنند. ما میتوانیم با داشتن یک ماتریس مجاورت یا ماتریس هزینه و در هر مرحله بروز رسانی همان ماتریس در انتها کوتاه ترین مسیر بین تمامی نود ها را داشته باشیم.
اینکار باعث صرفه جویی در مصرف حافظه می شود اما ماهیت پویا و بازگشتی الگوریتم را از بین می برد. این الگوریتم شبیه حالتی از پویا به صورت tabulation یا از پایین به بالا می شود با این تفاوت که در حال بهتر کردن ارتباط هستیم در برنامه نویسی پویا بهتر کردن یک مقدار معنی ندارد.

پیاده سازی الگوریتم فلوید با حافظه بهینه

در هریک از حالات الگوریتم فلوید که در برنامه نویسی رقابتی مطرح می شود نیاز به یک آرایه دو بعدی برای نشان دادن وجود رابطه بین i یا j یا هزینه برای رسیدن از i یا j داریم. در پیاده سازی این الگوریتم سه حلقه for به طول n پشت سرهم می بینیم و سپس همان خط بخصوص مطرح شده در بالا. توجه کنید که همیشه k (یعنی متغیری که واسطه می شود) باید در بالاترین حلقه تغییر کند وگرنه الگوریتم کامل نیست و به ازای تعدادی از ورودی ها خروجی نادرست به دنبال دارد.

شبه کد حالت کلی الگوریتم فلوید


for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
optimise i to j using k

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

 

پیاده سازی این الگوریتم با زبان سی شارپ

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

برای جستجوی پروژه های بیشتر عبارت implement floyd with csharp را جستجو کنید.

جهت مشاهده نحوه پیاده سازی فلوید با سی شارپ فیلم زیر را مشاهده بفرمایید که قسمت های پروژه به طور کامل همراه با نحوه عملکرد آن قابل مشاهده می باشد:

 

برای دریافت  این پروژه باید این پروژه را به سبد خرید خود اضافه کرده سپس عملیات خرید را انجام دهید.

 

راهنمای خرید

برای جستجوی پروژه های بیشتر در این زمینه می توانید عبارت implement floyd with csharp را در موتورهای جستجو سرچ کنید.

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

با جدیدترین و به روز ترین فایل ها و پروژه ها با سایت ایران فایلز همراه باشید.
در صورت هر گونه سوال به آیدی پشتبان سایت به آدرس  @iranfiles_Support  در تلگرام پیام دهید.

مطالعه بیشتر

راهنمای خرید:
  • لینک دانلود فایل بلافاصله بعد از پرداخت وجه به نمایش در خواهد آمد.
  • همچنین لینک دانلود به ایمیل شما ارسال خواهد شد به همین دلیل ایمیل خود را به دقت وارد نمایید.
  • ممکن است ایمیل ارسالی به پوشه اسپم یا Bulk ایمیل شما ارسال شده باشد.
  • در صورتی که به هر دلیلی موفق به دانلود فایل مورد نظر نشدید با ما تماس بگیرید.
زبان برنامه نویسی

#C

نقد و بررسی‌ها

  1. مهرداد قاسمیانمدیر سایت

    امتیاز بینندگان:۱ ستاره

دیدگاه خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *