مشاوره و تحلیل پروژه

C#.net, Asp.Net, SqlServer
JQuery, CSS3, HTML5
Java, Python, C++
لیست تمام پروژه ها
کد : 56

مسئله فروشنده دوره گرد (tps) به روش پویا



مسئله فروشنده دوره گرد (tps) به روش پویا
این برنامه مسئله فروشنده دوره گرد را با استفاده از روش برنامه نویسی پویا حل می کند
مسئله فروشنده دوره گرد  Travelling salesman problem، یا به اختصار: TSP  به این صورت است که نقشه شهر به صورت یک گراف وزن دار به عنوان ورودی داده میشود که وزن یال ها فاصله شهر ها از همدیگر استفرض کنید یک فروشنده بخواهد از هر شهر تنها یک بار عبور کند که نقطه شروع و پایان یک شهر باشد. کمترین مسافتی که فروشنده می تواند همه مسیر را بپیماید، کدام است؟ در واقع ما به دنبال یک دور همیلتونی بهینه هستیم .این مساله را می توان با نوشتن همه دورهای همیلتونی ممکن با نقطه شروع و پایان از راس و محاسبه کل مسافت پیموده شده برای هر دور حل کرد. اما این کار در عمل برای حتی تعداد کم شهرها بسیار زمان بر است به همین دلیل از روش پویا رای حل این مسئله استفاده می شود

شرح مسئله بدین شکل است:

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

تعداد کل راه‌حل‌ها برابر است با \frac{1}{2}(n-1)! برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یکگراف کامل با n رأس.


مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های 1- هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .




   قیمت:   ريال 200,000
   قیمت مستندات:   ريال 50,000

     

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

در زیر لیستی از پیاده سازی های متنوع همین پروژه را مشاهده می نمایید که ممکن است بیشتر با شرایط شما مطابقت داشته باشد
مسئله فروشنده دوره گرد (tps) به روش پویا با زبان C++
مسئله فروشنده دوره گرد (tps) به روش پویا با زبان C++ و ذخیره ماتریس های حل در فایل
فروشنده دوره گرد با وارد کردن مختصات شهرها
فروشنده دوره گرد با وارد کردن گراف شهرها
برنامه نویسی و طراحی سایت
گروه پروژه برنامه نویسی (پرودان) برنامه نویسی 1393 - 2014
Valid CSS!